Theory and techniques for synthesizing efficient breadth-first search algorithms

Repository

Theory and techniques for synthesizing efficient breadth-first search algorithms

Show simple record

dc.contributor.advisor Cook, William Randall
dc.creator Nedunuri, Srinivas
dc.date.accessioned 2012-10-05T21:15:34Z
dc.date.available 2012-10-05T21:15:34Z
dc.date.created 2012-08
dc.date.issued 2012-10-05
dc.date.submitted August 2012
dc.identifier.uri http://hdl.handle.net/2152/ETD-UT-2012-08-6242
dc.description.abstract 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).
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subject Program synthesis
dc.subject Algorithms
dc.subject Formal methods
dc.subject AI
dc.subject Search algorithms
dc.title Theory and techniques for synthesizing efficient breadth-first search algorithms
dc.date.updated 2012-10-05T21:15:46Z
dc.identifier.slug 2152/ETD-UT-2012-08-6242
dc.contributor.committeeMember Batory, Don
dc.contributor.committeeMember Baxter, Ira
dc.contributor.committeeMember Pingali, Keshav
dc.contributor.committeeMember Smith, Douglas R.
dc.description.department Computer Sciences
dc.type.genre thesis
dc.type.material text
thesis.degree.department Computer Sciences
thesis.degree.discipline Computer Science
thesis.degree.grantor University of Texas at Austin
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy

Files in this work

Size: 978.3Kb
Format: application/pdf

This work appears in the following Collection(s)

Show simple record


Advanced Search

Browse

My Account

Statistics

Information