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.

Click here to go to the LCI Forum page