A Spatial Search Framework for Executing Perceptions and Actions in Diagrammatic Reasoning
A Spatial Search Framework for Executing Perceptions and Actions in Diagrammatic Reasoning
复制标题
用于在图解推理中执行感知和行动的空间搜索框架
DOI：
10.1007/978-3-642-14600-8_15
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
B. Chandrasekaran
中科院分区：
文献类型：
--
作者：
Bonny Banerjee;B. Chandrasekaran
图解推理(DR)需要从图中感知信息，并根据问题解决的需要修改/创建图中的对象。大多数灾难恢复系统中的感知和操作都是针对特定应用手动编码的。缺乏执行观念/行动的一般框架是机会主义地使用这些观念/行动的主要障碍。我们的目标是开发一个框架，用于在不需要人工干预的情况下跨任务/域执行各种特定的感知和操作。我们观察到领域/任务特定的感知/行为可以转化为领域/任务无关的空间问题。在我们的框架中，人类问题解算器将空间问题指定为真实领域中的量化约束满足问题(QCSP)，使用涉及点、曲线、区域三种类型的空间对象的属性、关系和动作的开放式词汇表。传统的方法是通过计算等价的无量词的代数表达式来求解这类QCSP，其复杂性本质上是双指数的。在这篇文章中，我们研究了一个独立于领域的空间搜索框架，用于解决指定为QCSP的二维空间问题。该框架在图的空间中而不是在代数方程/不等式的空间中搜索解。我们证明了我们方法的正确性，并通过在两个军事应用中执行感知/动作，证明了它比著名的代数方法柱面代数分解更有效。
Diagrammatic reasoning (DR) requires perceiving information from a diagram and modifying/creating objects in a diagram according to problem solving needs. The perceptions and actions in most DR systems are hand-coded for the specific application. The absence of a general framework for executing perceptions/actions poses as a major hindrance to using them opportunistically. Our goal is to develop a framework for executing a wide variety of specified perceptions and actions across tasks/domains without human intervention. We observe that the domain/task-specific perceptions/actions can be transformed into domain/task-independent spatial problems. In our framework, a human problem solver specifies a spatial problem as a quantified constraint satisfaction problem (QCSP) in the real domain using an open-ended vocabulary of properties, relations and actions involving three types of spatial objects – points, curves, regions. Traditional approaches solve such QCSPs by computing the equivalent quantifier-free algebraic expression, the complexity of which is inherently doubly exponential. In this paper, we investigate a domain-independent framework of spatial search for solving 2Dspatial problems specified as QCSPs. The framework searches for the solution in the space of the diagram instead of in the space of algebraic equations/inequalities. We prove the correctness of our approach and show that it is more efficient than cylindrical algebraic decomposition, a well-known algebraic approach, by executing perceptions/actions in two army applications.