The purpose of this paper is to present an innovative planner for multi-agent exploration problems. The problem to be solved is similar to a Multiple Traveling Salesman problem: given a set of n targets and m vehicles, we seek optimal vehicle routes (shortest paths) for visiting all the targets once. Our approach first considers path planning for a single agent, solving the so-called Subtour problem, where the vehicle should visit k out of the n targets such that the connecting path is the shortest. A genetic algorithm is implemented to find near-optimal solutions of this Subtour problem. These solutions are then used to create an initial multi-vehicle plan through negotiation and sharing between the agents. This multi-agent plan is further optimized by a novel evolutionary algorithm to create a good overall team strategy. Results are presented to demonstrate the success of the approach.
展开▼
