In Partial Fulfillment of the Requirements for the Degree of Master of Science

Priyal Prasanna Kulkarni

will defend her thesis

Design of a System for Multiple Route Selection in the Presence of Flooding

Abstract

Safe navigation during flooding is integral in minimizing loss of life. Navigation has throughout literature been treated as a search problem with the aim of optimizing certain impedance. The earliest study of path finding started in the late 1800s forming the basis of depth-first search techniques. This was followed by the introduction of a lot of popular algorithms including Dijkstra’s, A*and Bellman-Ford. Recently, the study of path planning – for road networks based on heuristics for dynamic or partially known environments has gained a lot of attention. In this thesis, we present a unique approach to finding multiple competitive paths between two locations on a street network that also considers road flooding. The key idea is to find a cost optimal solution for two locations using Dijkstra’s algorithm. We then penalize the found solution by increasing the traversal cost of one segment or the whole path, forcing the search algorithm to find alternative solutions. This framework is developed for the street network the City of Houston leveraging the capabilities of ArcGIS Desktop and Python scripting. The proposed algorithm is evaluated for quality and safety of resultant routes. This is done by comparing route lengths, elevations, widths, percentage of duplicate road segments, maximum speed limits of the obtained paths. We also conducted an experimental evaluation that shows an elevated sensitivity towards these factors as compared to the standard shortest path algorithms.

Date: Tuesday, July 10, 2018
Time: 11:30 AM
Place: PGH 550
Advisor: Dr. Christoph F. Eick

Faculty, students, and the general public are invited.