Abstract
Path planning is a fundamental problem in many areas ranging from robotics and artificial intelligence to computer graphics and animation. While there is extensive literature for computing optimal, collision-free paths, there is little work that explores the satisfaction of spatial constraints between objects and agents at the global navigation layer. This paper presents a planning framework that satisfies multiple spatial constraints imposed on the path. The type of constraints specified could include staying behind a building, walking along walls, or avoiding the line of sight of patrolling agents. We introduce a hybrid environment representation that balances computational efficiency and discretization resolution, to provide a minimal, yet sufficient discretization of the search graph for constraint-aware navigation. An extended anytime-dynamic planner is used to compute constraint-aware paths, while efficiently repairing solutions to account for dynamic constraints. We demonstrate the benefits of our method on challenging navigation problems in complex environments for dynamic agents using combinations of hard and soft constraints, attracting and repelling constraints, on static obstacles and moving obstacles.
Related Articles
Planning Approaches to Constraint-Aware Navigation in Dynamic Environments
Kai Ninomiya, Mubbasir Kapadia, Francisco Garcia, and Norman I. BadlerComputer Animation and Virtual Worlds, 2014
Bibtex
Constraint-Aware Navigation in Dynamic Environments
Mubbasir Kapadia, Kai Ninomiya, Francisco Garcia, and Norman I. BadlerInternational Conference on Motion in Games, 2013
Bibtex
Source Code
The C# library an associated Unity project includes implementations of different planning algorithms including A*, Anytime Repairing A* (ARA*) and Anytime D* (AD*), along with extensions to handle static and dynamic spatial constraints.
Bitbucket repository
Videos
Download here