Grid-based angle-constrained path planning
Square grids are commonly used in robotics and game development as spatial models and well known in AI community heuristic search algorithms (such as A*, JPS, Theta* etc.) are widely used for path planning on grids. A lot of research is concentrated on finding the shortest (in geometrical sense) paths while in many applications finding smooth paths (rather than the shortest ones but containing sharp turns) is preferable. In this paper we study the problem of generating smooth paths and concentrate on angle constrained path planning. We put angle-constrained path planning problem formally and present a new algorithm tailored to solve it - LIAN. We examine LIAN both theoretically and empirically. We show that it is sound and complete (under some restrictions). We also show that LIAN outperforms the analogues when solving numerous path planning tasks within urban outdoor navigation scenarios.
Code (0)
등록된 구현이 없습니다.
Tasks
Heuristic SearchSimilar Papers 제목 키워드 기반
Theta*: Any-Angle Path Planning on Grids
Grids with blocked and unblocked cells are often used to represent terrain in robotics and video games. However, paths formed by grid edges can be longer than true shortest paths in the terrain since their headings are a…
Resolving Spatial-Time Conflicts In A Set Of Any-angle Or Angle-constrained Grid Paths
We study the multi-agent path finding problem (MAPF) for a group of agents which are allowed to move into arbitrary directions on a 2D square grid. We focus on centralized conflict resolution for independently computed p…
Multi-Agent Path FindingContinuous World Coverage Path Planning for Fixed-Wing UAVs using Deep Reinforcement Learning
Unmanned Aerial Vehicle (UAV) Coverage Path Planning (CPP) is critical for applications such as precision agriculture and search and rescue. While traditional methods rely on discrete grid-based representations, real-wor…
Deep Reinforcement LearningMotion PlanningMulti-Agent Path Planning based on MPC and DDPG
The problem of mixed static and dynamic obstacle avoidance is essential for path planning in highly dynamic environment. However, the paths formed by grid edges can be longer than the true shortest paths in the terrain s…
Decision MakingModel Predictive ControlUnityOptimal any-angle path planning in static and dynamic environments
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 conti…