Reasoning and Plannning with Sensing Actions and Their Applications

感知行为，当执行时改变代理的知识状态而不改变世界。在对世界不完全了解的情况下做计划是必要的。本研究的最初目的是开发一个正式的表征推理和计划与传感行动。要解决的问题包括：在信息不完整的情况下进行计划时，需要什么样的计划？什么时候这样的计划是正确的？在这种情况下，状态空间是什么？我们如何简洁地表示状态？我们如何在传感中描述噪声？我们如何指定目标？有感知的规划的复杂性是什么？这些问题的答案将用于开发更易于处理的规划算法和规划器，并使用有关传感动作的合理（但不一定完整）推理。本研究的另一个重点是在动态领域中使用感知行为来解决诊断问题。根据对不同时间点的一系列观察结果，PI将形成诊断的概念。由于一组特定的观察可能导致多个诊断，因此PI将开发诊断计划的概念，该诊断计划在执行时将导致推理器进行唯一（或较小的一组）诊断。然后，他将研究寻找诊断和构建诊断计划的复杂性，并为可处理子类开发和实现相应的算法。这个项目将导致一种行动理论，允许感知行动，这将使我们能够：开发健全和完整的计划者，以及健全，但不完整，但更容易处理的计划者。它将把代理控制和诊断等应用扩展到不完全世界，影响计算机科学的各个领域，包括移动机器人的高级控制方面，活动数据库和程序验证。

Sensing actions, which when executed change the state of an agent's knowledge without changing the world. are necessary when planning in the presence of incomplete knowledge about the world. The initial aim of this research is to develop a formal characterization of reasoning and planning with sensing actions. Questions to be addressed include: What kind of plans are necessary when planning with incomplete information? When is such a plan correct? What is the state-space in this case? How do we compactly represent states? How do we characterize noise in sensing? How do we specify goals? What is the complexity of planning with sensing? The answers to these questions will be used to develop planning algorithms and planners that are more tractable, and which use a sound (but not necessarily complete) reasoning about sensing actions.Another thrust of this research is to use sensing actions for diagnostic problem solving in dynamic domains. The PI will formulate the notion of a diagnosis, given a set of observations about different time points. Since a particular set of observations may lead to multiple diagnoses, the PI will develop the notion of a diagnostic plan which when executed will lead the reasoner to a unique (or a smaller set of) diagnoses. He will then study the complexity of finding a diagnosis and constructing diagnostic plans, and develop and implement corresponding algorithms for tractable subclasses.This project will lead to a theory of actions that allows sensing actions, which will allow us to: develop sound and complete planners as well as sound, but incomplete, but more tractable planners. It will extend applications such as agent control and diagnosis to the incomplete world, impacting diverse areas of computer science including the high-level control aspects of mobile robots, active databases, and program verification.