Multi-agent searching for fast determination of deconflicted trajectories

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.