Lexicographic Dual-Objective Path Finding in Multi-Agent Systems

Path finding in multi-agent systems aims to identify collision-free and cost-optimized paths for all agents with distinct start and goal positions. It poses challenging optimization problems. Existing research typically treats all agents equally, overlooking their differences in practical scenarios where they undertake the tasks of varying importance. In many application scenarios, agents must be differentiated into critical (c-agents) and acritical ones (a-agents) due to premium/general service, no-loaded/full-loaded states, and urgent/non-urgent tasks. Facing this practical need, this work focuses on multi-agent systems in which the different importance of agents must be considered; and tackles a lexicographic dual-objective variant of path-finding problem. The consideration of c-agents makes the concerned problem more useful yet more challenging than basic multi-agent path-finding problems. Different from existing multi-agent path planning methods that minimize the sum-of-costs of all agents, we optimize two objectives with preferences to emphasize the influence of c-agents on the system. The primary one is to minimize the sum-of-costs of c-agents and the secondary one is to minimize that of a-agents. As existing methods are inadequate for this unique challenge, we adapt a conflict-based search framework and design new two-level lexicographic dual-objective optimization methods to deal with it. A high level is responsible for iteratively expanding a search tree and adding constraints to resolve conflicts among agents. A low level is responsible for finding the path of each agent for the node newly expanded in the high level. By conducting numerous computational experiments, we verify the great performance of the presented methods in solving the concerned problem. We further develop a prototype system incorporating our methods and make it public to promote their practical application. This research contributes valuable insights and solutions to pathfinding challenges in multi-agent systems with critical and acritical agents. Note to Practitioners - This work addresses a multi-agent path finding problem in multi-agent systems involving both critical and acritical agents. The former are more important than the latter since they are assigned to perform more important tasks. This is a common scenario in manufacturing and service environments. We propose a two-level lexicographic dual-objective optimization framework to deal with the problem and underscore the importance of c-agents in the path finding problem. Three solution approaches are designed for practitioners to select based on their practical application needs. The computational experimental results and statistical analyses highlight the exceptional performance of our proposed approaches. In order to facilitate the practical application, we further provide a prototype system with our proposed approaches embedded, which is openly accessible for practitioners to realize their specific applications.