1. SocialMapf: Optimal and Efficient Multi-Agent Path Finding With Strategic Agents for Social Navigation
- Author
-
Rohan Chandra, Rahul Maligi, Arya Anantula, and Joydeep Biswas
- Subjects
FOS: Computer and information sciences ,Control and Optimization ,Computer Science - Artificial Intelligence ,Mechanical Engineering ,Biomedical Engineering ,Computer Science Applications ,Human-Computer Interaction ,Computer Science - Robotics ,Artificial Intelligence (cs.AI) ,Computer Science - Computer Science and Game Theory ,Artificial Intelligence ,Control and Systems Engineering ,Computer Science - Multiagent Systems ,Computer Vision and Pattern Recognition ,Robotics (cs.RO) ,Multiagent Systems (cs.MA) ,Computer Science and Game Theory (cs.GT) - Abstract
We propose an extension to the MAPF formulation, called SocialMAPF, to account for private incentives of agents in constrained environments such as doorways, narrow hallways, and corridor intersections. SocialMAPF is able to, for instance, accurately reason about the urgent incentive of an agent rushing to the hospital over another agent's less urgent incentive of going to a grocery store; MAPF ignores such agent-specific incentives. Our proposed formulation addresses the open problem of optimal and efficient path planning for agents with private incentives. To solve SocialMAPF, we propose a new class of algorithms that use mechanism design during conflict resolution to simultaneously optimize agents' private local utilities and the global system objective. We perform an extensive array of experiments that show that optimal search-based MAPF techniques lead to collisions and increased time-to-goal in SocialMAPF compared to our proposed method using mechanism design. Furthermore, we empirically demonstrate that mechanism design results in models that maximizes agent utility and minimizes the overall time-to-goal of the entire system. We further showcase the capabilities of mechanism design-based planning by successfully deploying it in environments with static obstacles. To conclude, we briefly list several research directions using the SocialMAPF formulation, such as exploring motion planning in the continuous domain for agents with private incentives., Full paper submission to R-AL. Shorter Blue Sky paper version available at AIHRI/2022/1016
- Published
- 2023