Mobile Robot Navigation in Dynamic Environments
PhD Thesis

Maren Bennewitz
June 2004



Summary

    Service robots which act in environments populated by humans have become very popular in the last few years. A variety of systems exists which act for example in hospitals, office buildings, department stores, and museums. Furthermore, several multi-robot systems have been developed for tasks which can be accomplished more efficiently by a whole team of robots than just by a single robot.

    Coordinating the motions of multiple mobile robots is one of the fundamental problems in robotics. The predominant algorithms for coordinating teams of robots are decoupled and prioritized, thereby avoiding combinatorially hard planning problems typically faced by centralized approaches. While these methods are very efficient, they have two major drawbacks. First, they are incomplete, i.e. they sometimes fail to find a solution even if one exists, and second, the resulting solutions are often not optimal. We developed a method for finding and optimizing priority schemes for such prioritized and decoupled planning techniques. Existing approaches apply a single priority scheme which makes them overly prone to failure in cases where valid solutions exist. By searching in the space of priorization schemes, our approach overcomes this limitation. It performs a randomized search with hill-climbing to find solutions and to minimize the overall path length. To focus the search, our algorithm is guided by constraints generated from the task specification.

    The second part of this thesis is focused on robots acting in environments populated by humans. These systems can improve their behavior if they react appropriately to the activities of the surrounding people and do not interfere with them. In contrast to a multi-robot path planning system, the future movements of people are not known. Therefore, the robots have to be able to detect people with their sensors, to identify them, and to learn their intentions in order to be able to make better predictions of their future behavior. Whenever people move through their environments they do not move randomly. Instead, they usually follow specific trajectories or motion patterns corresponding to their intentions. Knowledge about such patterns enables a mobile robot to robustly keep track of persons in its environment and to improve its behavior. We propose a technique for learning collections of trajectories that characterize typical motion patterns of persons. Data recorded with laser-range finders is clustered using the expectation maximization algorithm. Based on the result of the clustering process we derive a Hidden Markov Model (HMM) that is applied to estimate the current and future positions of persons based on sensory input. We present several experiments carried out in different environments with a mobile robot equipped with a laser range scanner and a camera system. The results demonstrate that our approach can reliably learn motion patterns of persons, can robustly estimate and predict the positions of multiple persons, and can be used to improve the navigation behavior of a mobile robot.


Links