p Mubbasir Kapadia

Home Projects Publications Teaching Resume

Constraint-Aware Navigation in Dynamic Environments

Mubbasir Kapadia, Kai Ninomiya, Alexander Shoulson, Francisco Garcia, and Norman I. Badler

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. Badler

Computer Animation and Virtual Worlds, 2014
Bibtex


Constraint-Aware Navigation in Dynamic Environments

Mubbasir Kapadia, Kai Ninomiya, Francisco Garcia, and Norman I. Badler

International 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

JW Player goes here

--> myspace visitor tracker