Devolopment of algorithms and reasoning techniques for planning under partial observability. Associated theoretical analysis and comparison of algorithms

该研究项目解决了在具有不确定性和部分可观测性的复杂环境中，当行动的影响不能明确地预测并且环境可以不完全观察时所面临的规划问题。为了实现既定的目标，需要制定计划，以决定采取哪些行动。智能自主人类、动物、机器人和软件代理需要它来确保在复杂的不可预测环境中的理性行为。首先，研究了状态空间中的正则性的利用，最显著的是对称性和动作之间缺乏相关性。对称性产生于几个可互换的物体的存在，并导致大而规则的状态空间。类似地，当某些动作之间没有依赖关系时，算法可以限制到结构更简单的计划，从而导致巨大的效率收益。第二个主题是以简洁的分解形式表示在计划构建过程中生成的多组子计划。部分可观测性算法中的一个主要问题是可能需要非常多的分支程序类计划。通过以紧凑的方式表示这些集合，可以获得很大的效率收益。

The research project addresses the planning problem faced in complex environments with nondeterminism and partial observability when the effects of actions cannot be unambiguously predicted and the environment can be incompletely observed. Planning is needed for deciding which actions to take in order to achieve given goals. It is needed by intelligent autonomous humans, animals, robots and software agents for guaranteeing rational behavior in complex unpredictable environments. First, exploitation of regularities in the state space, most notably symmetries and the lack of dependencies between actions, is investigated. Symmetries arise in the presence of several interchangeable objects, and lead to big but regular state spaces. Similarly, when there are no dependencies between certain actions, algorithms can restrict to plans with a simpler structure, thereby leading to big efficiency gains. The second topic is the representation of sets of subplans generated during plan construction in a succinct factored form. A main problem in algorithms for partial observability is the very high number of branching program-like plans potentially needed. By representing these sets in a compact way, big efficiency gains can be obtained.