A symbolic motion planning approach for the reach-avoid problem

摘要

This paper addresses the motion planning problem for two autonomous robots (the defender and the attacker) with competitive objectives, which are involved in a reach-avoid scenario. This adversarial aspect of the game makes the problem complex with high computational cost. To address this problem, we propose a novel symbolic approach for the robot motion planning and control of the robots, which can effectively manage the complexity of the problem. The basic idea is to partition the environment into convex regions, and then, capture the desired objectives of the defender and the adversarial behavior of the attacker with temporal logic formulas. We also use finite two-player zero-sum games as a tool for the robot decision-making over the partitioned space. An illustrative examples has been provided to detail the steps of the proposed algorithm and the simulation results are presented to verify the effectiveness of the proposed algorithm.