Multi-agent searching for fast determination of deconflicted trajectories
A methodology for a multi-agent cooperative autorouting system with multiple dimensions uses time as one dimension to allow the computation of Correct by Construction navigational trajectories taking timed events and other vehicles moving within the space into account to achieve path deconfliction.
1 . A method of operating a Real-Time Flight Management System (RTFMS), the RTFMS comprising at least one traffic management server and at least one unmanned aerial vehicle (UAV), the method comprising:
mapping an area of operation (AO) in three dimensions to establish a 3D model of the AO, wherein the AO includes static obstructions that are mapped from LIDAR imaging data, and dynamic obstructions corresponding to flight zone keep-out areas having activation and expiration times and dates, and specialized obstructions having minimum altitude restrictions over specified areas within the AO;
saving the 3D model of the AO and its static, dynamic and specialized obstructions within an obstruction database;
transmitting a request for a flight plan from at least one UAV to the RTFMS;
establishing a track line as a flight path in two or more dimensions from a source point to a destination point for the at least one UAV;
searching the obstruction database for obstructions that intersect the track line;
establishing a virtual grid along the track line within the AO, and based on the virtual grid, defining obstruction polygons that simulate the obstructions that intersect the track line from the source point to the destination point, leaving the navigable space within the virtual grid that is separate from the obstruction polygons;
tessellating the navigable space into navigable polygons with the source point and destination point each within a navigable polygon, where the count of the navigable polygons is smaller than the number of grids, each face of a navigable polygon sharing with one other navigable polygon or with no other navigable polygon if that face was blocked by an obstruction;
constructing a flight path search tree of the navigable polygons that depicts the relationships between the navigable polygons, their faces and connecting navigable polygons;
applying a tree transversal algorithm and a cost function to search the flight path search tree; and
determining a flight plan for the at least one UAV based upon the fewest number of navigable polygons from the source point to the destination point.
2 . The method of claim 1 , further comprising forming the obstruction database from the LIDAR imaging data and 3D imaging data or stacked 2-dimensional image data forming the 3D model.
3 . The method of claim 1 , wherein obstructions comprise objects that a respective flight vehicle could not fly over.
4 . The method of claim 1 , comprising establishing a tangent line against obstruction polygons within the obstruction database to determine if an intersection exists, and if yes, spacing the flight path from the intersection.
5 . The method of claim 1 , comprising completing the flight path from the source point to the destination point that includes arcs and tangent line segments.
6 . The method of claim 1 , wherein the RTFMS determines that a potential conflicting path occurs with another UAV, and modifies the flight plan for the at least one UAV to avoid a collision.
7 . The method of claim 1 , wherein the RTFMS establishes the virtual grid within a defined space of the AO that encompasses the track line.
8 . The method of claim 1 , wherein the RTFMS includes a request buffer into which requests for flight plans from UAV's are added, and as computational resources become available within the RTFMS, at least one request for flight plan is retrieved from the request buffer for further processing.
9 . The method of claim 1 , comprising employing the tree transversal algorithm and cost function to modify the flight plan for a respective UAV around an obstruction polygon from a first intersection of the track line to the polygon edge or vertex to the last intersection of the track line to the polygon edge or vertex and maintaining a continuous path from the source point to the destination point.
10 . The method of claim 1 , wherein static obstructions comprise objects within the AO that the respective UAV cannot fly over.
11 . The method of claim 1 , wherein the obstruction polygons are substantially rectangular configured.
12 . The method of claim 1 , wherein the navigable polygons are substantially rectangular configured.
13 . The method of claim 1 , wherein the virtual grid comprises a virtual construct within memory of the RTFMS.