FPAS: Frontier-Based Path Planning with Adaptive Sampling for Large-Scale Unknown Environments
Abstract
Reaching a distant goal in a large-scale unknown environment is challenging because the robot must plan with only partial observations while continuously updating its map. Existing planners often suffer from inefficient detours, frequent replanning, or increasing computational cost as the explored area grows.
We propose Frontier-Based Path Planning with Adaptive Sampling (FPAS), an efficient goal-reaching framework for large-scale unknown environments. FPAS reinterprets frontiers as guidance signals for both local navigation and global replanning. Frontiers guide the robot toward promising unobserved regions and serve as subgoal candidates when backtracking is required.
FPAS also introduces an adaptive sampling strategy based on a frontier-derived openness metric. It sparsifies the global graph in open areas to reduce computation, while preserving dense nodes in narrow passages to maintain connectivity. This enables efficient and robust goal-reaching across diverse unknown environments.
Challenges
Goal-reaching with limited observations
The robot does not know the full map in advance. It must choose actions using only the observed region and revise its plan as new areas are revealed.
Balancing exploration and goal-directed navigation
The planner must explore unknown space without losing progress toward the final goal. Pure exploration can cause detours, while greedy goal-seeking can lead to dead-ends.
Replanning from dead-ends and inefficient paths
When the current route becomes blocked or inefficient, the robot must decide where to backtrack. Poor subgoal selection can cause repeated back-and-forth behavior.
Managing a growing global graph
As exploration continues, the global graph grows larger and becomes expensive to maintain. The planner must reduce graph size while preserving connectivity in narrow passages.
Main Idea
Reinterpreting Frontiers for Goal-Reaching
FPAS reinterprets frontiers as guidance signals for goal-reaching in unknown environments. A frontier represents the boundary between observed free space and unobserved regions. Instead of using frontiers only for exploration, FPAS uses them to decide both where to move next and where to restart the search when the current route becomes inefficient.
Local frontiers guide forward navigation into promising unknown regions, while accumulated global frontiers serve as subgoal candidates for replanning.
Two-Stage Planning with Frontier-Guided Backtracking
FPAS consists of two stages: a reactive planning stage and a replanning stage. In the reactive planning stage, FPAS generates local candidate paths within the sensor range and selects a path that balances information gain and progress toward the final goal.
When the robot reaches a dead-end or a previously observed direction becomes more promising, FPAS enters the replanning stage. It selects a global frontier as a subgoal and backtracks through the global graph. This allows the robot to resume exploration from a meaningful location instead of backtracking arbitrarily.
Adaptive Sampling with Openness
To support replanning, FPAS maintains a global graph. However, storing every sampled node can make the graph too large. FPAS addresses this with adaptive sampling based on local openness.
Open areas usually produce many local frontiers, so FPAS samples the global graph sparsely there. Narrow passages produce fewer frontiers, so FPAS keeps denser nodes to preserve connectivity.
Efficient and Robust Global Planning
By adjusting the graph density according to openness, FPAS maintains a compact but reliable global graph. This reduces unnecessary nodes in open spaces while preserving useful connections in narrow passages.
By combining frontier-guided navigation, frontier-based backtracking, and adaptive graph management, FPAS achieves efficient goal-reaching in large-scale unknown environments.
Results
We evaluated FPAS in three large-scale unknown environments: Forest, Tunnel, and Garage. The experiments were designed as sequential multi-goal reaching tasks, where the robot must reach multiple goals while continuously updating and reusing its global graph.
Across diverse environments, FPAS achieved efficient and robust goal-reaching performance. In the Forest environment, FPAS significantly reduced processing time compared to visibility-graph-based planning, while maintaining competitive travel distance. In the Tunnel environment, FPAS showed reliable replanning performance in narrow, maze-like passages and achieved shorter travel distance than the RRT-based baseline. In the Garage environment, which contains both open areas and narrow passages, FPAS achieved the best overall performance in both travel distance and computation time.
These results show that FPAS can efficiently handle different environmental structures by combining frontier-guided navigation, frontier-based replanning, and adaptive global graph management.
Acknowledgement
This research was supported by the Challengeable Future Defense Technology Research and Development Program through the Agency for Defense Development (ADD) funded by the Defense Acquisition Program Administration (DAPA) in 2026 (No. 915108201).
The website template was partly borrowed from Michael Gharbi, and Jon Barron.