Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Constraint-aware navigation in dynamic environments
Kapadia M., Ninomiya K., Shoulson A., Garcia F., Badler N.  MIG 2013 (Proceedings of Motion in Games, Dublin, Ireland, Nov 7-9, 2013)111-120.2013.Type:Proceedings
Date Reviewed: Apr 23 2014

Kapadia et al. present a path planning method, mostly oriented to game applications such as non-player characters/autonomous agents, that is based on the anytime dynamic A* (AD*) planner [1]. The main improvements are related to the adoption of hybrid graphs to represent the environment, combining a coarse representation--the so-called “highways,” with few nodes and allowing fast planning--with a detailed representation--a dense graph with detailed triangulation of free spaces, and precise but slower planning. The authors also propose adding constraints that can influence the trajectories, with weights defining a multiplier field (continuous potential fields with attractors/repellants), generated from simple declarative prepositions (for example, In/Not In: Front, Between, LineOfSight). As the planner is based on AD*, it can deal with dynamic constraints and obstacles, interleaving planning with navigation execution. On the other side, as the planner uses constraints and hybrid graphs (with “highways”), the planned path is not guaranteed to be optimal.

The proposed approach improves the well-known path planning AD* algorithm, allowing it to define constraints and using an optimized hybrid representation of the environment, adding some interesting features to the original algorithm. The authors also present practical results that demonstrate the main advantages of their proposed approach.

Reviewer:  Fernando Osorio Review #: CR142210 (1407-0586)
1) Likhachev, M.; Ferguson, D. I.; Gordon, G. J.; Stentz, A.; Thrun, S. Anytime dynamic A*: an anytime, replanning algorithm. In Proc. of ICAPS. AAAI, 2005, 262–271.
Bookmark and Share
 
Animation (I.3.7 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Animation": Date
Making them move
Badler N., Barsky B., Zeltzer D., Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991. Type: Book (9781558601062)
Jul 1 1992
Computer animation primer
Fox D., Waite M., McGraw-Hill, Inc., New York, NY, 1984. Type: Book (9789780070217423)
Mar 1 1985
High speed animation and simulation for microcomputers
Adams L., TAB Books, Blue Ridge Summit, PA, 1987. Type: Book (9789780830628599)
Aug 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy