Motion Detection and Path Planning in Dynamic Environments

Motion detection from mobile platforms is a challenging task. It requires precise position information, which is difficult in cluttered dynamic environments. We combine motion detection and position estimation using Expectation Maximization. To reduce the computational time of this iterative approach, we segment the scan into feature elements which are then compared against an a-priori map. The motion detection is tested on real world data from a mass exhibition, showing correct classification. As one application of this information, we present a path planning approach with a unified probabilistic formalism for dynamic and static elements incorporating different levels of knowledge. The resulting probabilistic navigation function derives from co-occurrence probabilities and is currently computed using grids.

Toward Online Probabilistic Path Replanning

Björn Jensen, Roland Philippsen, Roland Siegwart

In this talk we present work on sensor-based motion planning in initially unknown dynamic environments. Motion detection and probabilistic motion modeling are combined with a smooth navigation function to perform on-line path planning and replanning in cluttered dynamic environments such as public exhibitions. Human behavior is unforeseeable in most situations that include human-robot interaction, e.g. service robots or robotic companions. This makes motion prediction problematic (they rarely move e.g. with constant velocity along straight lines), especially in settings which include large numbers of humans. Additionally, the robot is usually required to react swiftly rather than optimally, in other words the time required to calculate the plan becomes part of the optimality criterion. The "Probabilistic Navigation Function" (PNF) is an approach for planning in these cluttered dynamic environments. It relies on probabilistic worst-case computations of the collision risk and weighs regions based on that estimate. The PNF is intended to be used for gradient-descent control of a vehicle, where the gradient indicates the best trade-off between risk and detour. An underlying reactive collision avoidance provides the tight perception-action loop to cope with the remaining collision probability. As this is work in progress, we present the approach and describe finished components and give an outlook on remaining implementation issues. Two algorithmic building blocks have been developed and tested: On-line motion detection from a mobile platform is performed by the SLIP scan alignment method to separate static from dynamic objects (it also helps with pose estimation). The interface between motion detection and path planning is a probabilistic co-occurrence estimation measuring the risk of future collisions given environment constraints and worst-case scenarios, which unifies dynamic and static elements. The risk is translated into traversal costs for an E* path planner, which produces smooth navigation functions that can incorporate new environmental information in near real-time.

2006

Towards Real-Time Sensor-Based Path Planning in Highly Dynamic Environments

Björn Jensen, Roland Philippsen, Roland Siegwart

This paper presents work on sensor-based motion planning in initially unknown dynamic environments. Motion detection and probabilistic motion modeling are combined with a smooth navigation function to perform on-line path planning and replanning in cluttered dynamic environments such as public exhibitions. The SLIP algorithm, an extension of Iterative Closest Point, combines motion detection from a mobile platform with position estimation. This information is then processed using probabilistic motion prediction to yield a co-occurrence risk that unifies dynamic and static elements. The risk is translated into traversal costs for an E* path planner. It produces smooth paths that trade off collision risk versus detours.

2007

Toward Online Probabilistic Path Replanning

Björn Jensen, Roland Philippsen, Roland Siegwart

2006