xTrek: An Influence-Aware Technique for Dijkstra and A* Pathfinders

• Author(s): Amador, Gonçalo ; Gomes, Abel
• Date: 2018
• Persistent ID: http://hdl.handle.net/10400.6/8298
• Origin: uBibliorum
• Subject(s): Pathfinding; Dijkstra; Influence field; Risk-adverse pathfinder; Influence-aware pathfinder
• Document Type: Journal article
• Language: English
• Contributor(s): uBibliorum

Description

We propose a new pathfinding technique called xTrek that combines conventional pathfinding and influence fields; that is, we are introducing a new influence-sensitive pathfinder or influence-aware pathfinder. The leading idea of influence-aware pathfinding is to avoid unwanted regions and/or converge to desired regions of the search space during the path search. As shown throughout the paper, this region avoidance/convergence is more striking using our technique than in other field-aware pathfinders as, for example, risk-adverse pathfinders and constraint-aware navigation pathfinders. Furthermore, our technique constrains the search space even more than such state-of-the-art influence-aware pathfinders, aiming to reduce the memory space consumption, to speed up pathfinding computations, and at the same time to have better control on the paths to be discovered.