Rapid Plan Adaptation Through Offline Analysis of Potential Plan Disruptors

Simple item page
dc.contributor.advisordesJardins, Marie
dc.contributor.advisorFinin, Tim W
dc.contributor.authorHolder, Robert
dc.contributor.departmentComputer Science and Electrical Engineering
dc.contributor.programComputer Science
dc.date.accessioned2019-10-11T13:39:19Z
dc.date.available2019-10-11T13:39:19Z
dc.date.issued2016-01-01
dc.description.abstractComputing solutions to intractable planning problems is particularly problematic in dynamic, real-time domains. For example, visitation planning problems, such as a delivery truck that must deliver packages to various locations, can be mapped to a Traveling Salesman Problem (TSP). The TSP is an NP-complete problem, requiring planners to use heuristics to find solutions to any significantly large problem instance, and can require a lengthy amount of time. Planners that solve the dynamic variant, the Dynamic Traveling Salesman Problem (DTSP), calculate an efficient route to visit a set of potentially changing locations. When a new location becomes known, DTSP planners typically use heuristics to add the new locations to the previously computed route. Depending on the placement and quantity of these new locations, the efficiency of this adapted, approximated solution can vary significantly. Solving a DTSP in real time thus requires choosing between a TSP planner, which produces a relatively good but slowly generated solution, and a DTSP planner, which produces a less optimal solution relatively quickly. Instead of quickly generating approximate solutions or slowly generating better solutions at runtime, this dissertations introduces an alternate approach of precomputing a library of high-quality solutions prior to runtime. One could imagine a library containing a high-quality solution for every potential problem instance consisting of potential new locations, but this approach obviously does not scale with increasing problem complexity. Because complex domains preclude creating a comprehensive library, I instead choose a subset of all possible plans to include. Strategic plan selection will ensure that the library contains appropriate plans for future scenarios.
dc.genredissertations
dc.identifierdoi:10.13016/m2wenl-s1bi
dc.identifier.other11418
dc.identifier.urihttp://hdl.handle.net/11603/15479
dc.languageen
dc.relation.isAvailableAtThe University of Maryland, Baltimore County (UMBC)
dc.relation.ispartofUMBC Computer Science and Electrical Engineering Department Collection
dc.relation.ispartofUMBC Theses and Dissertations Collection
dc.relation.ispartofUMBC Graduate School Collection
dc.relation.ispartofUMBC Student Collection
dc.rightsThis item may be protected under Title 17 of the U.S. Copyright Law. It is made available by UMBC for non-commercial research and education. For permission to publish or reproduce, please see http://aok.lib.umbc.edu/specoll/repro.php or contact Special Collections at speccoll(at)umbc.edu
dc.sourceOriginal File Name: Holder_umbc_0434D_11418.pdf
dc.subjectplanning
dc.subjectproblem space analysis
dc.titleRapid Plan Adaptation Through Offline Analysis of Potential Plan Disruptors
dc.typeText
dcterms.accessRightsDistribution Rights granted to UMBC by the author.

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Holder_umbc_0434D_11418.pdf
Size:
1.59 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Holder_Rapid_Open.pdf
Size:
43.62 KB
Format:
Adobe Portable Document Format
Description:
Download

Collections

UMBC Theses and Dissertations