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.