Method and apparatus for efficient scheduling for multiple automated non-holonomic vehicles using a coordinated path planner
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G05D-001/00
G05D-001/02
출원번호
US-0110950
(2012-04-10)
등록번호
US-9188982
(2015-11-17)
국제출원번호
PCT/NZ2012/000051
(2012-04-10)
§371/§102 date
20131010
(20131010)
국제공개번호
WO2012/141601
(2012-10-18)
발명자
/ 주소
Thomson, Jacob Jay
출원인 / 주소
Crown Equipment Limited
대리인 / 주소
Dinsmore & Shohl LLP
인용정보
피인용 횟수 :
5인용 특허 :
84
초록▼
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 corre
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.
대표청구항▼
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 autom
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; andcommunicating, 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; andresuming 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; andstopping 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; andone 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; andcommunicate 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; andstop 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; andcommunicating, 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.
Trepagnier, Paul Gerard; Nagel, Jorge Emilio; Dooner, Matthew Taylor; Dewenter, Michael Thomas; Traft, Neil Michael; Drakunov, Sergey; Kinney, Powell; Lee, Aaron, Control and systems for autonomously driven vehicles.
Trepagnier, Paul Gerard; Nagel, Jorge Emilio; Dooner, Matthew Taylor; Dewenter, Michael Thomas; Traft, Neil Michael; Drakunov, Sergey; Kinney, Powell; Lee, Aaron, Control and systems for autonomously driven vehicles.
Andersen Eric T. (Rte. 1 ; Box 138A Barboursville VA 22923) Andersen Edward A. (Rte. 1 ; Box 138A Barboursville VA 22923), Height indicator for a fork lift truck.
Gaibler Dennis W. (Gresham OR) Skinner Jeffrey R. (Camas WA) Edwards Alan T. (Portland OR), Load-lifting mast especially adapted for use with automatically-guided vehicles.
Gorr Russell E. ; Hancock Thomas R. ; Judd J. Stephen ; Lin Long-Ji ; Novak Carol L. ; Rickard ; Jr. Scott T., Method and apparatus for automatically tracking the location of vehicles.
Bell, Jamie; Chandrasekar, Kashyap; Graham, Andres Evan; Howse, David Charles, Method and apparatus for sensing object load engagement, transportation and disengagement by automated vehicles.
Jascob, Bradley A.; Shaver, Scott; Martens, Todd; Yared, Nadim; Boes, Kirsten; Dukesherer, John H.; Hunter, Mark W., Method and apparatus for surgical navigation.
Alofs Cornell W. ; Drenth Ronald R. ; Drenth Justin R., Method and system for describing, generating and checking non-wire guidepaths for automatic guided vehicles.
Matthias Benzinger DE; Friedrich Boettiger DE; Rachad Mahmoud DE; Avshalom Suissa DE, Method and system for detecting and localizing sensor defects in motor vehicles.
.ANG.strom Karl-Erik,SEX, Method for determining the positions of a plurality of anonymous fixed reference objects for mobile surface transportation and a device for determining said positions.
Evans ; Jr. John M. (Brookfield CT) King Steven J. (Woodbury CT) Weiman Carl F. R. (Westport CT), Mobile robot navigation employing retroreflective ceiling features.
Wilson,Edward, Model-based fault detection and isolation for intermittently active faults with application to motion-based thruster fault detection and isolation for spacecraft.
McTamaney Louis S. (Cupertino CA) Wong Yue M. (Saratoga CA) Chandra Rangasami S. (Pleasanton CA) Walker Robert A. (Sunnyvale CA) Lastra Jorge E. (San Jose CA) Wagner Paul A. (Cambridge MA) Sharma Uma, Multi-purpose autonomous vehicle with path plotting.
Trepagnier, Paul Gerard; Nagel, Jorge Emilio; Kinney, Powell McVay; Dooner, Matthew Taylor; Wilson, Bruce Mackie; Schneider, Jr., Carl Reimers; Goeller, Keith Brian, Navigation and control system for autonomous vehicles.
Summerville David F. (Garland TX) Williston John P. (Plano TX) Wand Martin A. (Plano TX) Doty Thomas J. (Dallas TX) Rice Haradon J. (Plano TX), Static collision avoidance method for multiple automatically guided vehicles.
Enright,Jeffery M.; Martin,Kevin F.; Stephenson,Brad L.; Hathaway,Roy; Kehner,Tom; Knouff,Christopher J.; Varn,Kenneth C.; Thomas,Jeffrey R.; Drummond,Jay Paul; Kortis,John; Crane,David A.; Goldring,, System and method for capturing and searching image data associated with transactions.
Gudat Adam J. (Edelstein IL) Whittaker William L. (Pittsburgh PA) Kleimenhagen Karl W. (Peoria IL) Christensen Dana A. (Peoria IL) Kemner Carl A. (Peoria Heights IL) Bradbury Walter J. (Peoria IL) Ko, System and method for controlling an autonomously navigated vehicle.
Shaffer Gary K. (Butler PA) Whittaker William L. (Pittsburgh PA) West Jay H. (Pittsburgh PA) Clow Richard G. (Phoenix AZ) Singh Sanjiv J. (Pittsburgh PA) Lay Norman K. (Peoria IL) Devier Lonnie J. (P, System and method for detecting obstacles in the path of a vehicle.
Eglington,Michael; O'Connor,Michael L.; Leckie,Lars G.; Sapilewski,Glen A., System and method for interactive selection and determination of agricultural vehicle guide paths offset from each other with varying curvature along their length.
Haynie, Michael B.; Laurune, William R., System and method for vitally determining position and position uncertainty of a railroad vehicle employing diverse sensors including a global positioning system sensor.
Goncalves,Luis Filipe Domingues; Di Bernardo,Enrico; Pirjanian,Paolo; Karlsson,L. Niklas, Systems and methods for computing a relative pose for global localization in a visual simultaneous localization and mapping system.
Karlsson,L. Niklas; Goncalves,Luis Filipe Domingues; Di Bernardo,Enrico; Pirjanian,Paolo, Systems and methods for correction of drift via global localization with a visual landmark.
Goncalves, Luis Filipe Domingues; Di Bernardo, Enrico; Pirjanian, Paolo; Karlsson, L. Niklas, Systems and methods for filtering potentially unreliable visual data for visual simultaneous localization and mapping.
Goncalves,Luis Filipe Domingues; Karlsson,L. Niklas; Pirjanian,Paolo; Di Bernardo,Enrico, Systems and methods for filtering potentially unreliable visual data for visual simultaneous localization and mapping.
Karlsson,L. Niklas; Pirjanian,Paolo; Goncalves,Luis Filipe Domingues; Di Bernardo,Enrico, Systems and methods for incrementally updating a pose of a mobile device calculated by visual simultaneous localization and mapping techniques.
Karlsson, L. Nicklas; Pirjanian, Paolo; Goncalves, Luis Filipe Domingues; Bernardo, Enrico Di, Systems and methods for using multiple hypotheses in a visual simultaneous localization and mapping system.
Duggan,David S.; Felio,David A.; Pate,Billy B.; Longhi,Vince R.; Petersen,Jerry L.; Bergee,Mark J., Vehicle control system including related methods and components.
Keeler James D. (Austin TX) Havener John P. (Austin TX) Godbole Devendra (Austin TX) Ferguson ; II Ralph B. (Austin TX), Virtual emissions monitor for automobile.
Keeler James David (Austin TX) Havener John Paul (Austin TX) Godbole Devendra (Austin TX) Ferguson ; II Ralph Bruce (Austin TX), Virtual emissions monitor for automobile and associated control system.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.