# US 11,999,479 B2 · Fast path planning for dynamic avoidance in partially known environments > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,999,479 B2 - Document ID: US11999479B2 - Status: Granted - Kind: B2 - Application number: 17/447,540 - Filed: 2021-09-13 - Published: 2023-03-16 - Granted: 2024-06-04 - Earliest claimed: 2021-09-13 - Assignees: Aurora Flight Sciences Corporation, a subsidiary of The Boeing Company - Applicants: Aurora Flight Sciences Corporation, a subsidiary of The Boeing Company - Inventors: Craig John Bonnoit; Jeffery Saunders - Web page: https://patentgrep.com/patent/US11999479B2 ## CPC - B64C 39/024: {of the remote controlled vehicle type, i.e. RPV} - G01C 21/20: Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) - G01C 21/3807: {characterised by the type of data} - G05D 1/1064: {specially adapted for avoiding collisions with other aircraft} - G05D 1/622: Obstacle avoidance (predicting or avoiding probable or impending collision of road vehicles B60W30/08) - G05D 1/693: for avoiding collisions between vehicles - G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem - G08G 5/26: Transmission of traffic-related information between aircraft and ground stations - G08G 5/34: for flight plan modification - G08G 5/53: for cruising - G08G 5/55: for a single aircraft - G08G 5/723: {from the aircraft} - G08G 5/80: Anti-collision systems - B64U 2201/10: autonomous, i.e. by navigating independently from ground or air stations, e.g. by using inertial navigation systems [INS] - G06Q 10/06313: {Resource planning in a project environment} - G06Q 50/40: Business processes related to the transportation industry (shipping G06Q10/083) - G08G 5/57: for unmanned aircraft - B64C: AEROPLANES; HELICOPTERS - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR - G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93}) - B64U: UNMANNED AERIAL VEHICLES [UAV]; EQUIPMENT THEREFOR ## Abstract Techniques for traversing in an environment that includes at least one obstacle, by a mobile autonomous system, to a destination in the environment, are presented. The techniques can include generating, prior to the mobile autonomous system commencing activity in the environment, a graph including a plurality of vertices representing positions in the environment and a plurality of edges between vertices representing feasible transitions by the mobile autonomous vehicle in the environment; annotating the graph with at least one edge connecting a representation of a present position of the mobile autonomous system to a vertex of the graph; determining, based on the graph, a path from the present position of the mobile autonomous system in the environment to the destination; and traversing the environment to the destination, by the mobile autonomous system, based on the path. ## Claims ### Claim 1 A method of traversing in an environment that includes at least one obstacle, by a mobile autonomous system, to a destination in the environment, the method comprising: generating, prior to the mobile autonomous system commencing activity in the environment, a graph comprising a plurality of vertices representing positions in the environment and a plurality of edges between vertices representing feasible transitions by the mobile autonomous vehicle in the environment, wherein the vertices store identifications of next vertices in traversing to the destination, and wherein the graph is log-sparse; annotating the graph with at least one edge connecting a representation of a present position of the mobile autonomous system to a vertex of the graph; determining, based on the graph, a path from the present position of the mobile autonomous system in the environment to the destination; and traversing the environment to the destination, by the mobile autonomous system, based on the path. ### Claim 2 (depends on 1) The method of claim 1, wherein the vertices store location and direction information. ### Claim 3 (depends on 1) The method of claim 1, wherein the vertices store respective costs to the destination. ### Claim 4 (depends on 1) The method of claim 1, wherein the at least one obstacle comprises at least one dynamic obstacle. ### Claim 5 (depends on 4) The method of claim 4, further comprising invalidating at least one edge in the graph to represent a position of the at least one obstacle at a particular time. ### Claim 6 (depends on 1) The method of claim 1, wherein the annotating the graph with the at least one edge comprises adding to the graph the at least one edge without generating a new memory allocation on an order of a size of the graph. ### Claim 7 (depends on 1) The method of claim 1, wherein the mobile autonomous system comprises an aircraft. ### Claim 8 (depends on 1) The method of claim 1, wherein the destination comprises a plurality of locations, and wherein the graph represents the plurality of locations by a plurality of vertices. ### Claim 9 (depends on 1) The method of claim 1, wherein the determining the path comprises performing a non-exhaustive search of the graph. ### Claim 10 A system for traversing in an environment that includes at least one obstacle, by a mobile autonomous system, to a destination in the environment, the system comprising: an electronic processor; and electronic persistent memory comprising instructions that, when executed by the electronic processor, configure the electronic processor to perform operations comprising: generating, prior to the mobile autonomous system commencing activity in the environment, a graph comprising a plurality of vertices representing positions in the environment and a plurality of edges between vertices representing feasible transitions by the mobile autonomous vehicle in the environment, wherein the vertices store identifications of next vertices in traversing to the destination, and wherein the graph is log-sparse; annotating the graph with at least one edge connecting a representation of a present position of the mobile autonomous system to a vertex of the graph; and determining, based on the graph, a path from the present position of the mobile autonomous system in the environment to the destination; wherein the mobile autonomous system is configured to traverse the environment to the destination based on the path. ### Claim 11 (depends on 10) The system of claim 10, wherein the vertices store location and direction information. ### Claim 12 (depends on 10) The system of claim 10, wherein the vertices store respective costs to the destination. ### Claim 13 (depends on 10) The system of claim 10, wherein the at least one obstacle comprises at least one dynamic obstacle. ### Claim 14 (depends on 13) The system of claim 13, wherein the operations further comprise invalidating at least one edge in the graph to represent a position of the at least one obstacle at a particular time. ### Claim 15 (depends on 10) The system of claim 10, wherein the annotating the graph with the at least one edge comprises adding to the graph the at least one edge without generating a new memory allocation on an order of a size of the graph. ### Claim 16 (depends on 10) The system of claim 10, wherein the mobile autonomous system comprises an aircraft. ### Claim 17 (depends on 10) The system of claim 10, wherein the destination comprises a plurality of locations, and wherein the graph represents the plurality of locations by a plurality of vertices. ### Claim 18 (depends on 10) The system of claim 10, wherein the determining the path comprises performing a non-exhaustive search of the graph.