Font Size: a A A

# Interval computation methods and probabilistic methods for planning and plan checking under uncertainty and incomplete information

Posted on:2002-12-12Degree:Ph.DType:Dissertation
University:The University of Texas at El PasoCandidate:Trejo, Raul AFull Text:PDF
GTID:1462390011992543Subject:Computer Science
Abstract/Summary:
The main problem of planning is to find a sequence of actions that an agent must perform to achieve a given objective. An important part of planning is checking whether a given plan achieves the desired objective. Historically, in AI, the planning and plan checking problems were mainly formulated and solved in a deterministic environment, when the initial state is known precisely and when the results of each action in each state is known (and uniquely determined). In this deterministic case, planning is difficult, but plan checking is straightforward.; In many real-life situations, however, the agent does not have complete information about the initial state of the system. In the best case, the agent may know the probabilities of the different fluents that describe the state of the system; sometimes even such probabilities are unknown and the agent has no information whatsoever about the initial state of some fluents.; Recently, there has been proposal to use ‘sensing’ actions to plan in presence of incompleteness. In this work we use the action description language $A$ proposed in 1993 by M. Gelfond and V. Lifschitz, and its extensions, that allow for sensing actions. In real-life planning, we often also use the knowledge about the system's past behavior. To describe such more realistic planning situations, a special language $L$ was developed in 1997 by C. Baral, M. Gelfond and A. Provetti.; In this work we expand the known results about computational complexity of planning to this more general class of planning problems. The language $A$ allows planning in the situations with complete information. It is known that, if we consider only plans of feasible (polynomial) length, the planning problem for such situations is NP-complete: even checking whether a given objective is attainable from a given initial state is NP-complete. In this work, we show that the planning problem in presence of incompleteness is indeed harder: it belongs to the next level of complexity hierarchy (in precise terms, it is Σ2P-complete). To overcome the complexity of this problem, C. Baral and T. Son have proposed several approximations. We show that under certain conditions, one of these approximations—0-approximation—makes the problem NP-complete (thus indeed reducing its complexity). We also show results about the complexity of planning when the past states are considered.; Then we address the planning problem when initial probabilities of fluents are known. We describe how methods of interval computations can be used to get a feasible approximation to plan checking under probabilistic uncertainty. The resulting method is a natural generalization of 0-approximation. It turns out that some of the resulting probabilistic techniques coincides with heuristically proposed “fuzzy” methods. Thus, we justify these fuzzy heuristics as a reasonable feasible approximation to the (NP-hard) probabilistic problem.; In view of the usefulness of interval computation techniques in planning, we overview these techniques and propose improvements which lead to optimal and sub-optimal interval methods.
Keywords/Search Tags:Planning, Methods, Interval, Problem, Probabilistic, Information, Initial state, Agent
Related items
 1 Study On Interval Analysis Theory And Its Application In Slope Engineering 2 Non-probabilistic Reliability Studies Of Tunnel Lining Systems Based On Interval Theory 3 Research On Characteristic Representation Of Initial State Information And Its Relationship With Life For Electrical Apparatus 4 Research On Operation Strategies And Planning Methods For Multi-type Microgrids Under Uncertainties 5 Structure State Estimation And Damage Detection Based On Interval Analysis Considering Uncertainties 6 Battlefield Multi-agent Systems Analysis And Design Of Collaborative Information Processing 7 Study On The Analysis And Forecasting Methods For High Randomness Electric Load 8 Research On Multi-support Control Of Building Moving Based On Non-probabilistic Interval Set Model 9 Improvement Of Non-probabilistic Reliability Model Considering Interval Variable Data Distribution And Its Application In Bridges 10 Probabilistic analysis of the plastic collapse of random media