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.