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

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.

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

Toward Online Probabilistic Path Replanning

Björn Jensen, Roland Philippsen, Roland Siegwart

2006