# FIG-OP: Exploring Large-Scale Unknown Environments on a Fixed Time Budget

arXiv: https://arxiv.org/abs/2203.06316 · HTML: https://mlsanity.com/paper/2203.06316/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2022.

## Built on by (most cited first, 7 of 7)

- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [The Role of Predictive Uncertainty and Diversity in Embodied AI and Robot Learning](https://mlsanity.com/paper/2405.03164/) (2024)
- [Risk-aware Meta-level Decision Making for Exploration Under Uncertainty](https://mlsanity.com/paper/2209.05580/) (2022)
- [Improving the Resilience of Quadrotors in Underground Environments by Combining Learning-based and Safety Controllers](https://mlsanity.com/paper/2509.02808/) (2025)
- [HEADER: Hierarchical Robot Exploration via Attention-Based Deep Reinforcement Learning with Expert-Guided Reward](https://mlsanity.com/paper/2510.15679/) (2025)
- [FARE: Fast-Slow Agentic Robotic Exploration](https://mlsanity.com/paper/2601.14681/) (2026)
- [Orienteering Problem with Uncertain Time-Varying Rewards: Framework and Benchmark for Everyday Service Robotics](https://mlsanity.com/paper/2608.18672/) (2026)

## Abstract (arXiv)

We present a method for autonomous exploration of large-scale unknown environments under mission time constraints. We start by proposing the Frontloaded Information Gain Orienteering Problem (FIG-OP) -- a generalization of the traditional orienteering problem where the assumption of a reliable environmental model no longer holds. The FIG-OP addresses model uncertainty by frontloading expected information gain through the addition of a greedy incentive, effectively expediting the moment in which new area is uncovered. In order to reason across multi-kilometre environments, we solve FIG-OP over an information-efficient world representation, constructed through the aggregation of information from a topological and metric map. Our method was extensively tested and field-hardened across various complex environments, ranging from subway systems to mines. In comparative simulations, we observe that the FIG-OP solution exhibits improved coverage efficiency over solutions generated by greedy and traditional orienteering-based approaches (i.e. severe and minimal model uncertainty assumptions, respectively).