Optimal any-angle path planning in static and dynamic environments

• URL: http://arxiv.org/abs/2607.00065v1
• Date: Tue, 30 Jun 2026 12:40:23 GMT
• Title: Optimal any-angle path planning in static and dynamic environments
• Abstract summary: Zeta* and Zeta*-SIPP are developed for static and dynamic environments respectively.<n>Zeta*-SIPP, with either scanning method, is more than 20 times faster than the corresponding state-of-the-art optimal planner TO-AA-SIPP.
• Score: 3.8673630752805437
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Any-angle path planning extends traditional graph-based path planning by allowing movement between any pair of vertices, rather than being restricted by predefined edges. It can find straighter and shorter paths in continuous space with graphs, making it particularly suitable for navigation in open areas such as airspaces, warehouses, and oceans. Many any-angle path-planning algorithms have been proposed, but only a few can guarantee optimal solutions, especially in the presence of dynamic obstacles. To address this challenge, this article focuses on optimal any-angle path planning on grids and introduces two general techniques that accelerate computation while preserving optimality in both static and dynamic environments: 1) elliptical forward expansion, which leverages ellipse-based neighborhoods to restrict the search space, and 2) field of view, which replaces traditional line-of-sight methods to speed up visibility checks. To integrate these two techniques, inverted and forward scanning are introduced. Inverted scanning establishes visual connections from open nodes, whereas forward scanning initiates scans from closed nodes. Building on the proposed techniques, Zeta* and Zeta*-SIPP are developed for static and dynamic environments respectively. Zeta*, when combined with forward scanning, is similar to the state-of-the-art algorithm Anya and attains comparable performance. Unlike Anya, Zeta* can be readily extended to other settings, such as dynamic environments (e.g., Zeta*-SIPP). Zeta*-SIPP, with either scanning method, is more than 20 times faster than the corresponding state-of-the-art optimal planner TO-AA-SIPP. Overall, this research identifies the key requirements for achieving optimal any-angle path planning and introduces a unified approach suitable for different environments.

Related papers

• AutoPath: Learning Transferable Goal-Conditioned Stochastic Path Prior for Safe Navigation Without Human Demonstrations [103.61864552260316]
  Real-time navigation in dynamic environments requires collision-free and dynamically feasible motion under limited perception.<n>We formulate navigation as learning a transferable goal-aligned path prior that models a reusable distribution over goal-aligned geometry-consistent local paths conditioned on local observations.<n>We develop a structured prior learning framework that parameterizes local paths using a geometry-aware polar action manifold and incorporates risk-sensitive utility shaping with multi-goal distributional rollouts for stable and safety-aware planning.
  arXiv  Detail & Related papers  (2026-07-13T16:00:41Z)
• Search-Based Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets [4.512110686124693]
  We present an algorithmic framework based on graphs of space-time convex sets (ST-GCSs)<n>For multi-robot motion planning, we integrate ST-GCS planning and ECD into prioritized planning methods.<n>For large-scale demonstrations, the proposed multi-robot motion planner can solve instances with up to $100$ robots within only a few minutes.
  arXiv  Detail & Related papers  (2026-07-01T04:58:00Z)
• Hierarchical Informative Path Planning via Graph Guidance and Trajectory Optimization [10.020847331719398]
  We study informative path planning (IPP) with travel budgets in cluttered environments, where an agent collects measurements of a latent field modeled as a Gaussian process (GP) to reduce uncertainty at target locations.<n>We propose a hierarchical framework with three stages: (i) graph-based global planning, (ii) segment-wise budget allocation using geometric and kernel bounds, and (iii) spline-based refinement of each segment with hard constraints and obstacle pruning.
  arXiv  Detail & Related papers  (2026-01-23T23:27:20Z)
• Neural Nonmyopic Bayesian Optimization in Dynamic Cost Settings [73.44599934855067]
  LookaHES is a nonmyopic BO framework designed for dynamic, history-dependent cost environments.<n>LookaHES combines a multi-step variant of $H$-Entropy Search with pathwise sampling and neural policy optimization.<n>Our innovation is the integration of neural policies, including large language models, to effectively navigate structured, domain-specific action spaces.
  arXiv  Detail & Related papers  (2026-01-10T09:49:45Z)
• Enhanced UAV Path Planning Using the Tangent Intersection Guidance (TIG) Algorithm [0.0]
  Tangent Intersection Guidance (TIG) is an advanced approach for UAV path planning in both static and dynamic environments.<n>It generates two sub-paths for each threat, selects the optimal route based on an algorithm rule, and iteratively refines the path until the target is reached.<n>TIG demonstrates efficient real-time path planning capabilities for collision avoidance, outperforming APF and Dynamic APPATT algorithms.
  arXiv  Detail & Related papers  (2025-08-26T12:11:59Z)
• SCoTT: Strategic Chain-of-Thought Tasking for Wireless-Aware Robot Navigation in Digital Twins [78.53885607559958]
  We propose SCoTT, a wireless-aware path planning framework.<n>We show that SCoTT achieves path gains within 2% of DP-WA* while consistently generating shorter trajectories.<n>We also show the practical viability of our approach by deploying SCoTT as a ROS node within Gazebo simulations.
  arXiv  Detail & Related papers  (2024-11-27T10:45:49Z)
• GOI: Find 3D Gaussians of Interest with an Optimizable Open-vocabulary Semantic-space Hyperplane [53.388937705785025]
  3D open-vocabulary scene understanding is crucial for advancing augmented reality and robotic applications. We introduce GOI, a framework that integrates semantic features from 2D vision-language foundation models into 3D Gaussian Splatting (3DGS) Our method treats the feature selection process as a hyperplane division within the feature space, retaining only features that are highly relevant to the query.
  arXiv  Detail & Related papers  (2024-05-27T18:57:18Z)
• Vision-aided UAV navigation and dynamic obstacle avoidance using gradient-based B-spline trajectory optimization [7.874708385247353]
  This paper proposes a gradient-based B-spline trajectory optimization algorithm utilizing the robot's onboard vision. The proposed optimization first adopts the circle-based guide-point algorithm to approximate the costs and gradients for avoiding static obstacles. With the vision-detected moving objects, our receding-horizon distance field is simultaneously used to prevent dynamic collisions.
  arXiv  Detail & Related papers  (2022-09-15T02:12:30Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  We introduce a class of first-order methods for smooth constrained optimization. Two distinctive features of our approach are that projections or optimizations over the entire feasible set are avoided. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear.
  arXiv  Detail & Related papers  (2021-07-17T11:45:13Z)
• Learning Space Partitions for Path Planning [54.475949279050596]
  PlaLaM outperforms existing path planning methods in 2D navigation tasks, especially in the presence of difficult-to-escape local optima. These gains transfer to highly multimodal real-world tasks, where we outperform strong baselines in compiler phase ordering by up to 245% and in molecular design by up to 0.4 on properties on a 0-1 scale.
  arXiv  Detail & Related papers  (2021-06-19T18:06:11Z)
• Path Planning Followed by Kinodynamic Smoothing for Multirotor Aerial Vehicles (MAVs) [61.94975011711275]
  We propose a geometrically based motion planning technique textquotedblleft RRT*textquotedblright; for this purpose. In the proposed technique, we modified original RRT* introducing an adaptive search space and a steering function. We have tested the proposed technique in various simulated environments.
  arXiv  Detail & Related papers  (2020-08-29T09:55:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.