Reactive Planning in Non-Convex Environments

Integration of offline and online information for real-time execution of a provably correct navigation scheme in non-convex environments

Closed-loop, vector field based planning offers an important alternative to traditional motion planning techniques (e.g., RRTs), due to their robustness when modeling errors and sensory noise become important. Traditionally, guaranteed convergence to a designated goal within the context of vector-field based planning had only been established for reactive planners possessing substantial prior knowledge about the environment. However, sensor-based reactive methods are needed to guarantee safe navigation in an unknown environment with unforeseen obstacles. Important recent advances in the theory of sensor-based navigation show how to successfully negotiate unknown obstacles in real time without losing global convergence guarantees, but are limited by the necessity of simple geometry (i.e., the obstacles need to be strongly convex).

This research seeks to elucidate the manner in which partial knowledge may suffice to inform safe, convergent, reactive navigation in geometrically more interesting environments. Recent developments in semantic SLAM and object pose and triangular mesh extraction using convolutional neural net architectures now provide an avenue for incorporating partial prior knowledge within a deterministic framework well suited to our vector field planning methods.

Multi-layer representation of the environment

In our work, we assume a catalogue of known shapes that can be recognized and localized online by a limited range onboard sensor. These ingredients suggest a representation of the environment taking the form of a “multi-layer” triple of topological spaces whose realtime interaction can be exploited to integrate geometrically naive sensor driven methods with offline memorized geometry sensitive methods. We generate a realtime smooth change of coordinates (i.e., a diffeomorphism) of the mapped layer of the environment into a topologically equivalent but geometrically more favorable model layer relative to which simple sensor-based methods can be directly applied. We prove that the conjugate vector field defined by pulling back the reactive model space planner through this diffeomorphism induces a vector field on the robot’s physical configuration space that inherits the same formal guarantees of obstacle avoidance and convergence.

Provably correct navigation among known and unknown obstacles

We also extend the construction to the case of a differential drive robot, by pulling back the extended field over planar rigid transformations through a suitable polar coordinate transformation of the tangent lift of our original planar diffeomorphism and demonstrate, once again, that the physical differential drive robot inherits the same obstacle avoidance and convergence properties as those guaranteed for the geometrically simple model robot. Finally, to better support online implementation of these constructions, we adopt modular methods for implicit descriptions of geometric shape.

Representation of an obstacle boundary as an AND-OR tree using R-functions

Ongoing research seeks to extend this work to arbitrary planar shapes, elucidate the way in which vector field planning can be applied in 3D environments (e.g., with quadrotors) and provide open-source software for efficiently implementing sensor-based navigation schemes online with any platform.


Vasileios Vasilopoulos‘s role: Vassilis has been involved with the development of the navigation scheme and the algorithm that “deforms” obstacles with complicated geometry in the mapped layer to obstacles with simple disk-shaped geometry in the model layer.

Publications: WAFR 2018

Sponsor: AFRL