High-Level Mission Planning for Multi-Agent Indoor System

Abstract

The manuscript presents a high-level mission planning for multi-agent indoor systems. The high-level mission planning separates the mission goals between the agents, plans the order of the mission goals, and provides corridors serving as constraints for a real-time controller of the multi-agent system in which the real-time controller searches for optimal paths while resolving conflicts between the agents. The proposed algorithm uses a highly optimized tree data structure to represent a 3D indoor environment. Then the set of adjacent tree nodes defines the shortest possible corridor to fulfill the mission goals while avoiding obstacles in the indoor environment. Planning the mission goals order and assignment to agents is an NP-hard problem that we solve using heuristic algorithms to find a viable solution before the mission starts. This work implements a multi-objective optimization algorithm combining a genetic algorithm and simulated annealing to find a viable solution for the mission as a composition of the unobstructed corridors between the individual mission goals found by the A* path planning algorithm. The evaluation of the proposed high-level mission planning in a typical indoor environment finds a viable solution in time, even for a large number of mission goals. Also, the behavior of the multi-agent system is easily altered to prefer solutions minimizing the total traveled distance or distributing the workload evenly between the agents based on the mission character.