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.