The development of efficient algorithms to solve a wide variety of
combinatorial and planning problems is a significant achievement in
computer science. Traditionally each algorithm is developed individually,
based on flashes of insight or experience, and then (optionally) verified
for correctness. While computer science has formalized the analysis
and verification of algorithms, the process of algorithm development remains largely ad-hoc. The ad-hoc nature
of algorithm development is especially limiting when developing algorithms
for a family of related problems.
Guided program synthesis is an existing
methodology for systematic development of algorithms. Specific algorithms
are viewed as instances of very general algorithm schemas. For example,
the Global Search schema generalizes traditional branch-and-bound
search, and includes both depth-first and breadth-first strategies.
Algorithm development involves systematic specialization of the algorithm
schema based on problem-specific constraints to create efficient algorithms
that are correct by construction, obviating the need for a separate
verification step. Guided program synthesis has been applied to a
wide range of algorithms, but there is still no systematic process
for the synthesis of large search programs such as AI planners.
Our first contribution is the specialization of Global Search to a
class we call Efficient Breadth-First Search (EBFS), by incorporating
dominance relations to constrain the size of the frontier of the search
to be polynomially bounded. Dominance relations allow two search spaces
to be compared to determine whether one dominates the other, thus
allowing the dominated space to be eliminated from the search. We
further show that EBFS is an effective characterization of greedy
algorithms, when the breadth bound is set to one. Surprisingly, the
resulting characterization is more general than the well-known characterization
of greedy algorithms, namely the Greedy Algorithm parametrized over
algebraic structures called greedoids.
Our second contribution is a methodology for systematically deriving
dominance relations, not just for individual problems but for families
of related problems. The techniques are illustrated on numerous well-known
problems. Combining this with the program schema for EBFS results
in efficient greedy algorithms.
Our third contribution is application of the theory and methodology
to the practical problem of synthesizing fast planners. Nearly all
the state-of-the-art planners in the planning literature are heuristic
domain-independent planners. They generally do not scale well and
their space requirements also become quite prohibitive.
Planners such as TLPlan that incorporate domain-specific information
in the form of control rules are orders of magnitude faster. However,
devising the control rules is labor-intensive task and requires domain
expertise and insight. The correctness of the rules is also not guaranteed.
We introduce a method by which domain-specific dominance relations
can be systematically derived, which can then be turned into control
rules, and demonstrate the method on a planning problem (Logistics). / text
| Identifer | oai:union.ndltd.org:UTEXAS/oai:repositories.lib.utexas.edu:2152/ETD-UT-2012-08-6242 |
| Date | 05 October 2012 |
| Creators | Nedunuri, Srinivas |
| Source Sets | University of Texas |
| Language | English |
| Detected Language | English |
| Type | thesis |
| Format | application/pdf |
Page generated in 0.002 seconds