• Sorted by Date • Classified by Publication Type • Sorted by First Author Last Name • Classified by Author Last Name •
Suling Yang and Alan K. Mackworth. Hierarchical Shortest Pathfinding Applied to Route-Planning for Wheelchair Users. In Proceedings of the Canadian Conference on Artificial Intelligence, CanadianAI 2007, pp. 539–550, Montreal, PQ, May 2007.
Pathfinding on large maps is time-consuming. Classical search algorithms such as Dijkstra's and A* algorithms may solve difficult problems in polynomial time. However, in real-world pathfinding examples where the search space increases dramatically, these algorithms are not appropriate. Hierarchical pathfinding algorithms that provide abstract plans of future routing, such as HPA* and PRA*, have been explored by previous researchers based on classical ones. Although the two hierarchical algorithms show improvement in efficiency, they only obtain near optimal solutions. In this paper, we introduce the Hierarchical Shortest Path algorithm (HSP) and a hybrid of the HSP and A* (HSPA*) algorithms, which find optimal solutions in logarithmic time for numerous examples. Our empirical study shows that HSP and HSPA* are superior to the classical algorithms on realistic examples, and our experimental results illustrate the efficiency of the two algorithms. We also demonstrate their applicability by providing an overview of our Route Planner project that applies the two algorithms proposed in this paper.
@InProceedings{CCAI07,
author = {Suling Yang and Alan K. Mackworth},
title = {Hierarchical Shortest Pathfinding Applied to Route-Planning for Wheelchair Users},
year = {2007},
month = {May},
pages = {539--550},
booktitle = {Proceedings of the Canadian Conference on Artificial Intelligence, CanadianAI 2007},
address = {Montreal, PQ},
note = {},
abstract = {Pathfinding on large maps is time-consuming. Classical search
algorithms such as Dijkstra's and A* algorithms may solve difficult problems
in polynomial time. However, in real-world pathfinding examples
where the search space increases dramatically, these algorithms are not
appropriate. Hierarchical pathfinding algorithms that provide abstract
plans of future routing, such as HPA* and PRA*, have been explored
by previous researchers based on classical ones. Although the two hierarchical
algorithms show improvement in efficiency, they only obtain near
optimal solutions. In this paper, we introduce the Hierarchical Shortest
Path algorithm (HSP) and a hybrid of the HSP and A* (HSPA*) algorithms,
which find optimal solutions in logarithmic time for numerous
examples. Our empirical study shows that HSP and HSPA* are superior
to the classical algorithms on realistic examples, and our experimental
results illustrate the efficiency of the two algorithms. We also demonstrate
their applicability by providing an overview of our Route Planner
project that applies the two algorithms proposed in this paper.},
bib2html_pubtype ={Refereed Conference Proceeding},
bib2html_rescat ={},
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Apr 23, 2014 19:08:34