Sketching for Efficient and Robust Top-Down Autonomous Navigation

Overview

Inspired by the human ability to efficiently and robustly navigate in a diversity of environments, our project aims to develop a novel top-down, low-resource robotic navigation approach in unmapped environments. Comparing state-of-the-art solutions in robotics with their natural counterparts, this project focuses on three opportunities:

  1. Combine machine learning and optimization techniques to sketch a high-level representation of the environment composed of semantically meaningful units.
  2. Generate a collection feedback controllers, with rigorous performance guarantees, that can be used to both navigate and improve the representation of the environment.
  3. Consider multi-agent settings where robots in a team use collaboration to further reduce sensing requirements, and reuse previous experience to reduce computation requirements. 

BoxMap: High-Level Mapping and Navigation Supported by Machine Learning

BoxMap is a novel high-level mapping method that uses machine learning algorithms to exploit the structure of sensed partial environments, and update a topological map representing semantic entities (rooms and doors) and their relations.

BoxMap has two main components: machine learning for extracting and fusing high-level entities from measurements, and graph-based map construction and navigation.

Machine Learning for Extracting and Fusing High-Level Entities from Measurements

We developed a new deep learning architecture that combines parametric representations (for semantic entities) with non-parametric partial maps (to fuse measurements). The architecture includes:

  •  A Convolutional Neural Network backbone plus a Detection Transformer with gating to extract features from low-level measurements (laser scans) into estimate of parameters of semantic entities.
  • Hand-crafted ReLU layers that translate, in a differentiable way, our parametric representation into non-parametric Truncated Distance Sign Functions (TSDFs).
  • Loss functions that compare non-parametric representations. The loss is hierarchical, as it first computes a loss on rooms only, subtracts their footprint, and then focuses on doors.
Conceptual diagram showing a CNN backbone, a transformer-based encoder-decoder producing a set of room and door predictions, and a map-based loss.
Overview of the machine learning component of BoxMap: a CNN backbone, a transformer-based encoder-decoder, hand-crafted layers producing a set of room and door predictions, and a TSDF-based loss.

Mapping component

A semantic map module builds a graph of semantic entities (rooms connected by doors). The graph is updated by transforming it into a local TSDF, and then fusing it with new measurements using the neural network above. The fusion produces new candidates for rooms and doors, which are then incorporated in the topological map via simple overlap tests.

A diagram with multiple rows of images. The first row shows the cumulative occupancy grid generated from the current graph map. The second row shows the current measurements. The third row shows the result of the inference of the machine learning module. The fourth row shows the current, explored, unexplored rooms and a planned path. The fifth row shows the path of the robot.
Map construction and exploration using BoxMap

Testing

BoxMap has been tested in a Python-only simulation (based on pseudoSLAM), and then in a ROS-Gazebo simulation.

Our BoxMap representation scales quadratically with the number of rooms (with a small constant), resulting in significant savings over a full geometric map. Moreover, our high-level topological representation results in 23.9% shorter trajectories in the exploration task with respect to standard methods.

Lyapunov Control with Monotonic Layers for Navigation in BoxMap

Lyapunov monotone neural networks have layers that compose three operations: projections of the input along given directions; monotone neurons, which output monotonically increasing piecewise linear functions of the projections; sums of all monotone neurons.

We developed Lyapunov monotonic neural networks, a novel deep learning architecture to encode Lyapunov functions. Our architecture ensures, by construction, that Lyapunov functions are unimodal and quasi-convex (i.e., with a unique minimum at the origin and star-convex level sets).

Verified region of attraction for a 4-D cart-pole system before (blue) and after (red) maximization.

When paired with a piecewise linear feedback controller and a piecewise linear model for the dynamics, our Lyapunov monotonic neural networks enable rigorous verification of stability over a Region of Attraction (RoA) using Mixed-Integer Linear Programming (MILP). The result of the verification can be used to train the Lyapunov function and the controller together over a fixed RoA, or increase the RoA.

In the context of BoxMap, this methodology has been applied to synthesize the control of a unicycle in rooms connected by doors (i.e., compatible with the high-level representation used by BoxMap).

Controller synthesis for a unicycle model navigating in a rectangular room toward a door (right side). The environment is divided in three regions, with a separate controller for each region. Left: control field for a zero-heading angle. Right: resulting trajectories.

Funding and support

This project is supported by the National Science Foundation grant “Sketching for Efficient and Robust Top-Down Autonomous Navigation” (Award number 2409733) 

Start date: September 1, 2024
End date: July 31, 2027

Disclaimer: Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.