Planning under partial observability is one of the most significant and challenging planning problems. It combines the need to deal with belief states, as in conformant planning, with the need for and-or search, typical of conditional planning. In this paper, we tackle the problem of planning under partial observability within the framework of planning via symbolic model checking. We propose a new algorithm for planning under partial observability, able to generate conditional plans that are guaranteed to achieve the goal despite of the uncertainty in the initial condition, the uncertain effects of actions, and the partial observability of the domain. The experimental evaluation compares the heuristic-symbolic algorithm with a recently proposed approach based on a depth-first search (/DFS) style. We show that, while /DFS search may often result in deep plans, and suffers sometimes from inefficiencies resulting from a `bad` initial choice, heuristic-symbolic search, even considering only a fixed simple selection function, constructs plans of better quality, and, for certain classes of problems may significantly improve the efficiency of the search

Conditional Planning under Partial Obserbability as Heuristic-Symbolic Search in Belief Space

Bertoli, Piergiorgio;Cimatti, Alessandro;Roveri, Marco
2001-01-01

Abstract

Planning under partial observability is one of the most significant and challenging planning problems. It combines the need to deal with belief states, as in conformant planning, with the need for and-or search, typical of conditional planning. In this paper, we tackle the problem of planning under partial observability within the framework of planning via symbolic model checking. We propose a new algorithm for planning under partial observability, able to generate conditional plans that are guaranteed to achieve the goal despite of the uncertainty in the initial condition, the uncertain effects of actions, and the partial observability of the domain. The experimental evaluation compares the heuristic-symbolic algorithm with a recently proposed approach based on a depth-first search (/DFS) style. We show that, while /DFS search may often result in deep plans, and suffers sometimes from inefficiencies resulting from a `bad` initial choice, heuristic-symbolic search, even considering only a fixed simple selection function, constructs plans of better quality, and, for certain classes of problems may significantly improve the efficiency of the search
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11582/392
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact