Simultaneous HumanRobot Matching and Routing for MultiRobot Tour Guiding Under Time Uncertainty

Abstract

This work presents a framework for multirobot tour guidance in a partially known environment with uncertainty, such as a museum. In the proposed centralized multirobot planner, a simultaneous matching and routing problem (SMRP) is formulated to match the humans with robot guides according to their selected places of interest (POIs) and generate the routes and schedules for the robots according to uncertain spatial and time estimation. A large neighborhood search algorithm is developed to efficiently find suboptimal lowcost solutions for the SMRP. The scalability and optimality of the multirobot planner are evaluated computationally under different numbers of humans, robots, and POIs. The largest case tested involves 50 robots, 250 humans, and 50 POIs. Then, a photorealistic multirobot simulation platform was developed based on HabitatAI to verify the tour guiding performance in an uncertain indoor environment. Results demonstrate that the proposed centralized tour planner is scalable, makes a smooth tradeoff in the plans under different environmental constraints, and can lead to robust performance with inaccurate uncertainty estimations (within a certain margin).