Multi-Robot Human Guidance Using Topological Graphs.

Abstract

Prior approaches to human guidance using robots inside a building have typically been limited to a single robot guide that navigates a human from start to goal. However, due to their limited mobility, the robot is often unable to keep up with the human’s natural speed. In contrast, this paper addresses this difference in mobility between robots and people by presenting an approach that uses multiple robots to guide a human. Our approach uses a compact topological graph representation of the environment, and we first present the procedure for generating this representation. Next, we formulate the multi-robot guidance problem as a Markov Decision Process (MDP). Using a model of human motion in the presence of guiding robots, we define the transition function for this MDP. Finally, we solve the MDP using Value Iteration to obtain an optimal policy for placing robots and evaluate this policy’s effectiveness. Indoor environments such as airports, shopping malls, hospitals, and warehouse stores are characteristically full of people hurrying towards a destination or trying to locate a particular item. Often, they are unfamiliar with the environment and spend a fair amount of time locating these resources. With recent advancements in service robots, it is becoming far more feasible to deploy a large number of robots to aid humans in these environments. This paper studies how ubiquitous robots in an environment can be used to guide people efficiently to their destinations. Past research has explored the possibility of using a single robot to guide people (Thrun et al. 1999; Philippsen and Siegwart 2003). However, in environments densely packed with moving people and goods, navigating a guide robot the entire length from a human’s start location to their goal can be a significant challenge. The same navigation task can be completed far more efficiently by people, and yet they become limited by the navigation speed of the guide. A multirobot solution can make use of a human’s ease of navigation by proactively placing robots where the human is likely to need help in the future. Whenever the system needs to guide a human at a specific location, it can commission a nearby robot to direct the human towards the next objective, whether it be another guide robot or the goal. Once that Copyright c ??? 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. robot’s task is completed, it can go back to performing its other duties. Potentially, this approach can greatly reduce the time each individual robot has to spend guiding the human, allowing robots to assist more people in the same time. This paper specifically studies the problem of deciding where to place robots in an environment to guide a human as he or she moves around. First, we formulate this multi-robot guidance problem as a Markov Decision Process (MDP), and use a hand-coded model of human motion in the presence of guide robots to define the transition function for this MDP. We then use Value Iteration (Sutton and Barto 1998) to solve this MDP, generating an optimal solution for placing robots. Such a solution can take the uncertainty in a human’s movement into account and avoid actions that have a significant probability of failure. Finally, we evaluate the generated policy by comparing it against a heuristic solution for deciding robot placements. Experiments are run using the model of human motion, as well as with avatars controlled by real humans in a simulation environment. To reason about human movement and robot placements, a representation of the environment is required. This paper uses a topological graph representation of the environment for reasoning (see Fig. 1h). Topological graphs can provide a compact representation of the environment while still retaining all key locations and the connectivity between these locations. The process of topological graph generation described in this paper is built on previous work (Thrun and B