  This work presents a framework for multi-robot tour guidance in a partially
known environment with uncertainty, such as a museum. A simultaneous matching
and routing problem (SMRP) is formulated to match the humans with robot guides
according to their requested places of interest (POIs) and generate the routes
for the robots according to uncertain time estimation. A large neighborhood
search algorithm is developed to efficiently find sub-optimal low-cost
solutions for the SMRP. The scalability and optimality of the multi-robot
planner are evaluated computationally. The largest case tested involves 50
robots, 250 humans, and 50 POIs. A photo-realistic multi-robot simulation was
developed to verify the tour guiding performance in an uncertain indoor
environment.
