Vehicle dispatching method and system

Abstract

A method for dispatching a plurality of vehicles operating in a work area among a plurality of destination locations and a plurality of source locations includes implementing linear programming that takes in an optimization function and constraints to generate an optimum schedule for optimum production, utilizing a reinforcement learning algorithm that takes in the schedule as input and cycles through possible environmental states that could occur within the schedule by choosing one possible action for each possible environmental state and by observing the reward obtained by taking the action at each possible environmental state, developing a policy for each possible environmental state, and providing instructions to follow an action associated with the policy.

What is claimed is: 
     
         1 . A method for dispatching a plurality of vehicles operating in a work area among a plurality of destination locations and a plurality of source locations comprising:
 implementing linear programming that takes in an optimization function and constraints to generate an optimum schedule for optimum production, the optimum schedule defining the number of trips taken along paths between the destination locations and the source locations to achieve the optimum production;   
       utilizing a reinforcement learning algorithm that takes in the optimum schedule as input and cycles through possible environmental states that could occur within the optimum schedule by choosing one possible action for each possible environmental state and by assigning a reward value obtained by taking the action at each possible environmental state; 
       developing a policy for each possible environmental state based on at least the reward value and time, the policy being associated with a preferred action; 
       associating a state in the work area with one of the possible environmental states and accessing the preferred action associated with the policy for the associated possible environmental state; and 
       providing instructions to follow the preferred action. 
     
     
         2 . The method of  claim 1 , wherein the developing a policy is further based on at least one of a subsequent possible environmental state, a subsequent action, elapsed time in the cycle through the possible environmental states. 
     
     
         3 . The method of  claim 1 , wherein the optimization function maximizes the amount of material hauled. 
     
     
         4 . The method of  claim 1 , wherein the constraints comprise two or more of the number of vehicles operating in the work area, velocity of one or more vehicles, material constraints and time limitations. 
     
     
         5 . The method of  claim 4 , wherein the constraints do not include fixed time intervals. 
     
     
         6 . The method of  claim 1 , wherein disturbances are added to the reinforcement learning. 
     
     
         7 . The method of  claim 6 , wherein the disturbances simulate entropy in the schedule. 
     
     
         8 . The method of  claim 7 , wherein the entropy includes vehicle breakdown, road closures, obstacles or path detours. 
     
     
         9 . The method of  claim 1 , further comprising applying function approximation to the number of possible environmental states. 
     
     
         10 . The method of  claim 1 , wherein the reinforcement learning algorithm is a Monte Carlo reinforcement learning method. 
     
     
         11 . The method of  claim 1 , wherein the reinforcement learning algorithm comprises a reinforcement technique such as Q learning or temporal difference learning including SARSA 
     
     
         12 . The method of  claim 1 , further comprising causing the plurality of vehicles to comply with the instructions to pursue the preferred action. 
     
     
         13 . The method of  claim 1 , wherein the work area is a dynamic work area.