کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6853243 658335 2014 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Limitations of acyclic causal graphs for planning
ترجمه فارسی عنوان
محدودیت های گرافیکی علیه سیلیکونی برای برنامه ریزی
کلمات کلیدی
برنامه ریزی، پیچیدگی محاسباتی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی
Causal graphs are widely used in planning to capture the internal structure of planning instances. Researchers have paid special attention to the subclass of planning instances with acyclic causal graphs, which in the past have been exploited to generate hierarchical plans, to compute heuristics, and to identify classes of planning instances that are easy to solve. This naturally raises the question of whether planning is easier when the causal graph is acyclic. In this article we show that the answer to this question is no, proving that in the worst case, the problem of plan existence is PSPACE-complete even when the causal graph is acyclic. Since the variables of the planning instances in our reduction are propositional, this result applies to Strips planning with negative preconditions. We show that the reduction still holds if we restrict actions to have at most two preconditions. Having established that planning is hard for acyclic causal graphs, we study two subclasses of planning instances with acyclic causal graphs. One such subclass is described by propositional variables that are either irreversible or symmetrically reversible. Another subclass is described by variables with strongly connected domain transition graphs. In both cases, plan existence is bounded away from PSPACE, but in the latter case, the problem of bounded plan existence is hard, implying that optimal planning is significantly harder than satisficing planning for this class.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 210, May 2014, Pages 36-55
نویسندگان
, , ,