Hierarchical Shortest Pathfinding Applied to Scheduling and Route Planning for Wheelchair Users
By Suling Yang
The population of wheelchair users is very significant and increasing
dramatically. Thus, finding accessible wheelchair routes is an important
problem. However, the routes to the closest elevator in a new building,
temporary road conditions and bus schedules may be unknown to wheelchair users.
Therefore, we were motivated to create route planning software which can be
installed on a small device to give wheelchair users route accessibility
information while they are traveling. Our software also contains a simple
scheduler which can synchronize with a route planner to provide more accurate
commuting information for clients. As well as designing and creating the new
system, we have analyzed and implemented a new efficient pathfinding algorithm,
which is the major contribution of this thesis. The algorithm deploys the
hierarchical structure of real-life maps.
Assuming that the distance within an abstract high-level node is significantly
shorter than along high-level edges, the algorithm can prune away unsubstantial
paths. Runtime analysis and experimental results show that this algorithm is
efficient in numerous scenarios.