Learning the agent specific sub-optimal bound for multi-agent path finding

Abstract

Multi-Agent Path Finding (MAPF) is a prominent challenge in robotics and artificial intelligence, encompassing the task of finding collision-free paths for multiple agents sharing a common environment. CBS, a fundamental component of this research, plays a pivotal role in resolving conflicts encountered during path planning. There can be conflict between vertices (V) or there can be conflict in edges (E). The more agents there are in the environment, the higher the potential for collisions. With a greater number of agents, the likelihood of agents intersecting paths or occupying the same space at the same time increases. However, CBS typically aims for optimality, which can be computationally expensive and not always practical in real-time scenarios. To enhance the scalability and adaptability of MAPF, this study advocates for sub-optimal path planning, which takes into account agent-specific objectives and constraints. By relaxing the pursuit of optimal solutions, the approach reduces computational complexity and accommodates diverse agent requirements. Sub-optimal paths offer a deal between solution quality and computational effectiveness. Furthermore, the integration of ML models into MAPF augments its capabilities. Machine learning models can capture complex environmental dynamics and agent behaviors, enabling the prediction of future states and proactive path adjustments. This introduces an adaptive element to MAPF, where agents can dynamically adapt their paths based on real-time data and predictions. In conclusion, this research advocates a novel approach to MAPF by combining CBS, sub-optimal path planning tailored to individual agents, and the utilization of machine learning models. The synergy of these components offers a promising avenue for addressing complex multi-agent pathfinding problems in a scalable, adaptive, and efficient manner, opening new possibilities for realworld applications in robotics and AI.