Heuristic Approach for Real-Time Multi-Agent Trajectory Planning under Uncertainty

Motion planning of agents is one of the fundamental research problems in autonomous systems. An important aspect of motion planning is collision avoidance of the agents with other agents and obstacles that are present in the agent's environment. Typically, the collision avoidance constraints are non-linear and non-convex. Thus, the mathematical formulation of motion planning of multiple agents, in the presence of other agents and obstacles, is NP-Hard. In this paper, a novel heuristic approach for motion planning in multi-agent dynamic environment is proposed. The approach is computationally cheap, and can be launched locally on each agent for the trajectory planning. The applicability of the proposed approach is illustrated by numerical examples considering uncertainty in the environment. Detailed discussions on the performance of the proposed approach are presented. Finally, the observations on the key characteristics of the proposed approach are summarized.