Shortest path problems arise in a variety of applications ranging from transportation planning to network routing among others. One group of these problems involves finding shortest paths in graphs where the edge weights are defined by probability distributions. While some research has addressed the problem of finding a single shortest path, no research has been done on finding multiple paths in such graphs. This thesis addresses the problem of finding paths for multiple robots through a graph in which the edge weights represent the probability that each edge will fail. The objective is to find paths for n robots that maximize the probability that at least k of them will arrive at the destination. If we make certain restrictions on the edge weights and topology of the graph, this problem can be solved in O(n log n)time. If we restrict only the topology, we can find approximate solutions which are still guaranteed to be better than the single most reliable path.
| Identifer | oai:union.ndltd.org:CLAREMONT/oai:scholarship.claremont.edu:hmc_theses-1146 |
| Date | 01 April 2003 |
| Creators | Chase, Melissa |
| Publisher | Scholarship @ Claremont |
| Source Sets | Claremont Colleges |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | HMC Senior Theses |
Page generated in 0.0022 seconds