GENERAL ENQUIRIES: Tel: + 27 12 841 2911 | Email:

Show simple item record Leenen, L Terlunen, A 2014-02-26T06:49:14Z 2014-02-26T06:49:14Z 2013-11
dc.identifier.citation Leenen, L and Terlunen, A. 2013. A focussed dynamic path finding algorithm with constraints. In: International Conference on Adaptive Science and Technology (ICAST), Pretoria, South Africa, November 2013 en_US
dc.description International Conference on Adaptive Science and Technology (ICAST), Pretoria, South Africa, November 2013. Post print attached. en_US
dc.description.abstract The Military Unit Path Finding Problem (MUPFP) is the problem of finding a path from a starting point to a destination where a military unit has to move, or be moved, safely whilst avoiding threats and obstacles and minimising path cost in some digital representation of the actual terrain. The MUPFP has to be solved in an environment where information can change whilst the optimal path is being calculated, i.e. obstacles and threats can move or appear and path costs can change. In previous work, the authors formulated the MUPFP as a constraint satisfaction problem (CSP) where path costs are minimised whilst threat and obstacle avoidance constraints are satisfied in a dynamic environment. In this paper the previous algorithm is improved by adding a heuristic to focus the search for an optimal path. Existing approaches to solving path planning problems tend to combine path costs with various other criteria such as obstacle avoidance in the objective function which is being optimised. The authors’ approach is to optimise only path costs while ensuring that other criteria such as safety requirements, are met through the satisfaction of added constraints. Both the authors’ previous algorithm and the improved version presented in this paper are based on dynamic path planning algorithms presented by Stenz. Stenz’s original D* algorithm solves dynamic path finding problems (by optimising path costs without satisfying additional constraints) and his Focussed D* algorithm employs a heuristic function to focus the search. Stenz’s algorithms only optimises path costs; no additional factors such as threat and obstacle avoidance are addressed. en_US
dc.language.iso en en_US
dc.publisher IEEE Xplore en_US
dc.relation.ispartofseries Workflow;11880
dc.subject Military Unit Path Finding Problem en_US
dc.subject MUPFP en_US
dc.subject Constraint satisfaction problem en_US
dc.subject CSP en_US
dc.subject Path finding en_US
dc.subject Dynamic A* search en_US
dc.subject Optimisation en_US
dc.title A focussed dynamic path finding algorithm with constraints en_US
dc.type Presentation en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search ResearchSpace

Advanced Search


My Account