FPAS: Frontier-Based Path Planning with Adaptive Sampling for Large-Scale Unknown Environments
2026-06-22 • Robotics
Robotics
AI summaryⓘ
The authors developed a new method called FPAS to help robots or agents find their way efficiently in large, unknown places. They improved how the system uses 'frontiers,' which are edges between explored and unexplored areas, to choose good paths toward goals and to backtrack when necessary. FPAS also changes how densely it maps the environment based on how open or narrow each area is, saving computing power in open spaces while checking narrow paths carefully. Tests showed FPAS is faster than other methods while still finding good routes.
Path PlanningFrontier ExplorationAdaptive SamplingGoal-reachingGraph DensityGlobal GraphNavigationComputational EfficiencySubgoalsUnknown Environments
Authors
Jinwoo Choi, Yeonkyu Lee, Jung-Taak Kim, Jisung Bae, Seung-Woo Seo
Abstract
In this work, we propose Frontier-based Path Planning with Adaptive Sampling (FPAS), a novel framework designed for efficient goal-reaching in large-scale, unknown environments. While existing planners often struggle with computational bottlenecks or inefficient paths during long-range navigation, FPAS overcomes these challenges by reinterpreting the frontier concept for goal-directed tasks. Specifically, our method leverages frontiers to effectively guide forward progression into unobserved regions and to select promising subgoals for backtracking from dead-ends or inefficient paths. Furthermore, FPAS introduces an adaptive sampling mechanism based on a frontier-derived openness metric. This mechanism dynamically adjusts the global graph's density by employing sparse nodes in open areas to alleviate computational burdens, while preserving denser sampling in narrow passages to ensure connectivity. Extensive evaluations demonstrate that FPAS substantially improves computational efficiency over baseline methods while maintaining highly competitive goal-reaching performance.