Learning Heuristics for Efficient Environment Exploration Using Graph Neural Networks

Edwin Paúl Herrera-Alarcón, Gabriele Baris, Massimo Satler, Carlo Alberto Avizzano, Giuseppe LoiannoICAR 2023 · OpenReview

Abstract

The robot exploration problem focuses on maximizing the volumetric map of a previously unknown environment. This is a relevant problem in several applications, such as search and rescue and monitoring, which require autonomous robots to examine the surroundings efficiently. Graph-based planning approaches embed the exploration information into a graph describing the global map while the robot incrementally builds it. Nevertheless, even if graph-based representations are computational and memory-efficient, the exploration decision-making problem complexity increases according to the graph size that grows at each iteration. In this paper, we propose a novel Graph Neural Network (GNN) approach trained with Reinforcement Learning (RL) that solves the decision-making problem for autonomous exploration. The learned policy represents the exploration expansion criterion, solving the decision-making problem efficiently and generalizing to different graph topologies and, consequently, environments. We validate the proposed approach with an aerial robot equipped with a depth camera in a benchmark exploration scenario using a high-performance physics engine for environment rendering. We compare the results against a state-of-the-art planning exploration algorithm, showing that the proposed approach matches its performance in terms of explored mapped volume. Additionally, our approach consistently maintains its performance regardless of the objective function used to explore the environment.

Introduction

Autonomous robot exploration is a fundamental challenge in robotics, particularly for applications like search and rescue where a robot must map an unknown environment quickly. A central part of this challenge is the Next-Best-View (NBV) problem: deciding which location to visit next to gain the most information.

Overview of the GNN-based exploration process, illustrating how the robot builds an exploration tree and uses a GNN to identify the next best view in a grid-based environment.

Traditional approaches typically rely on frontier-based methods or sampling-based planners. While effective, sampling-based planners build large exploration trees that become computationally expensive to evaluate as the mission progresses. This paper introduces a method to replace hand-crafted heuristics with a learned policy using a Graph Neural Network (GNN), enabling more efficient decision-making that scales with graph complexity.

Methodology

The core of the proposed approach is a modular framework that integrates a GNN into a standard sampling-based planner, such as Rapidly-exploring Random Trees (RRT).

GNN Architecture

The decision-making policy is implemented as an attention-based GNN with an encoder-decoder structure.

The GNN architecture uses an encoder to embed node features (position, gain, cost) and a decoder with multi-head attention to output a probability distribution for node selection.
  • Encoder: Processes node features, including 3D coordinates, expected information gain ("prize"), and movement cost ("penalty"). It uses multi-head attention to create embeddings that are invariant to node ordering.
  • Decoder: Uses the graph embeddings to output a probability distribution over the available nodes, effectively identifying the most promising branch of the exploration tree.

Training via Reinforcement Learning

The model is trained using the REINFORCE algorithm with a rollout baseline. By framing exploration as a Prize-Collecting Traveling Salesman Problem (PCTSP), the agent learns to maximize the "prize" (newly mapped volume) while minimizing the "penalty" (distance traveled). This RL-based training allows the model to generalize to various graph topologies without requiring a labeled dataset of optimal paths.

Experimental Results

The approach was validated in a high-fidelity simulation of a 40x40m maze-like environment. The GNN-based policy was compared against the state-of-the-art Receding Horizon NBV (RH-NBVP) planner.

  • Performance Parity: The GNN matched the total volume explored by the benchmark planner within the same time constraints.
  • Decision Efficiency: In scenarios focused on surface reconstruction, the GNN made fewer but more strategic decisions. It tended to choose nodes further away than those selected by "greedy" heuristics, leading to better map refinement and fewer errors.
  • Robustness: Unlike traditional heuristics that require tuning for specific goals, the learned policy demonstrated consistent performance across different exploration objectives, such as frontier discovery and high-detail reconstruction.

Discussion and Future Work

A key advantage of this GNN approach is its ability to provide efficient heuristics that avoid the heavy computational cost of re-optimizing paths at every step. However, current limitations include a "local" view of the exploration tree, which can occasionally lead to the robot getting stuck in local minima.

Future research will focus on incorporating the robot's entire exploration history into the GNN's memory. This would enable better global re-positioning decisions and further improve the autonomy of robots in complex, real-world environments.

Summary updated

Abstract

The robot exploration problem focuses on maximizing the volumetric map of a previously unknown environment. This is a relevant problem in several applications, such as search and rescue and monitoring, which require autonomous robots to examine the surroundings efficiently. Graph-based planning approaches embed the exploration information into a graph describing the global map while the robot incrementally builds it. Nevertheless, even if graph-based representations are computational and memory-efficient, the exploration decision-making problem complexity increases according to the graph size that grows at each iteration. In this paper, we propose a novel Graph Neural Network (GNN) approach trained with Reinforcement Learning (RL) that solves the decision-making problem for autonomous exploration. The learned policy represents the exploration expansion criterion, solving the decision-making problem efficiently and generalizing to different graph topologies and, consequently, environments. We validate the proposed approach with an aerial robot equipped with a depth camera in a benchmark exploration scenario using a high-performance physics engine for environment rendering. We compare the results against a state-of-the-art planning exploration algorithm, showing that the proposed approach matches its performance in terms of explored mapped volume. Additionally, our approach consistently maintains its performance regardless of the objective function used to explore the environment.
BibTeX
@inproceedings{herreraalarcon2023learning,
  author = {Edwin Paúl Herrera-Alarcón and Gabriele Baris and Massimo Satler and Carlo Alberto Avizzano and Giuseppe Loianno},
  title = {{Learning Heuristics for Efficient Environment Exploration Using Graph Neural Networks}},
  booktitle = {ICAR},
  year = {2023},
  url = {https://openreview.net/forum?id=35zBYgZjzx},
}
Figure