Problem Space Analysis for Plan Library Generation and Algorithm Selection in Real-time Systems

Computing solutions to intractable planning problems is particularly problematic within real-time domains. Many visitation planning problems can be mapped to a Dynamic Vehicle Routing Problem (DVRP), in which a system uses a set of vehicles to visit a set of potentially changing locations. One approach to this problem includes off-line computation of contingency plans. However, because complex domains preclude creating a comprehensive library, a system must choose a subset of all possible plans to include. Strategic selections will ensure that the library contains an appropriate plan for encountered situations.

This work proposes a scheme in which problem space analysis drives the creation of an efficient plan library. Problem space analysis can also inform the selection of an appropriate algorithm and its configuration during initial solution generation, and later during any necessary adaptation.

For complex problems, an exact analysis of the problem space is not feasible, and an efficient means of creating an approximation is required. Thus, this work proposes the development of algorithms to both efficiently generate and leverage the problem space analysis of complex planning problems.

• Dr. Tim Finin (Advisor, Chair)
• Dr. Marie desJardins
• Dr. Tim Oates
• Dr. R. Scott Cost