Method and apparatus for efficient scheduling for multiple automated non-holonomic vehicles using a coordinated path planner

• US 9,188,982 B2
• Filed: 04/10/2012
• Issued: 11/17/2015
• Est. Priority Date: 04/11/2011
• Status: Active Grant

• Current Assignee: Crown Equipment Corporation
• Original Assignee: Crown Equipment Corporation
• Inventors: Thomson, Jacob Jay
• Primary Examiner(s): Olszewski, John R
• Assistant Examiner(s): WHITTINGTON, JESS G
• Application Number:
  US14/110,950
• Publication Number:
  US 20140032035A1
• Time in Patent Office: 1,316 Days
• Field of Search: None
• 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 receiving an executable task for an automated vehicle, providing a multi-level graph comprising high-level nodes, connection nodes, roadmap nodes, and one or more local paths, constructing a grid corresponding with the multi-level graph, selecting grid squares corresponding to a start position, a goal position, or both if they are off the multi-level graph, determining joining paths from the start position, goal position, or both to the multi-level graph, constructing a solution set of roadmap graphs from the multi-level graph, selecting a coordinate path plan, communicating at least a portion of the coordinate path plan to each automated vehicle, and controlling the automated vehicle in accordance with the coordinate path plan.

Claims

1. A method for coordinating path planning for a plurality of automated vehicles, the method comprising:

receiving, through a network and with one or more central processing units, an executable task in an industrial environment for one of the plurality of automated vehicles wherein respective automated vehicles comprise a navigation module, a steering component, and a motion component, and the central processing units are communicatively coupled to the plurality of automated vehicles through the network;

providing a multi-level graph comprising high-level nodes, wherein respective high level nodes correspond to a region of the industrial environment, each of the high-level nodes 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;

constructing, with the central processing units, a grid associated with the industrial environment, wherein the grid demarcates a plurality grid squares and respective grid squares contain a portion of the industrial environment and a portion of the corresponding multi-level graph;

selecting from the plurality of grid squares, with the 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 industrial environment but off the multi-level graph;

determining within respective ones of the selected grid squares, with the central processing units, joining paths from the start position, the goal position, or both, to the multi-level graph;

constructing, with the central processing units, a solution set of roadmap graphs from the multi-level graph, wherein each of the roadmap graphs comprises the start position linked via a final path to the goal position, and wherein the final path comprises a determined joining path and at least a portion of the local paths;

selecting, with the central processing units, a coordinated path plan for the automated vehicles from the solution set of roadmap graphs; and

communicating, through the network, at least a portion of the coordinated path plan to each automated vehicle wherein the navigation module of each of the automated vehicle operates the steering component, the motion component, or both according to the coordinated path plan.

2. The method of claim 1, further comprising removing at least a portion of the roadmap graphs from the solution set of roadmap graphs based at least in part upon the heuristic of each of the portion of the roadmap graphs.

3. The method of claim 1, further comprising constraining 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.

4. The method of claim 3, wherein the number of the automated vehicles permitted within each of the high-level nodes is two or less.

5. The method of claim 1, further comprising:

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

resuming 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.

6. The method of claim 1, further comprising:

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

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

7. The method of claim 1, further comprising forming a modified-Dubins path comprising joining paths at ends of the modified-Dubins 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 wherein the one or more local paths of one of the roadmap graphs comprises the modified-Dubins path.

8. The method of claim 1, wherein the joining path does not intersect with the start position and the goal position of each of the roadmap graphs for another automated vehicle.

9. The method of claim 1, 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.

10. The method of claim 1, wherein the heuristic is indicative of travel time.

11. The method of claim 1, wherein the heuristic is indicative of cost associated with start-up of an idled vehicle of the automated vehicles.

12. The method of claim 1, wherein the heuristic is indicative of the high-level nodes, the connection nodes, and roadmap nodes that are unavailable.

13. The method of claim 1, wherein the automated vehicles are non-holonomic.

14. The method of claim 1, further comprising identifying, with the central processing units, 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 industrial environment and on the multi-level graph.

15. The method of claim 1, further comprising associating, with the central processing units, a heuristic with each of the roadmap graphs, wherein the heuristic is indicative of the final path of its associated roadmap graph, wherein the coordinated path plan is selected based at least in part upon the heuristic.

16. A system for coordinating path planning in a warehouse, the system comprising:

a plurality of automated vehicles located within the warehouse, each of the automated vehicles comprising a navigation module in communication with a steering component and a motion component; and

one or more central processing units in communication with each of the automated vehicles, wherein the one or more central processing units execute instructions to;

receive an executable task for one of the plurality of automated vehicles;

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

construct a grid associated with the warehouse, wherein the grid demarcates a plurality grid squares and respective grid squares contain a portion of the warehouse and a portion of the corresponding multi-level graph;

select from the plurality of grid squares, grid squares corresponding to a start position, a goal position, or both, if the start position, the goal position, or both are within the warehouse but off the multi-level graph;

determine within respective ones of the selected grid squares, joining paths from the start position, the goal position, or both, to the multi-level graph;

construct a solution set of roadmap graphs from the multi-level graph, wherein each of the roadmap graphs comprises the start position linked via a final path to the goal position, and wherein the final path comprises a determined joining path and at least a portion of the local paths;

select a coordinated path plan for the automated vehicles from the solution set of roadmap graphs; and

communicate at least a portion of the coordinated path plan to each of the automated vehicles, wherein the navigation module of each of the automated vehicles controls the steering component, the motion component, or both according to the coordinated path plan.

17. The system of claim 16, wherein the one or more central processing units execute the 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 of the warehouse corresponding the blocked nodes.

18. The system of claim 16, wherein the one or more central processing units execute the instructions to form a modified-Dubins path comprising joining paths at ends of the modified-Dubins 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 wherein the one or more local paths of one of the roadmap graphs comprises the modified-Dubins path.

19. The system of claim 16, wherein the joining path does not intersect with the start position and the goal position of each of the roadmap graphs for another automated vehicle.

20. The system of claim 16, wherein the coordinated path plan requires one of the automated vehicles to wait until another of the automated vehicles passes a specific location.

21. A method for coordinating path planning for a plurality of automated forklifts, wherein the automated forklifts are located within a warehouse and in communication with one or more central processing units, and wherein the method comprises:

receiving, with the central processing units, an executable task in an industrial environment for one of the plurality of automated forklifts wherein respective automated forklifts comprise a navigation module, a steering component, and a motion component;

providing a multi-level graph comprising high-level nodes, wherein respective high level nodes correspond to a region of the warehouse, each of the high-level nodes comprises one or more connection nodes corresponding to a boundary of the region of the warehouse, one or more roadmap nodes corresponding to an interior of the region of the warehouse, and one or more local paths that link the connection nodes, the roadmap nodes, or a combination thereof;

constructing, with the central processing units, a grid associated with the warehouse, wherein the grid demarcates a plurality grid squares and respective grid squares contain a portion of the warehouse and a portion of the corresponding multi-level graph;

selecting from the plurality of grid squares, with the 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 warehouse but off the multi-level graph;

determining within respective ones of the selected grid squares, with the central processing units, joining paths from the start position, the goal position, or both to the multi-level graph;

constructing, with the central processing units, a solution set of roadmap graphs from the multi-level graph, wherein each of the roadmap graphs comprises the start position linked via a final path to the goal position, and wherein the final path comprises a determined joining path and at least a portion of the local paths;

selecting, with one or more central processing units, a coordinated path plan for the automated forklifts from the solution set of roadmap graphs; and

communicating, through the network, at least a portion of the coordinated path plan to each automated forklift wherein the navigation module of each of the automated forklift controls the steering component, the motion component, or both according to the coordinated path plan.