Invention Grant
- Patent Title: Systems and methods for informable multi-objective and multi-direction rapidly exploring random tree route planning
-
Application No.: US17733654Application Date: 2022-04-29
-
Publication No.: US12104910B2Publication Date: 2024-10-01
- Inventor: Jiunn-Kai Huang , Yingwen Tan , Dongmyeong Lee , Vishnu R. Desaraju , Jessy W. Grizzle
- Applicant: Toyota Research Institute, Inc. , The Regents Of The University Of Michigan
- Applicant Address: US CA Los Altos
- Assignee: Toyota Research Institute, Inc.,Toyota Jidosha Kabushiki Kaisha,The Regents of the University of Michigan
- Current Assignee: Toyota Research Institute, Inc.,Toyota Jidosha Kabushiki Kaisha,The Regents of the University of Michigan
- Current Assignee Address: US CA Los Altos; JP Toyota; US MI Ann Arbor
- Agency: Dinsmore & Shohl LLP
- Main IPC: G06Q50/40
- IPC: G06Q50/40 ; G01C21/34 ; G06N3/126 ; G06N5/01 ; G06Q10/047

Abstract:
A method includes inputting a source into a weighted and undirected graph having a plurality of nodes and edges, inputting a target, inputting a plurality of objectives, searching the graph using a rapidly exploring random tree algorithm to determine a solution path that meets an existence constraint and an order constraint, determining a plurality of paths between the source and the target that intersects with each one of the plurality of objectives at least once that conforms with the existence constraint, assigning a travel cost for each of the determined plurality of paths, determining a visiting order of the plurality of objectives that reduces the assigned travel cost by the RRT* algorithm asymptotically decreasing with an allocated computation time by rewiring each one of the plurality of objectives and outputting the solution path to form a connected graph having the plurality of nodes.
Public/Granted literature
Information query