MTL Robustness for Path Planning with A*

Maintaining the safety of an autonomous drone while it executes a mission is a primary concern in presence of fixed and mobile enemies. Path planning using A* fails to deliver a feasible, safe plan when a drone has resource limitations in such environments. Enhancing A* with constraint optimization techniques may improve outcomes, but significantly increases path determination time. We define Robust A* (RA*) that introduces the use of a safety margin to maximize the robustness of the drone to meet mission requirements while managing resource restrictions. We rely on a theory of robustness based on Metric Temporal Logic (MTL) as applied to offline verification and online control of hybrid systems. By satisfying the predefined MTL constraints, RA* dynamically defines a safety margin between the drone and an enemy, while constraining the margin size given the drone's resources. The safety margin creates a robust neighborhood around the dynamically generated path. The robust neighborhood holds all valid trajectories within the current world state. When the world state changes, RA* first examines the robust neighborhood to find a valid trajectory before initiating the path re-planning. We evaluate RA* using the Rassim simulator. The results show that the algorithm generates faster and safer paths than the classical A* in the presence of moving enemies. 1 .