Neural Formation A*: A Knowledge-Data Hybrid-Driven Path Planning Algorithm for Multi-agent Formation Cooperation

Efficient path planning method is crucial for multi-agent coordination tasks, such as cooperative transportation. The knowledge-driven approach has been widely employed. However, in problems with complex constraint conditions, the solution time of the knowledge-driven approach increases, accompanied by a degradation in solution quality. Motivated by this practical challenge, a knowledge-data hybrid-driven path planning algorithm named Neural Formation A* (NFA*) is proposed in this paper. It first utilizes a feature extraction network to transform the given environment map into a feature map. Path planning problem instances with ground-truth path are utilized to train the feature extraction network. Then, a map reconfiguration module is designed to inflate the area of obstacles in the environment to exclude infeasible nodes for multi-agent formation. Finally, a differentiable A* module is designed to generate feasible path for the multi-agent formation from start location to goal location. By combining data-driven techniques with knowledge, NFA* provides a promising solution for multi-agent formation path planning problems. Evaluations under different path planning scenarios demonstrate that NFA* outperforms a state-of-the-art path planner in terms of path feasibility.