SYSTEM FOR EFFICIENT SCHEDULING FOR MULTIPLE AUTOMATED NON-HOLONOMIC VEHICLES USING A COORDINATED PATH PLANNER

• US 20160033971A1
• Filed: 10/13/2015
• Published: 02/04/2016
• Est. Priority Date: 04/11/2011
• Status: Active Grant

• Current Assignee: Crown Equipment Corporation
• Original Assignee: Crown Equipment Corporation
• Inventors: Thomson, Jacob Jay
• Granted Patent: US 9,958,873 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G05D 1/0212 with means for defining a desired trajectory involving a plurality of land vehicles G05D1/0287
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0289 with means for avoiding collisions between vehicles vehicle fittings for automatically controlling speed including means for detecting potential obstacles B60K31/0008; avoiding obstacles by action on the steering system B62D; radar, sonar, lidar systems designed for anti-collision purposes G01S13/93, G01S15/93, G01S17/93
• CPC Class Codes: G05D 1/0291 Fleet control monitoring fleets in traffic control systems for road vehicles G08G1/127, G08G1/127
• CPC Class Codes: G05D 1/0297 by controlling means in a control room

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.

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 comprises a navigation module, a steering component, and a motion component; and

the central processing unit(s) 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 automated vehicles,

select a coordinated path plan for the automated vehicles for which the executable task has been received,

communicate at least a portion of the coordinated path plan to the automated vehicles for which the executable task has been received such that respective navigation modules of the automated vehicles operate the steering component of the automated vehicle, the motion component of the automated vehicle, or both, 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 automated vehicles,

use the up-coming executable task to forecast a revised coordinated path plan for the 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 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 automated vehicles operate the steering component of the automated vehicle, the motion component of the automated vehicle, or both, according to the received portion of the revised coordinated path plan.

2. The system as claimed in claim 1 wherein the central processing unit(s) execute instructions to monitor the plurality of automated vehicles to ensure they are performing each executable task according to the coordinated path plan or the revised coordinated path plan.

3. The system as claimed in claim 1 wherein the central processing unit(s) are communicatively coupled to the plurality of vehicles through a network.

4. The system as claimed in claim 1 wherein the central processing unit(s) execute instructions to:

access a multi-level graph corresponding to the multivehicle warehouse wherein the multi-level graph comprises one or more regions and one or more high level nodes, each high level node corresponds to a region and comprises one or more connection nodes corresponding to a boundary of the region, one or more roadmap nodes corresponding to an interior of the region, and one or more local paths that link the connection nodes, the roadmap nodes, or a combination thereof; and

construct a solution set of roadmap graphs from the multi-level graph, wherein each of the roadmap graphs comprises a start position linked via a final path to a 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.

5. The system as claimed in claim 4 wherein the central processing unit(s) execute instructions to:

generate a list of blocked nodes corresponding to the high-level nodes, the connection nodes, and roadmap nodes that are unavailable; and

stop the automated vehicles from navigating a part of the region corresponding the blocked nodes.

6. The system as claimed in claim 4 wherein the central processing unit(s) execute instructions to constrain a number of the automated vehicles permitted within each of the high-level nodes to reduce the time needed to construct a solution set of roadmap graphs.

7. The system as claimed in claim 4 wherein the number of the automated vehicles permitted within each of the high-level nodes is two or less.

8. The system as claimed in claim 4 wherein the central processing unit(s) execute instructions to:

stop operation of the automated vehicles at a predetermined time; and

resume operation of the automated vehicles after a period of time has elapsed after the predetermined time, wherein the coordinated path plan is selected during the period of time.

9. The system as claimed in claim 4 wherein the central processing unit(s) execute instructions to form a modified-Dubins path comprising joining paths at ends of the modified-Dubins paths and a continuous change in curvature path located between the joining paths, wherein the modified-Dubins path comprises sharper turns than the continuous change in curvature path, and the one or more local paths of one of the roadmap graphs comprises the modified-Dubins path.

10. The system as claimed in claim 4 wherein the determined joining path does not intersect with the start position and the goal position of each of the roadmap graphs for another automated vehicle.

11. The system as claimed in claim 4 wherein the coordinated path plan requires one of the automated vehicles to wait until another of the one or more automated vehicles passes a specific location.

12. The system as claimed in claim 4 wherein the central processing unit(s) execute instructions to remove at least a portion of the roadmap graphs from the solution set of roadmap graphs based at least in part upon a heuristic of each removed portion of the roadmap graphs.

13. The system as claimed in claim 12 wherein the heuristic is indicative of travel time.

14. The system as claimed in claim 12 wherein the heuristic is indicative of cost associated with start-up of an idled vehicle of the automated vehicles.

15. The system as claimed in claim 12 wherein the heuristic is indicative of the high-level nodes, the connection nodes, and roadmap nodes that are unavailable.

16. The system as claimed in claim 4 wherein the central processing unit(s) execute instructions to identify respective connection nodes, roadmap nodes, or local paths which correspond to the start position, the goal position, or both, if the start position, the goal position, or both are within the multivehicle warehouse and on the multi-level graph.

17. The system as claimed in claim 1 wherein the automated vehicles are non-holonomic.

18. 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 navigation module, a steering component, and a motion component; and

the central processing unit(s) 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 automated vehicles,

select a coordinated path plan for the automated vehicles for which executable tasks have been received,

communicate at least a portion of the coordinated path plan to the automated vehicles for which executable tasks have been received such that respective navigation modules of the automated vehicles operate the steering component of the automated vehicle, the motion component of the automated vehicle, or both, 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 automated vehicles,

use the up-coming executable tasks to forecast a revised coordinated path plan for the 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 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 automated vehicles operate the steering component of the automated vehicle, the motion component of the automated vehicle, or both, according to the received portion of the revised coordinated path plan.