dc.contributor.author |
Leenen, L
|
|
dc.contributor.author |
Terlunen, A
|
|
dc.date.accessioned |
2014-02-26T06:49:14Z |
|
dc.date.available |
2014-02-26T06:49:14Z |
|
dc.date.issued |
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.identifier.uri |
http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6707501
|
|
dc.identifier.uri |
http://hdl.handle.net/10204/7250
|
|
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 |
Conference Presentation |
en_US |
dc.identifier.apacitation |
Leenen, L., & Terlunen, A. (2013). A focussed dynamic path finding algorithm with constraints. IEEE Xplore. http://hdl.handle.net/10204/7250 |
en_ZA |
dc.identifier.chicagocitation |
Leenen, L, and A Terlunen. "A focussed dynamic path finding algorithm with constraints." (2013): http://hdl.handle.net/10204/7250 |
en_ZA |
dc.identifier.vancouvercitation |
Leenen L, Terlunen A, A focussed dynamic path finding algorithm with constraints; IEEE Xplore; 2013. http://hdl.handle.net/10204/7250 . |
en_ZA |
dc.identifier.ris |
TY - Conference Presentation
AU - Leenen, L
AU - Terlunen, A
AB - 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.
DA - 2013-11
DB - ResearchSpace
DP - CSIR
KW - Military Unit Path Finding Problem
KW - MUPFP
KW - Constraint satisfaction problem
KW - CSP
KW - Path finding
KW - Dynamic A* search
KW - Optimisation
LK - https://researchspace.csir.co.za
PY - 2013
T1 - A focussed dynamic path finding algorithm with constraints
TI - A focussed dynamic path finding algorithm with constraints
UR - http://hdl.handle.net/10204/7250
ER -
|
en_ZA |