基于符号模型检测的一致性规划

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
我们通过提出一种新的一致性规划方法来解决不确定性领域中的规划问题。一致性规划是一个问题，即尽管领域的不确定性，但找到一个保证实现目标的动作序列。我们的方法是基于规划域作为有限状态自动机的表示。我们使用符号模型检查技术，特别是二元决策图，来紧凑地表示和有效地搜索自动机。在本文中，我们做出了以下贡献。首先，我们提出了一个通用的一致性规划算法，该算法适用于初始条件和作用效果都不确定的完全不确定性领域。该算法基于广度优先的反向搜索，如果存在规划问题的解，则返回最小长度的一致性规划，否则终止该问题不存在一致性解的结论。其次，我们给出了基于二元决策图的搜索空间的符号表示，这是由符号模型检查衍生的搜索技术的基础。符号表示使得在单个计算步骤中分析潜在的大的状态和转换集合成为可能，从而提供了一种有效的实现。第三，我们提出了CMBP（Conformant Model Based Planner）,它是上述数据结构和算法的有效实现，直接基于BDD操作，它允许搜索层的紧凑表示和搜索步骤的有效实现。最后，我们将我们的方法与目前最先进的一致性规划器CGP、QBFPLAN和GPT进行了实验比较。我们的分析包括来自这些系统的分销包的所有规划问题，以及其他定义为强调一些具体因素的问题。我们的方法似乎是最有效的：严格来说，CMBP比QBFPLAN和CGP更有表现力，而且在所有可能进行比较的问题中，CMBP的表现优于其竞争对手，有时是数量级的。
---
英文标题：
《Conformant Planning via Symbolic Model Checking》
---
作者：
A. Cimatti, M. Roveri
---
最新提交年份：
2011
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  We tackle the problem of planning in nondeterministic domains, by presenting a new approach to conformant planning. Conformant planning is the problem of finding a sequence of actions that is guaranteed to achieve the goal despite the nondeterminism of the domain. Our approach is based on the representation of the planning domain as a finite state automaton. We use Symbolic Model Checking techniques, in particular Binary Decision Diagrams, to compactly represent and efficiently search the automaton. In this paper we make the following contributions. First, we present a general planning algorithm for conformant planning, which applies to fully nondeterministic domains, with uncertainty in the initial condition and in action effects. The algorithm is based on a breadth-first, backward search, and returns conformant plans of minimal length, if a solution to the planning problem exists, otherwise it terminates concluding that the problem admits no conformant solution. Second, we provide a symbolic representation of the search space based on Binary Decision Diagrams (BDDs), which is the basis for search techniques derived from symbolic model checking. The symbolic representation makes it possible to analyze potentially large sets of states and transitions in a single computation step, thus providing for an efficient implementation. Third, we present CMBP (Conformant Model Based Planner), an efficient implementation of the data structures and algorithm described above, directly based on BDD manipulations, which allows for a compact representation of the search layers and an efficient implementation of the search steps. Finally, we present an experimental comparison of our approach with the state-of-the-art conformant planners CGP, QBFPLAN and GPT. Our analysis includes all the planning problems from the distribution packages of these systems, plus other problems defined to stress a number of specific factors. Our approach appears to be the most effective: CMBP is strictly more expressive than QBFPLAN and CGP and, in all the problems where a comparison is possible, CMBP outperforms its competitors, sometimes by orders of magnitude.
---
PDF链接：
https://arxiv.org/pdf/1106.0252

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：一致性 Presentation Intelligence manipulation Experimental algorithm conformant planning Model 我们