How can we make a robot autonomously explore an indoor environment, focusing on "rooms"? And how can we make multiple robots collectively explore as many rooms without redundancy under limited communication?

Abstract

This work proposes an autonomous multi-robot exploration pipeline that coordinates the behaviors of robots in an indoor environment composed of multiple rooms. Contrary to simple frontier-based exploration approaches, we aim to enable robots to methodically explore and observe an unknown set of rooms in a structured building, keeping track of which rooms are already explored and sharing this information among robots to coordinate their behaviors in a distributed manner. To this end, we propose (1) a geometric cue extraction method that processes 3D point cloud data and detects the locations of potential cues such as doors and rooms, (2) a circular decomposition for free spaces used for target assignment. Using these two components, our pipeline effectively assigns tasks among robots, and enables a methodical exploration of rooms. We evaluate the performance of our pipeline using a team of up to 3 aerial robots, and show that our method outperforms the baseline by 33.4% in simulation and 26.4% in real-world experiments

Perception and Data Processing

We focus on 3D LiDAR point cloud processing approach that enables high-speed, low-compute processing onboard.

An indoor environment is composed of multiple rooms. The exploring robot generates 3D occupancy voxel grid from 3D point cloud data. The robot flattens 3D voxel grid map into 2D binary voxel grid map, and appiles median filtering. Then the robot generates 2D distance transform map. We utilize this distance transform map to extract meaningful geometric features and cues for exploration.

Door Detection using Saddle Point Extraction

We model the doors as saddle points in the distance transform.

Think of a top-down view of a drone located at a door. And let's think about the distance to the closest occupied cells (which, in this case, are walls).

The point at the door has the farthest distance to the occupied cells, when compared to other points that lie on the axis of wall. This point has the smallest distance to the occupied cells, when compared to other points that lie on the perpendicular axis. In the distance transform space, the door(point) is at its maximum along one axis, and at its minimum along another perpendicular axis. Thus, we can model the doors as saddle points in the distance transform.

Circular Decomposition of Free Space

We represent the free space in rooms by decomposing it into circles. Extracting local maxima and distance to the occupied cells from distance transform map, robot generates circles that are tangent to the inner walls of the rooms via our circular decomposition method.

The motivation behind this is that visiting the centers of the circles will enable the robot to observe most of the room. A circle, which is defined by a center and a radius, is also a compact representation of the space to maintain.

Multi-Robot Coordination

For multi-robot coordination, we make the robots share the doors (saddle points) and rooms (free space decomposed into circles) as necessary information. Each robot updates the doors it has reached and circles it has completed, and publishes this information to other robots; each robot also receives information on the doors and circles that were reached by other robots.

Communicating this information bidirectionally, each robot avoids targeting a door that was reached by itself and other robots. Likewise, each robot avoids targeting a circle that was visited by itself and other robots.

Qualitative Results

Using the baseline (frontier-based exploration), robots first choose to travel corridors fast by moving straight because the goal is to simply increase the coverage. In contrary, using our methods, the robots quickly turn directions as the focus is to explore rooms. The robots first target doors and then enter each room to explore.

Using our method, two robots simultaneously explore rooms in a building without redundancy.

Using our method, three robots simultaneously explore rooms in a building without redundancy.

Our saddle point extraction algorithm is robust at detecting doors (a) not only in normal settings, (b) but also when the axes of walls are not aligned with x-axis and y-axis of global coordinate frame. This is because the detection of saddle points (which is obtained from second-order partial derivative test from 2D Hessian matrix) can be done irrespective of the wall's alignment with the global axes. It only requires that a function (in this case, distance to the occupied cells) has a local maximum in one direction, but a local minimum in another direction. These two directions should be perpendicular each other, but they don't necessarily have to be aligned with the global axes.

Real-Robot Experiments

Here are real-robot experiments.

Codes will be released soon.

Citation

Acknowledgements

We thank Ian Higgins, Je Hon Tan, Jay Patrikar, and Aditya Parandekar for helping with real-robot experiments. This work was supported by Defense Science and Technology Agency (DSTA) Singapore.