Abstract:
A method for selecting routes for items being sent from a given beginning node to a given destination node within a network. Each segment of a trip is evaluated and assigned a negative reward based on the deviation from the ideal length of time to complete that segment. Upon arrival of the item at the destination node, the route is assigned a large positive reward. The system is configured to attempt to maximize rewards at all times by selecting the routes with the lowest likelihood of delay. As more and more trips are completed, the control system may define a policy that selects routes based on their probability of yielding the highest reward.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the benefit of provisional patent application Ser. No. 62113484, filed Feb. 8, 2015 by the present inventor. 
     
    
     FIELD OF INVENTION 
       [0002]    The present invention relates to methods for using artificial intelligence to route items through networks. 
       BACKGROUND OF INVENTION 
       [0003]    The following is a tabulation of some prior art that presently appears relevant: 
         [0000]    
       
         
               
             
               
               
               
               
             
           
               
                   
               
               
                 U.S. Patent Documents 
               
             
          
           
               
                 Patent Number 
                 Kind Code 
                 Issue Date 
                 Patentee 
               
               
                   
               
               
                 6,411,701 
                 B1 
                 2002 Jun. 25 
                 Nokia Siemens Networks 
               
               
                   
                   
                   
                 GmbH and Co KG 
               
               
                 5,142,570 
                 A 
                 1992 Aug. 25 
                 TTI Inventions A LLC 
               
               
                 6,606,380 
                 B1 
                 2003 Aug. 12 
                 Telefonaktiebolaget 
               
               
                   
                   
                   
                 L M Ericsson 
               
               
                 5,590,118 
                 A 
                 1996 Dec. 31 
                 Alcatel-Lucent NV 
               
               
                 634122 
                 B1 
                 2002 Jan. 29 
                 Telefonaktiebolaget 
               
               
                   
                   
                   
                 L M Ericsson 
               
               
                 6,829,347 
                 B1 
                 2004 Dec. 7 
                 RPX CLEARINGHOUSE 
               
               
                   
                   
                   
                 LLC 
               
               
                 6,282,170 
                 B1 
                 2001 Aug. 28 
                 RPX CLEARINGHOUSE 
               
               
                   
                   
                   
                 LLC, World Trade Center 
               
               
                   
                   
                   
                 Montreal 
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
               
               
             
           
               
                   
               
               
                 U.S. Patent Application Publications 
               
             
          
           
               
                 Publication Nr 
                 Kind Code 
                 Publ. Date 
                 Applicant 
               
               
                   
               
               
                 20090190579 
                 A1 
                 2009 Jul. 30 
                 Telefonaktiebolaget 
               
               
                   
                   
                   
                 L M Ericsson 
               
               
                   
               
             
          
         
       
     
         [0004]    Various types of networks are used to deliver items from a starting point to an end point via links between nodes. However, currently available methods do not always select the most efficient route in real-time. Delays due to traffic in a network may cause an item to arrive later than normal at its destination. A need exists for a method to intelligently route items within a network from a starting point to a destination based on historical data of past trips within the network. 
       SUMMARY OF INVENTION 
       [0005]    It is a goal of the present invention to provide a method for intelligently routing items through a network that selects the best fastest route based on historical data. 
         [0006]    The present invention achieves the aforementioned goal through a routing method capable of intelligently selecting paths for an item to most rapidly reach its destination. According to the proposed invention, each segment of a trip is evaluated and assigned a small negative reward based the amount of delay incurred in each segment. Upon completion of a trip, a large positive reward is assigned. The system then calculates the value of each trip based on the net rewards of that trip. The control system can then use the value of each trip to define a policy to select the best route for any given future trip at a particular time. That is, the route with the highest probability of yielding the highest net reward. 
     
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         [0007]      FIG. 1  illustrates a network comprised of a plurality of nodes connected by links embodying features of the present invention. 
           [0008]      FIG. 2  illustrates another network comprised of a plurality of nodes connected by links embodying features of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0009]    The present invention will now be described in detail with reference to a few embodiments thereof as illustrated in the accompanying drawings. In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art, that the present invention may be practiced without some or all of these specific details. In other instances, well known process steps and/or structures have not been described in detail in order to not unnecessarily obscure the present invention. 
         [0010]    Generally, the present invention relates to a method for routing items through a network of nodes connected by links using a positive and negative rewards system. 
         [0011]    Each item&#39;s trip from a starting node to a destination node is monitored. An item may travel from a starting node along a link to another node where it is transferred to another link, by which it travels to another node where it is transferred to another link, and so on, until the item has arrived at its destination node. Referring to  FIG. 1 , a network  100  is illustrated. The network is comprised of nodes  101  and links  102  connecting the nodes. A plurality of possible routes between a given starting node and a given destination node may exist. The proposed method is concerned with the problem of choosing the most efficient route from a given starting node to a given destination node. 
         [0012]    Referring to  FIG. 2 , another network  200  is illustrated. If an item with starting node  201  has a destination node of  209 , there is more than one route the item may take to arrive at the destination. The item may take the route: node  202 , node  206 , node  205 , node  211 , node  214 , node  212 , node  208 , node  209 . This route contains seven nodes before the destination is reached. An alternative route is: node  202 , node  206 , node  207 , node  213 , node  210 , node  209 . This route contains five nodes before the destination is reached. Although the first route contains more nodes than the second route, which can cause a route to take longer, the second route may take longer than the first route because the total distance between nodes is greater. Another alternative route is node  202 , node  203 , node  204 , node  207 , node  213 , node  210 , node  209 . This route contains six nodes before the destination is reached. Although this route contains more nodes than the second route, it may be advantageous in the event that there is a lot of traffic at node  206 . Because it follows a different path than the other two routes, it may serve as an efficient route under certain circumstances. 
         [0013]    The efficiency of the particular route used may be evaluated by looking at each segment of the trip between nodes. A small negative reward is assigned at the end of each segment of a trip based on the amount of delay (if any) incurred during the segment. So, referring to the example in  FIG. 2 , the routes with more nodes will result in more opportunities for delays and therefore penalties. However the delay within each segment of the trip is also accounted for. The system is configured to maximize rewards at all times, so it attempts to select the route with the smallest likelihood of delay. A large positive reward is assigned at the end of each complete trip to incentivize the system to continue trips in spite of the negative rewards incurred after each segment. The following formula may be used to calculate rewards for trip segments: 
         [0014]    [W(estimated)−W (actual)]R=reward 
         [0015]    where 
         [0016]    W (estimated) is the amount of time to complete the segment with no delays; 
         [0017]    W (actual) is the amount of time it actually took to complete the segment; and 
         [0018]    R is a predetermined reward rate. 
         [0019]    The reward rate is negative, so that greater penalties are assigned as the deviation from the estimated segment time (amount of time to complete the segment with no delays) increases. 
         [0020]    As stated previously, the system is configured to attempt to maximize rewards at all times, so that it always attempts to find the route with the shortest trip time. This may be represented by: 
         [0021]    W(estimated)−W (actual)=Deviation 
         [0000]    
       
         
           
             
               ArgMin 
               D 
             
              
             
               [ 
               
                 
                   W 
                    
                   
                     ( 
                     estimated 
                     ) 
                   
                 
                 - 
                 
                   W 
                    
                   
                     ( 
                     actual 
                     ) 
                   
                 
               
               ] 
             
           
         
       
     
         [0022]    The greater the deviation from the estimated trip time, the larger the penalty. Deviation from the ideal trip time may occur for a variety of reasons, such as traffic within the network and waiting in queues. 
         [0023]    The reward of each state may be represented by: 
         [0000]        R   (s) = R   (ts)    
         [0024]    The reward after he transition from state (s) to (s′) may be represented by: 
         [0000]    
       
      
       R 
       (s′) 
       =R 
       (ts) 
       +R 
       (ts+1)  
      
     
         [0025]    The total reward for work in the session can be represented by the following formula: 
         [0000]        R   (t0)   +R   (t1)   +R   (t2)   +R   (t3)   + . . . +R   (tn) =Total reward 
         [0026]    The system is configured to attempt to maximize this value at all times, which is represented by the formula: 
         [0000]        E[ΣR   t ]→Max
 
         [0027]    Where E is the expectation that R (reward) is maximized. 
         [0028]    Therefore, the value of state (s) when policy (π) is executed equals the expected sum of all future rewards provided that initial state (s 0 ) is (s) and policy (n) is executed as represented by the formula: 
         [0000]    
       
         
           
             
               
                 π 
                 
                   ( 
                   s 
                   ) 
                 
               
                
               
                   
               
                
             
             = 
             
               E 
                
               
                   
               
                
               
                 
                   π 
                   i 
                 
                  
                 
                   [ 
                   
                     
                       
                         ∑ 
                         
                           R 
                           t 
                         
                       
                       | 
                       
                         s 
                         0 
                       
                     
                     = 
                     s 
                   
                   ] 
                 
               
             
           
         
       
     
         [0029]    Each time a trip is completed, the system records the corresponding net rewards earned in a table. After completing a number of trips, the system may use the data to determine which routes produce the highest rewards. 
         [0030]    From the above, the value iteration may be concluded: 
         [0000]        V   (s) =[max as′   ΣP ( s|s,a ) V   (s′)   ]R   (s)    
         [0031]    Where: 
         [0032]    max a =maximizing action 
         [0033]    V (s′) =value of successor 
         [0034]    R (s) =reward or cost to get to state s 
         [0035]    P=state transition function 
         [0036]    R=reward function 
         [0037]    The above formula is found after convergence according to Bellman&#39;s equation represented by the formula: 
         [0000]    
       
         
           
             max 
              
             
               
                 ∑ 
                 
                   t 
                   = 
                   0 
                 
                 ∞ 
               
                
               
                 
                   β 
                   i 
                 
                  
                 
                   μ 
                    
                   
                     ( 
                     
                       c 
                       t 
                     
                     ) 
                   
                 
                  
                 
                     
                 
                  
                 subject 
                  
                 
                     
                 
                  
                 to 
               
             
           
         
       
       
         
           
             
               
                 a 
                 
                   t 
                   + 
                   1 
                 
               
               = 
               
                 
                   
                     ( 
                     
                       1 
                       + 
                       r 
                     
                     ) 
                   
                    
                   
                     
                       ( 
                       
                         
                           a 
                           t 
                         
                         - 
                         
                           c 
                           t 
                         
                       
                       ) 
                     
                     · 
                     
                       c 
                       t 
                     
                   
                 
                 ≥ 
                 0 
               
             
             , 
             and 
           
         
       
       
         
           
             
               
                 
                   limit 
                   
                     t 
                     = 
                     ∞ 
                   
                 
                  
                 
                     
                 
                  
                 
                   a 
                   t 
                 
               
               ≥ 
               0 
             
             , 
             
               
                 and 
                  
                 
                   
 
                 
                  
                 
                   ( 
                   a 
                   ) 
                 
               
               = 
               
                 
                   max 
                   
                     0 
                     ≤ 
                     c 
                     ≤ 
                     a 
                   
                 
                  
                 
                   { 
                   
                     
                       
                         μ 
                          
                         
                           ( 
                           c 
                           ) 
                         
                       
                       + 
                       β 
                     
                      
                     
                       ( 
                       
                         
                           ( 
                           
                             1 
                             + 
                             r 
                           
                           ) 
                         
                          
                         
                           ( 
                           
                             a 
                             - 
                             c 
                           
                           ) 
                         
                       
                       ) 
                     
                   
                   } 
                 
               
             
           
         
       
     
         [0038]    The value of a given state depends on the outcome of the prior state multiplied by the cost (penalty incurred) to get there. The system can then compare values of routes used and determine which routes for items traveling from a particular starting node to a particular destination node have the highest value. As the system completes more and more trips, more and more data is gathered, and values are assigned to each state. That is, a value is assigned to each route for delivering an item from a starting node to a destination node. Once values have been assigned to the routes, the system can calculate a policy to maximize rewards. The system develops a policy, π, which defines the best route yet discovered. This is represented by the formula: 
         [0000]    
       
         
           
             
               π 
                
               
                 ( 
                 s 
                 ) 
               
             
             = 
             
               
                 
                   argmax 
                   
                     s 
                     ′ 
                   
                 
                  
                 
                   ∑ 
                   
                     P 
                      
                     
                       ( 
                       
                         
                           s 
                           ′ 
                         
                         | 
                         
                           
                             s 
                             1 
                           
                            
                           a 
                         
                       
                       ) 
                     
                   
                 
               
                
               
                 ( 
                 
                   s 
                   ′ 
                 
                 ) 
               
             
           
         
       
     
         [0039]    From value iteration methods one may find policy 1, which is a better policy than policy 0, and then find a policy 2, which is a better than policy 1, and so on. The above formula therefore finds the best eventual policy. 
         [0040]    P a (s, s′)=Pr (s t+1 =s′|s t =s, a t =a) is the probability that action a in a state s at time t will lead to state s′ at time t+1 
         [0041]    and 
         [0042]    R a  (s, s′) is the immediate reward received after transition to state s′ from s. 
         [0043]    A desirable outcome is to choose a policy, π, that will maximize the expected discounted sum of the rewards collected at any given S. The system uses the policy, π, to route items in the best known manner. 
         [0044]    S (state) here refers to each possible trip segment of a route. A finite number of segments are possible, thus there are a finite set of states. A is the action of selecting a route, which takes the system from state S to state S′. A s  is the finite set of possible routes defined from any state. T is the time interval between each state transition of S to S′. 
         [0045]    The proposed routing method may be used in any application without limitation. For example, the routing method may be used to route packages through a pneumatic tube network, route trains through a rail network, or route baggage through a conveyor belt network.