Strong planning under partial observability
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
project report helper
Active In SP

Posts: 2,270
Joined: Sep 2010
19-10-2010, 04:27 PM

Strong planning under partial observability

Piergiorgio Bertoli ∗, Alessandro Cimatti, Marco Roveri, Paolo Traverso
ITC-IRST, Via Sommarive 18, 38055 Povo, Trento, Italy
Received 4 April 2004; received in revised form 1 May 2005; accepted 10 January 2006


Rarely planning domains are fully observable. For this reason, the ability to deal with partial observability is one of the most important challenges in planning. In this paper, we tackle the problem of strong planning under partial observability in nondeterministic domains: find a conditional plan that will result in a successful state, regardless of multiple initial states, nondeterministic action effects, and partial observability. We make the following contributions. First, we formally define the problem of strong planning within a general framework for modeling partially observable planning domains. Second, we propose an effective planning algorithm, based on and-or search in the space of beliefs. We prove that our algorithm always terminates, and is correct and complete. In order to achieve additional effectiveness, we leverage on a symbolic, BDD-based representation for the domain, and propose several search strategies. We provide a thorough experimental evaluation of our approach, based on a wide selection of benchmarks. We compare the performance of the proposed search strategies, and identify a uniform winner that combines heuristic distance measures with mechanisms that reduce runtime uncertainty. Then, we compare our planner MBP with other state-of-the art-systems. MBP is able to outperform its competitor systems, often by orders of magnitude.


Very often, planning domains are partially observable and nondeterministic: at execution time, the state of the world can not be completely observed, and actions may have several possible outcomes. In this case, the status of the domain can not be uniquely determined. Planning for nondeterministic and partially observable domains is a significant, well known and difficult problem. It is a significant problem since several realistic applications require to deal with sources of nondeterminism, within the general case of partial observability. The special cases of full observability, where every state variable can be observed at every step, and null observability, where no observation is ever possible, only cover a limited set of realistic situations. Indeed, the problem has been extensively addressed in the literature. Different approaches include extensions to techniques for classical planning, see e.g., , Partially Observable Markov Decision Processes (POMDPs), see e.g., , logical frameworks ,planning based on Quantified Boolean Formulas (QBF), and planning based on symbolic model checking. The problem has been shown to be hard, both theoretically and experimentally. Compared to planning under full observability, planning under partial observability must deal with uncertainty about the state in which the actions will be executed. This makes the search space no longer the set of states of the domain, but its powerset, i.e. the space of “belief states”. Compared to the case of null observability, called conformant planning, plans are no longer sequential, but conditional, in order to represent a conditional course depending on the observations performed at execution time. In this paper, we address the problem of strong planning under partial observability, i.e., the problem of generating conditional plans that are guaranteed to achieve the goal in spite of the nondeterminism and partial observability of the domain. Strong planning can be formalized as a problem of search in the space of a (possibly cyclic) and-or graph induced by the domain [9], where each node in the graph corresponds to the set of possible states for the current situation, i.e., a belief state. Or-nodes correspond to alternative actions that can be applied to a belief state, while andnodes correspond to observations that partition a belief state into subsets for all of which a solution must be found. We present a novel approach to the problem and provide evidence that the approach is well-founded and practical:

for more :->

Important Note..!

If you are not satisfied with above reply ,..Please


So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  computer aided process planning seminar ppt jaseelati 0 242 15-01-2015, 04:20 PM
Last Post: jaseelati
  computer aided process planning ppt jaseelati 0 157 09-01-2015, 02:17 PM
Last Post: jaseelati
  computer aided process planning ppt jaseelati 0 176 05-01-2015, 04:00 PM
Last Post: jaseelati
  computer aided process planning ppt jaseelati 0 103 01-01-2015, 03:30 PM
Last Post: jaseelati
  Survivability Analysis of ad hoc network under attack ppt study tips 0 253 19-08-2013, 04:49 PM
Last Post: study tips
  Deployment Planning Basics study tips 0 220 02-08-2013, 12:49 PM
Last Post: study tips
  Capacity Planning in Repetitive Manufacturing study tips 0 297 22-07-2013, 04:52 PM
Last Post: study tips
  BUSINESS PLANNING AND MODELING FOR BANK ATM SYSTEM study tips 0 316 19-07-2013, 03:54 PM
Last Post: study tips
  Dynamic partial reconfiguration in FPGAs pdf study tips 0 283 19-06-2013, 12:41 PM
Last Post: study tips
  Improved Ant Colony Optimization for Multiobjective Route Planning of Dangerous Goods study tips 0 271 10-06-2013, 03:52 PM
Last Post: study tips