METHOD AND APPARATUS FOR EFFICIENT SCHEDULING FOR MULTIPLE AUTOMATED NON-HOLONOMIC VEHICLES USING A COORDINATED PATH PLANNER

• US 20140032035A1
• Filed: 04/10/2012
• Published: 01/30/2014
• 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,188,982 B2
• Time in Patent Office: Days
• US Class Current: 701/25
• 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
• CPC Class Codes: G05D 2201/0216 Vehicle for transporting goods in a warehouse, factory or similar

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-16. -16. (canceled)

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

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

constructing, offline, a solution set of roadmap graphs from the multi-level graph, wherein each of the roadmap graphs comprises a start position within one of the high-level nodes linked via a final path to a goal position of another of the high-level nodes, and wherein the final path comprises a portion of the local paths of the high-level nodes;

associating a heuristic with each of the roadmap graphs, wherein the heuristic is indicative of the final path of its associated roadmap graph;

selecting, online and automatically with one or more central processing units, a coordinated path plan for the automated vehicles from the solution set of roadmap graphs, wherein the coordinated path plan is selected based at least in part upon the heuristic; and

operating the automated vehicles according to the coordinated path plan.

18. The method of claim 17, 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.

19. The method of claim 17, further comprising constraining a number of the automated vehicles permitted within each of the high-level nodes.

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

21. The method of claim 17, 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.

22. The method of claim 17, further comprising:

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

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

23. The method of claim 17, 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.

24. The method of claim 17, further comprising:

constructing, offline, a grid associated with the multi-level graph, wherein the grid demarcates a plurality of areas that each corresponds to a portion of the local paths, the connection nodes, and the local nodes;

selecting a current area of one of the automated vehicles from the plurality of areas, wherein the current area is indicative of a location of the one of the automated vehicles; and

determining, online and automatically with the one or more central processing units, a joining path from the location to a member of the portion of the local paths, the connection nodes, and the local nodes corresponding to the current area.

25. The method of claim 24, wherein the joining path does not intersect with the start position and the goal position of each of the roadmap graphs.

26. The method of claim 17, 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.

27. The method of claim 17, wherein the heuristic is indicative of travel time.

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

29. The method of claim 17, wherein the heuristic is indicative of the high-level nodes, the connection nodes, and local nodes that are unavailable.

30. The method of claim 17, wherein the automated vehicles are non-holonomic.

31. 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 or 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;

access a multi-level graph comprising high-level nodes each corresponding to a region of the warehouse, wherein 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 local nodes corresponding to an interior of the region of the warehouse, and one or more local paths that link the connection nodes, the local nodes, or a combination thereof;

construct, offline, a solution set of roadmap graphs from the multi-level graph, wherein each of the roadmap graphs comprises a start position within one of the high-level nodes linked via a final path to a goal position of another of the high-level nodes, and wherein the final path comprises a portion of the local paths of the high-level nodes;

associate a heuristic with each of the roadmap graphs, wherein the heuristic is indicative of the final path of its associated roadmap graph;

select, online, a coordinated path plan for the automated vehicles from the solution set of roadmap graphs, wherein the coordinated path plan is selected based at least in part upon the heuristic; 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 of controls the steering component, the motion component, or both according to the coordinated path plan.

32. The system of claim 31, 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 local nodes that are unavailable; and

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

33. The system of claim 31, 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.

34. The system of claim 31, wherein the one or more central processing units execute the instructions to:

construct, offline, a grid associated with the multi-level graph, wherein the grid demarcates a plurality of areas of the warehouse that each corresponds to a portion of the local paths, the connection nodes, and the local nodes;

select a current area of one of the automated vehicles from the plurality of areas, wherein the current area is indicative of a location within the warehouse of the one of the automated vehicles; and

determine, online, a joining path from the location to a member of the portion of the local paths, the connection nodes, and the local nodes corresponding to the current area.

35. The system of claim 34, wherein the joining path does not intersect with the start position and the goal position of each of the roadmap graphs.

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

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

providing a multi-level graph comprising high-level nodes corresponding to a region of the warehouse, wherein 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 local nodes corresponding to an interior of the region of the warehouse, and one or more local paths that link the connection nodes, the local nodes, or a combination thereof;

constructing, offline, a solution set of roadmap graphs from the multi-level graph, wherein each of the roadmap graphs comprises a start position within one of the high-level nodes linked via a final path to a goal position of another of the high-level nodes, and wherein the final path comprises a portion of the local paths of the high-level nodes, and wherein the final path corresponds to a route within the warehouse;

associating a heuristic with each of the roadmap graphs, wherein the heuristic is indicative of the final path of its associated roadmap graph;

selecting, online and automatically with the one or more central processing units, a coordinated path plan for the automated vehicles from the solution set of roadmap graphs, wherein the coordinated path plan is selected based at least in part upon the heuristic; and

operating the automated vehicles within the warehouse according to the coordinated path plan.