Autonomous Exploration Development Environment and the Planning Algorithms

Chao Cao, Hongbiao Zhu, Fan Yang, Yukun Xia, Howie Choset, Jean Oh, Ji Zhang

This paper, authored by researchers at Carnegie Mellon University, introduces a comprehensive open-source software stack designed to take the headache out of developing and deploying autonomous robots. By providing a "mid-layer" that handles the messy reality of terrain analysis and local obstacle avoidance, the authors allow researchers to focus on high-level planning while ensuring their algorithms work just as well on a real robot as they do in a simulator.

TL;DR

The researchers have released the Autonomous Exploration Development Environment, an open-source "full-stack" repository for 3D Lidar-based navigation. It includes high-fidelity simulation models, a robust local planner, and two state-of-the-art high-level planners (TARE and FAR) that powered the CMU-OSU team to a "Most Sectors Explored" award at the DARPA Subterranean Challenge.

What Problem Does This Paper Address?

Building an autonomous navigation system usually requires a massive engineering effort to integrate disparate modules: state estimation, terrain mapping, collision avoidance, and global path planning. Often, a researcher might develop a brilliant exploration algorithm in a simplified simulation, only to find it fails in the real world because it can't handle "negative obstacles" (like a pit or a cliff) or because the transition from simulation to hardware is too jarring.

This paper addresses the gap between high-level planning research and real-world deployment. It provides a standardized "middle-ware" that abstracts away the low-level complexities of the robot's hardware while providing a realistic environment for testing.

Methods

The system follows a three-tier architecture:

  1. Bottom Layer: Handles state estimation (where the robot is) and motion control (how the wheels turn).
  2. Mid-Layer (The "Dev Env"): This is the core contribution. It includes a Local Planner that uses Monte Carlo sampling to find collision-free paths and a Terrain Analysis module that builds voxel-based cost maps. Crucially, it handles "negative obstacles" by analyzing data point distributions to identify drops in the floor.
  3. Top Layer (High-Level Planners):
    • TARE (Exploration): A hierarchical planner that solves a "Traveling Salesman Problem" at two levels—a coarse global path and a detailed local path—to ensure the robot doesn't waste time revisiting areas.
  4. FAR (Route Planning): A visibility graph-based planner that can navigate both known and unknown environments, dynamically updating its map as the robot moves.

Datasets

The paper provides five distinct simulation environments to stress-test different navigation challenges:

  • Campus: Large-scale, undulating terrain.
  • Indoor: Narrow corridors and lobby areas.
  • Garage: A multi-floor (5-story) environment with steep ramps.
  • Tunnel: A complex network of underground passages.
  • Forest: Cluttered outdoor space with trees and houses.

The environment is also compatible with Matterport3D (photorealistic indoor models) and AI Habitat. For real-world validation, the authors used data from the DARPA Subterranean Challenge.

Key Insights and Ideas

  • Sim-to-Real Parity: The environment is designed so that the exact same code used in simulation can be ported to a vehicle computer. It doesn't rely on "cheating" (like using ground-truth global maps that wouldn't exist in the real world).
  • Hierarchy over Greed: Most exploration algorithms are "greedy," meaning they just go to the nearest unknown point. TARE’s hierarchical approach looks further ahead, leading to significantly more efficient coverage of large spaces.
  • Visibility Graphs for Speed: By using visibility graphs for the FAR planner, the system can re-calculate complex routes in less than 0.3 milliseconds, allowing the robot to react instantly to new information.

Key Results

  • DARPA Subterranean Challenge: The system was the "brain" of the CMU-OSU team. In the final competition, they explored 26 out of 28 sectors, the highest completion rate among all competing teams.
  • Efficiency: In a test involving a four-story garage, the TARE planner successfully explored the entire 1,839-meter environment in roughly 31 minutes (1907s).
  • Computational Load: The FAR planner is highly efficient, utilizing only about 15% of a single CPU thread on a standard i7 laptop for its visibility graph expansions.

Limitations and Future Work

  • Kinematic Constraints: The current system is optimized for differential-drive or skid-steer robots (like wheelchairs or treaded bots). It does not currently support "car-like" (Ackermann) steering, which involves more complex turning radius constraints.
  • Sensor Focus: The stack is primarily built around 3D Lidar. While it supports vision-based research through simulation, the core navigation modules are geometry-heavy.
  • Future Directions: The authors plan to extend the environment to support multi-robot coordination and are looking into "mixed-initiative" navigation, where a human can provide high-level natural language instructions (e.g., "go through the door and turn left") that the system then executes.

Note to researchers: The code for the Development Environment, TARE, and FAR planners is available on GitHub (links provided in the paper's footnotes).

Summary updated

Abstract

Autonomous Exploration Development Environment is an open-source repository released to facilitate development of high-level planning algorithms and integration of com-plete autonomous navigation systems. The repository contains representative simulation environment models, fundamental navigation modules, e.g., local planner, terrain traversability analysis, waypoint following, and visualization tools. Together with two of our high-level planner releases - TARE planner for exploration and FAR planner for route planning, we detail usage of the three open-source repositories and share experiences in integration of autonomous navigation systems. We use DARPA Subterranean Challenge as a use case where the repositories together form the main navigation system of the CMU-OSU Team. In the end, we discuss a few potential use cases in extended applications.
BibTeX
@inproceedings{cao2022autonomous,
  author = {Chao Cao and Hongbiao Zhu and Fan Yang and Yukun Xia and Howie Choset and Jean Oh and Ji Zhang},
  title = {{Autonomous Exploration Development Environment and the Planning Algorithms}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2022},
  doi = {10.1109/icra46639.2022.9812330},
}
Figure