System for efficient scheduling for multiple automated non-holonomic vehicles using a coordinated path planner
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G01C-021/20
G05D-001/02
출원번호
US-0881511
(2015-10-13)
등록번호
US-9958873
(2018-05-01)
발명자
/ 주소
Thomson, Jacob Jay
출원인 / 주소
Crown Equipment Corporation
대리인 / 주소
Dinsmore & Shohl LLP
인용정보
피인용 횟수 :
0인용 특허 :
151
초록▼
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 p
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.
대표청구항▼
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 ve
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; andthe 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. 2. The system as claimed in claim 1 wherein the one or more central processing units execute instructions to monitor the plurality of automated vehicles to ensure the plurality of automated vehicles 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 one or more central processing units are communicatively coupled to the plurality of automated vehicles through a network. 4. The system as claimed in claim 1 wherein the one or more central processing units execute instructions to: access the multi-level graph comprising high-level nodes, wherein the high-level nodes each correspond to a region of the multivehicle warehouse, each of the high level nodes comprises one or more lower-level nodes and one or more local paths, wherein: the one or more lower-level nodes comprise one or more connection nodes corresponding to a boundary of the region, and one or more roadmap nodes corresponding to an interior of the region, andthe one or more local paths link the connection nodes, the roadmap nodes, or a combination thereof;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;construct, with the one or more central processing units, the 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 the final path comprises a determined joining path and at least a portion of the local paths. 5. The system as claimed in claim 4 wherein the one or more central processing units execute 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 plurality of automated vehicles from navigating a part of the region corresponding the blocked nodes. 6. The system as claimed in claim 4 wherein the one or more central processing units execute instructions to constrain a number of the plurality of 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 plurality of automated vehicles permitted within each of the high-level nodes is two or less. 8. The system as claimed in claim 4 wherein the one or more central processing units execute instructions to: stop operation of the plurality of automated vehicles at a predetermined time; andresume operation of the plurality of 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 one or more central processing units 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 of one of the plurality of automated vehicles does not intersect with the start position and the goal position of one or more of the roadmap graphs for another automated vehicle of the plurality of automated vehicles. 11. The system as claimed in claim 4 wherein the coordinated path plan requires one of the plurality of automated vehicles to wait until another of the plurality of automated vehicles passes a specific location. 12. The system as claimed in claim 4 wherein the one or more central processing units 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 plurality of 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 one or more central processing units 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 plurality of automated vehicles are non-holonomic. 18. The system as claimed in claim 1 wherein the floor portion of the multivehicle warehouse comprises a floor area of a floor, the floor area comprising: one or more ramp portions, at least two levels comprising different elevations, or both. 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; andthe 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, andcommunicate 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.
Takayama Kuniharu,JPX ; Nakano Eiji,JPX ; Mori Yoshikazu,JPX ; Takahashi Takayuki,JPX, Apparatus for controlling motion of normal wheeled omni-directional vehicle and method thereof.
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.
Eric Richard Bartsch ; Charles William Fisher ; Paul Amaat France ; James Frederick Kirkpatrick ; Gary Gordon Heaton ; Thomas Charles Hortel ; Arseni Velerevich Radomyselski ; James Randy Stig, Home cleaning robot.
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.
Hill Heidebrecht (Remchingen Noe DEX), Method for determining the course of a land vehicle by comparing signals from wheel sensors with signals of a magnetic s.
.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.
Veugen Leonardus M. M.,NLX ; Hermans Hans G. M.,NLX ; Van Kessel Antoon M. M.,NLX, Method of determining a directional change during vehicle navigation, apparatus for carrying out such a method, and veh.
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.
Onishi Masanori,JPX ; Murata Masanao,JPX ; Nakai Yutaka,JPX ; Yasuda Katsumi,JPX ; Sugino Tsukasa,JPX ; Nakagawa Susumu,JPX ; Miura Kouji,JPX, Positional deviation detecting device for a mobile body and position correcting apparatus for a working machine mounted on a mobile body.
LaRue Charles (La Canada CA), Sensor free vehicle navigation system utilizing a voice input/output interface for routing a driver from his source poin.
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.
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.
Rao Prithvi N. (Pittsburgh PA) Shin Dong Hun (Pittsburgh PA) Whittaker William L. (Pittsburgh PA) Kleimenhagen Karl W. (Peoria IL) Singh Sanjiv J. (Pittsburgh PA) Kemner Carl A. (Peoria Heights IL) B, System and method for enabling an autonomous vehicle to track a desired path.
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.
Shin Dong Hun (Pittsburgh PA) Whittaker William L. (Pittsburgh PA) Singh Sanjiv J. (Pittsburgh PA) Devier Lonnie J. (Pittsburgh PA), System, and method for enabling a vehicle to track a path.
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.
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.
McKeefery James (2070 Stratford Dr. Milpitas CA 95035) Sachs James (503 Gilbert Ave. Menlo Park CA 94025) Wotiz Richard (15010 Montebello Rd. Cupertino CA 95014), Vehicle guidance and control systems and methods for controllably guiding a vehicle along a predetermined pathway.
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는 부적절한 답변을 할 수 있습니다.