Dissertation/Thesis Abstract

Planning in incomplete domains
by Robertson, Jared, M.S., Utah State University, 2012, 71; 1532849
Abstract (Summary)

Engineering complete planning domain descriptions is often very costly because of human error or lack of domain knowledge. While many have studied knowledge acquisition, relatively few have studied the synthesis of plans when the domain model is incomplete (i.e., actions have incomplete preconditions or effects). Prior work has evaluated the correctness of plans synthesized by disregarding such incomplete features, but not how to synthesize plans by reasoning about the incompleteness. In this work, we describe several techniques for reasoning that takes into account action incompleteness to increase the number of interpretations under which the plans will succeed. Among the techniques, we show that representing explanations of plan failure with prime implicants provides a natural approach to comparing plans by counting prime implicants instead of models—leading to better scalability and comparable quality plans.

We present and empirically evaluate a forward heuristic search planner, called DeFAULT, that synthesizes plans by propagating information about faults due to incompleteness both within the state space and the relaxed planning space. We compare DeFAULT with a control planner that uses the fast forward (FF) heuristic (measuring plan length and ignoring incompleteness). The results show that DeFAULT i) scales comparable to the planner using the FF heuristic (while finding better solutions), and ii) scales better when counting prime implicants than models.

Indexing (document details)
Advisor: Bryce, Daniel
Commitee: Allan, Vicki H., Flann, Nicholas
School: Utah State University
Department: Computer Science
School Location: United States -- Utah
Source: MAI 51/04M(E), Masters Abstracts International
Subjects: Artificial intelligence, Computer science
Keywords: Automated planning, Domain independent, Incomplete domains
Publication Number: 1532849
ISBN: 978-1-267-89399-4
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy