Strong planning under partial observability
#1


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



Abstract

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.

Introduction

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 :->
http://portal.acmcitation.cfm?id=1141144
Reply

Important Note..!

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

ASK HERE

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
Popular Searches: strong conclusion for green engine ppt, fokken strong training, mymathlab coursecompass stron, mymathlab coursecompass strong, observability, fundamental aspects of a strong effective team, partial seizure epilepsy,

[-]
Quick Reply
Message
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
  Satellite Image Time Series Analysis Under Time Warping computer girl 0 383 06-06-2012, 05:23 PM
Last Post: computer girl
  Enterprise Resource Planning System for Laptop Manufacturing seminar class 0 1,580 29-03-2011, 09:25 AM
Last Post: seminar class
  Fast Redundant Binary Partial Product Generators for Booth Multiplication electronics seminars 0 2,515 09-01-2010, 05:45 PM
Last Post: electronics seminars
  A logic programming approach to knowledge state planning nit_cal 0 1,086 30-10-2009, 03:06 PM
Last Post: nit_cal
  IMAGE PROCESSING UNDER EDGE DETECTION AND CORRECTION ALGORITHM FOR 3D CT IMAGES seminar projects crazy 0 1,968 13-06-2009, 07:02 PM
Last Post: seminar projects crazy
  IMAGE PROCESSING UNDER EDGE DETECTION AND CORRECTION ALGORITHM FOR 3D CT IMAGES Computer Science Clay 0 2,076 07-06-2009, 01:17 AM
Last Post: Computer Science Clay

Forum Jump: