# US 9,436,187 B2 · System and method for decentralized, multi-agent unmanned vehicle navigation and formation control > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,436,187 B2 - Document ID: US9436187B2 - Status: Granted - Kind: B2 - Application number: 14/597,522 - Filed: 2015-01-15 - Published: 2016-07-21 - Granted: 2016-09-06 - Earliest claimed: 2015-01-15 - Assignees: The United States of America as represented by the Secretary of the Navy - Applicants: William Dale Arbogast; Waleed Barnawi; Michael Eric Lind; Blake Wall - Inventors: William Dale Arbogast; Waleed Barnawi; Michael Eric Lind; Blake Wall - Web page: https://patentgrep.com/patent/US9436187B2 ## CPC - G05D 1/0291: {Fleet control (monitoring fleets in traffic control systems for road vehicles G08G1/127, G08G1/127)} - G01C 21/20: Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) - G05D 1/00: Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots (drive control systems specially adapted for autonomous road vehicles B60W60/00) - G05D 1/622: Obstacle avoidance (predicting or avoiding probable or impending collision of road vehicles B60W30/08) - G05D 1/695: for maintaining a fixed relative position of the vehicles, e.g. for convoy travelling or formation flight - G05D 1/6985: {using a lead vehicle, e.g. primary-secondary arrangements} - G05D 2109/34: {operating on the water surface} - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES - 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) ## Abstract A system and method for a USV fleet is disclosed that can execute autonomous path-planning in an A2/AD environment, where communication reach back to a base station for instruction or Positional, Navigation, and Timing (PNT) data is not assured. This process has the ability to adapt considering the failure and intermittent connection of the ad-hoc USV-to-USV data network. This process also has the ability to continue operation considering the failure of any or all communications between members and is immediately prepared for reconnection should failures occur. ## Claims ### Claim 1 A method for navigating a fleet of multiple unmanned vehicles from a first starting location to a second ending location via an initial pathway of waypoints, the iterative method for each of the unmanned vehicles comprising: accumulating sensor information representative of obstacle locations and boundaries of one or more sensed obstacles and vehicle locations of other sensed vehicles in the fleet between the first and second locations; calculating artificial potential field (APF) additive force vectors representative of virtual forces between each of the vehicles and between each vehicle and the sensed obstacles, including calculating when a force vector is zero which is representative of a local minimum; responsive to the local minimum, communicating to the fleet that a new path needs to be generated and generating a new path forward, including calculating one or more new path forward waypoints such that the local minimum is removed because of attraction to the new waypoints by calculating additive force vectors to remove the local minimum and attract the vehicle to the new waypoints around the sensed obstacles and the other sensed vehicles to the second location. ### Claim 2 (depends on 1) The method of claim 1 where each vehicle iteratively broadcasts position updates and calculates the APF force vectors. ### Claim 3 (depends on 2) The method of claim 2 where obstacles are sensed and estimated as a point-cloud, the obstacle point-cloud representation is abstracted on a grid representation of a map, a graph search algorithm is used and the waypoints to the destination location are the output, and the waypoints are applied to a real map. ### Claim 4 (depends on 3) The method of claim 3 where one of the vehicles in the fleet is designated as the current leader vehicle. ### Claim 5 (depends on 4) The method of claim 4 where a first group of one or more of the UVs lose communication others of the vehicles over a set period of time such that the first group stops operationally relying upon the others of the vehicles and where the current leader vehicle requests information and calls for an election of a new leader vehicle. ### Claim 6 The method of claim where the new leader vehicle listens and waits for responses and disseminates an analysis and decision. ### Claim 7 (depends on 6) The method of claim 6 where the vehicles are underwater vehicles. ### Claim 8 (depends on 6) The method of claim 6 where the vehicles are ground vehicles. ### Claim 9 (depends on 6) The method of claim 6 where the vehicles are air vehicles. ### Claim 10 (depends on 6) The method of claim 6 where the vehicles are space vehicles. ### Claim 11 (depends on 6) The method of claim 6 where at least two of the vehicles are different from a group of underwater, ground, air and space vehicles. ### Claim 12 A method for navigating a fleet of multiple unmanned vehicles from a first starting location to a second ending location via an initial pathway of waypoints, the iterative method for each of the unmanned vehicles comprising: accumulating sensor information representative of obstacle locations and boundaries of one or more sensed obstacles and vehicle locations of other sensed vehicles in the fleet between the first and second locations; calculating artificial potential field (APF) additive force vectors representative of virtual forces between each of the vehicles and between each vehicle and the sensed obstacles, including calculating when a force vector is zero which is representative of a local minimum; responsive to the local minimum, communicating to the fleet that a new path needs to be generated and generating a new path forward, including calculating one or more new path forward waypoints such that the local minimum is removed because of attraction to the new waypoints by calculating additive force vectors to remove the local minimum and attract the vehicle to the new waypoints around the sensed obstacles and the other sensed vehicles to the second location; where each vehicle iteratively broadcasts position updates and calculates the APF force vectors and where obstacles are sensed and estimated as a point-cloud, the obstacle point-cloud representation is abstracted on a grid representation of a map, a graph search algorithm is used and the waypoints to the destination location are the output, and the waypoints are applied to a real map. ### Claim 13 A method for navigating a fleet of multiple unmanned vehicles from a first starting location to a second ending location via an initial pathway of waypoints, the iterative method for each of the unmanned vehicles comprising: accumulating sensor information representative of obstacle locations and boundaries of one or more sensed obstacles and vehicle locations of other sensed vehicles in the fleet between the first and second locations; calculating artificial potential field (APF) additive force vectors representative of virtual forces between each of the vehicles and between each vehicle and the sensed obstacles, including calculating when a force vector is zero which is representative of a local minimum; responsive to the local minimum, communicating to the fleet that a new path needs to be generated and generating a new path forward, including calculating one or more new path forward waypoints such that the local minimum is removed because of attraction to the new waypoints by calculating additive force vectors to remove the local minimum and attract the vehicle to the new waypoints around the sensed obstacles and the other sensed vehicles to the second location; where each vehicle iteratively broadcasts position updates and calculates the APF force vectors and where obstacles are sensed and estimated as a point-cloud, the obstacle point-cloud representation is abstracted on a grid representation of a map, a graph search algorithm is used and the waypoints to the destination location are the output, and the waypoints are applied to a real map, and where one of the vehicles in the fleet is designated as the current leader vehicle, where a first group of one or more of the UVs lose communication others of the vehicles over a set period of time such that the first group stops operationally relying upon the others of the vehicles and where the current leader vehicle requests information and calls for an election of a new leader vehicle, and where the new leader vehicle listens and waits for responses and disseminates an analysis and decision. ### Claim 14 (depends on 13) The method of claim 13 where the vehicles are underwater vehicles. ### Claim 15 (depends on 13) The method of claim 13 where the vehicles are ground vehicles. ### Claim 16 (depends on 13) The method of claim 13 where the vehicles are air vehicles. ### Claim 17 (depends on 13) The method of claim 13 where the vehicles are space vehicles. ### Claim 18 (depends on 13) The method of claim 13 where at least two of the vehicles are different from a group of underwater, ground, air and space vehicles.