System for efficient scheduling for multiple automated non-holonomic vehicles using a coordinated path planner
First Claim
1. A system for coordinated path planning in a multivehicle warehouse environment, the system comprising a plurality of automated vehicles for moving a product around the multivehicle warehouse and one or more central processing units, wherein:
- each automated vehicle of the plurality of automated vehicles comprises a memory comprising a navigation module; and
the one or more central processing units are communicatively coupled to the plurality of automated vehicles and execute instructions to;
receive an executable task in the multivehicle warehouse for one or more of the plurality of automated vehicles,select a coordinated path plan for a number of the plurality of automated vehicles for which the executable task has been received, wherein the coordinated path plan is selected with the one or more central processing units from a solution set of roadmap graphs from a multi-level graph, the multi-level graph comprising a plurality of graph levels with respect to a floor portion of the multivehicle warehouse, the plurality of graph levels comprising at least a higher level graph of the floor portion and a lower level graph of the floor portion, the higher level graph comprising a plurality of high-level nodes, the lower level graph comprising a plurality of lower-level nodes, each lower-level node disposed in a position within or on a boundary of a respective high-level node of the plurality of high-level nodes, each lower-level node comprising a smaller surface area than the respective high-level node with respect to the floor portion, and the solution set of roadmap graphs comprising one or more unique combinations of lower-level nodes and high-level nodes and path segments connection various ones of the lower-level nodes and the high-level nodes,communicate at least a portion of the coordinated path plan to the number of the plurality of automated vehicles for which the executable task has been received such that respective navigation modules of the number of the plurality of automated vehicles navigate a respective automated vehicle, according to the received portion of the coordinated path plan,receive an up-coming executable task in the multivehicle warehouse for one or more of the plurality of automated vehicles,use the up-coming executable task to forecast a revised coordinated path plan for the number of the plurality of automated vehicles operating according to the received portion of the coordinated path plan, andcommunicate at least a portion of the revised coordinated path plan to the number of the plurality of automated vehicles for which the up-coming executable task has been received such that, upon receipt of instructions to execute the up-coming executable task, respective navigation modules of the number of the plurality of automated vehicles navigate the respective automated vehicle, according to the received portion of the revised coordinated path plan.
1 Assignment
0 Petitions
Accused Products
Abstract
A method for coordinating path planning for one or more automated vehicles is described, including querying an online path planner for possible solutions for at least one executable task for each of the one or more automated vehicles, examining the results of the query, deciding a coordinated path plan for each vehicle, and communicating the coordinated path plan to a traffic manager, wherein the traffic manager ensures that the one or more automated vehicles perform each executable task according to the coordinated path plan.
264 Citations
19 Claims
-
1. A system for coordinated path planning in a multivehicle warehouse environment, the system comprising a plurality of automated vehicles for moving a product around the multivehicle warehouse and one or more central processing units, wherein:
-
each automated vehicle of the plurality of automated vehicles comprises a memory comprising a navigation module; and the one or more central processing units are communicatively coupled to the plurality of automated vehicles and execute instructions to; receive an executable task in the multivehicle warehouse for one or more of the plurality of automated vehicles, select a coordinated path plan for a number of the plurality of automated vehicles for which the executable task has been received, wherein the coordinated path plan is selected with the one or more central processing units from a solution set of roadmap graphs from a multi-level graph, the multi-level graph comprising a plurality of graph levels with respect to a floor portion of the multivehicle warehouse, the plurality of graph levels comprising at least a higher level graph of the floor portion and a lower level graph of the floor portion, the higher level graph comprising a plurality of high-level nodes, the lower level graph comprising a plurality of lower-level nodes, each lower-level node disposed in a position within or on a boundary of a respective high-level node of the plurality of high-level nodes, each lower-level node comprising a smaller surface area than the respective high-level node with respect to the floor portion, and the solution set of roadmap graphs comprising one or more unique combinations of lower-level nodes and high-level nodes and path segments connection various ones of the lower-level nodes and the high-level nodes, communicate at least a portion of the coordinated path plan to the number of the plurality of automated vehicles for which the executable task has been received such that respective navigation modules of the number of the plurality of automated vehicles navigate a respective automated vehicle, according to the received portion of the coordinated path plan, receive an up-coming executable task in the multivehicle warehouse for one or more of the plurality of automated vehicles, use the up-coming executable task to forecast a revised coordinated path plan for the number of the plurality of automated vehicles operating according to the received portion of the coordinated path plan, and communicate at least a portion of the revised coordinated path plan to the number of the plurality of automated vehicles for which the up-coming executable task has been received such that, upon receipt of instructions to execute the up-coming executable task, respective navigation modules of the number of the plurality of automated vehicles navigate the respective automated vehicle, according to the received portion of the revised coordinated path plan. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A system for coordinated path planning in a multivehicle warehouse environment, the system comprising a plurality of automated vehicles for moving a product around the multivehicle warehouse and one or more central processing units, wherein:
-
each automated vehicle comprises a memory comprising a navigation module; and the one or more central processing units are communicatively coupled to the plurality of automated vehicles and execute instructions to; receive executable tasks in the multivehicle warehouse for one or more of the plurality of automated vehicles, select a coordinated path plan for a number of the plurality of automated vehicles for which executable tasks have been received, wherein the coordinated path plan is selected with the one or more central processing units from a solution set of roadmap graphs from a multi-level graph, the multi-level graph comprising a plurality of graph levels with respect to a floor portion of the multivehicle warehouse, the plurality of graph levels comprising at least a higher level graph of the floor portion and a lower level graph of the floor portion, the higher level graph comprising a plurality of high-level nodes, the lower level graph comprising a plurality of lower-level nodes, each lower-level node disposed in a position within or on a boundary of a respective high-level node of the plurality of high-level nodes, each lower-level node comprising a smaller surface area than the respective high-level node with respect to the floor portion, and the solution set of roadmap graphs comprising one or more unique combinations of lower-level nodes and high-level nodes and path segments connection various ones of the lower-level nodes and the high-level nodes, construct, with the one or more central processing units, a grid associated with the multivehicle warehouse, wherein the grid demarcates a plurality of grid squares, and respective grid squares contain a portion of the multivehicle warehouse and a portion of the corresponding multi-level graph; select from the plurality of grid squares, with the one or more central processing units, grid squares corresponding to a start position, a goal position, or both, if the start position, the goal position, or both, are within the multivehicle warehouse but off the multi-level graph; determine within one or more of the selected grid squares, with the one or more central processing units, joining paths from the start position, the goal position, or both, to the multi-level graph, wherein each of the roadmap graphs comprises the start position linked via a final path to the goal position, the final path comprises a determined joining path and at least a portion of the local paths, and the coordinated path plan for the automated vehicles is selected from the solution set of roadmap graphs; communicate at least a portion of the coordinated path plan to the number of the plurality of automated vehicles for which executable tasks have been received such that respective navigation modules of the number of the plurality of automated vehicles navigate a respective automated vehicle, according to the received portion of the coordinated path plan, receive up-coming executable tasks in the multivehicle warehouse for one or more of the plurality of automated vehicles, use the up-coming executable tasks to forecast a revised coordinated path plan for the number of the plurality of automated vehicles operating according to the received portion of the coordinated path plan, and communicate at least a portion of the revised coordinated path plan to the number of the plurality of automated vehicles for which up-coming executable tasks have been received such that, upon receipt of instructions to execute up-coming executable tasks, respective navigation modules of the number of the plurality of automated vehicles navigate the respective automated vehicle, according to the received portion of the revised coordinated path plan.
-
Specification