More Web Proxy on the site http://driver.im/

Article

Extending Graphplan to handle uncertainty and sensing actions

Authors:

Daniel S. Weld,

Corin R. Anderson,

David E. SmithAuthors Info & Claims

AAAI '98/IAAI '98: Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence

Pages 897 - 904

Published: 01 July 1998 Publication History

Abstract

If an agent does not have complete information about the world-state, it must reason about alternative possible states of the world and consider whether any of its actions can reduce the uncertainty. Agents controlled by a contingent planner seek to generate a robust plan, that accounts for and handles all eventualities, in advance of execution. Thus a contingent plan may include sensing actions which gather information that is later used to select between different plan branches. Unfortunately, previous contingent planners suffered defects such as confused semantics, incompleteness, and inefficiency. In this paper we describe SGP, a descendant of Graphplan that solves contingent planning problems. SGP distinguishes between actions that sense the value of an unknown proposition from those that change its value. SGP does not suffer from the forms of incompleteness displayed by CNLP and Cassandra. Furthermore, SGP is relatively fast.

References

[1]

Blum, A., and Furst, M. 1997. Fast planning through planning graph analysis. J. Artificial Intelligence 90(1-2):281-300.

[2]

Draper, D., Hanks, S., and Weld, D. 1994. Probabilistic planning with information gathering and contingent execution. In Proc. 2nd Intl. Conf. AI Planning Systems .

[3]

Etzioni, O., Hanks, S., Weld, D., Draper, D., Lesh, N., and Williamson, M. 1992. An approach to planning with incomplete information. In Proc. 3rd Int. Conf. on Principles of Knowledge Representation and Reasoning , 115-125.

[4]

Fagin, R., Halpern, J., Moses, Y., and Vardi, M. 1995. Reasoning about Knowledge . Cambridge, Mass.: MIT Press.

[5]

Gazen, B., and Knoblock, C. 1997. Combining the expressivity of UCPOP with the efficiency of Graphplan. In Proc. 4th European Conference on Planning .

[6]

Genesereth, M., and Nourbakhsh, I. 1993. Time-saving tips for problem solving with incomplete information. In Proc. 11th Nat. Conf. AI , 724-730.

[7]

Goldman, R. P. and Boddy, M. S. 1994. Conditional Linear Planning. In Proc. 2nd Intl. Conf. AI Planning Systems , 80-85.

[8]

Kaelbling, L. P. 1988. Goals as parallel program specifications. In Proc. 7th Nat. Conf. AI . Morgan Kaufmann.

[9]

Koehler, J., Nebel, B., Hoffmann, J., and Dimopoulos, Y. 1997. Extending planning graphs to an ADL subset. In Proc. 4th European Conference on Planning .

[10]

McDermott, D. 1987. A critique of pure reason. Computational Intelligence 3:151-160.

[11]

Mittal, S., and Falkenhainer, B. 1990. Dynamic constraint satisfaction problems. In Proc. 8th Nat. Conf. AI , 25-32.

[12]

Peot, M., and Smith, D. 1992. Conditional Nonlinear Planning. In Proc. 1st Intl. Conf. AI Planning Systems , 189-197.

[13]

Pryor, L., and Collins, G. 1996. Planning for contingencies: A decision-based approach. J. Artificial Intelligence Research .

[14]

Schoppers, M. 1987. Universal plans for reactive robots in unpredictable environments. In Proc. 10th Int. Joint Conf. AI , 1039-1046.

[15]

Smith, D., and Weld, D. 1998. Conformant Graphplan. In Proc. 15th Nat. Conf. AI .

[16]

Warren, D. 1976. Generating Conditional Plans and Programs. In Proceedings of AISB Summer Conference , 344-354.

Cited By

Bozzano MCimatti ARoveri M(2021)A Comprehensive Approach to On-board Autonomy Verification and ValidationACM Transactions on Intelligent Systems and Technology10.1145/347271512:4(1-29)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3472715
Balaban EJohnson SKochenderfer M(2019)Unifying system health management and automated decision makingJournal of Artificial Intelligence Research10.1613/jair.1.1136665:1(487-518)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1613/jair.1.11366
Hagen SKemper AChemouil PMehaoua AFestor OLupu E(2011)A performance and usability comparison of automated planners for IT change planningProceedings of the 7th International Conference on Network and Services Management10.5555/2147671.2147694(143-151)Online publication date: 24-Oct-2011
https://dl.acm.org/doi/10.5555/2147671.2147694
Show More Cited By

Index Terms

Extending Graphplan to handle uncertainty and sensing actions

Recommendations

Conformant Graphplan
AAAI '98/IAAI '98: Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence

Planning under uncertainty is a difficult task. If sensory information is available, it is possible to do contingency planning - that is, develop plans where certain branches are executed conditionally, based on the outcome of sensory actions. However, ...
Replanning in domains with partial information and sensing actions

Replanning via determinization is a recent, popular approach for online planning in MDPs. In this paper we adapt this idea to classical, non-stochastic domains with partial information and sensing actions, presenting a new planner: SDR (Sample, ...
Distributed Graphplan
ICTAI '02: Proceedings of the 14th IEEE International Conference on Tools with Artificial Intelligence

Significant advances in plan synthesis under classical assumptions have occurred in last seven years. All such efficient planners are centralized planners. One very major development among these is the Graphplan planner. Its popularity is clear from its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

AAAI '98/IAAI '98: Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence

July 1998

1218 pages

ISBN:0262510987

Chairmen:
Jack Mostow
Carnegie Mellon Univ., Pittsburgh, PA
,
Charles Rich
Mitsubishi Electric Research Lab
,
Bruce Buchanan
Mitsubishi Electric Research Lab

Publisher

American Association for Artificial Intelligence

United States

Publication History

Published: 01 July 1998

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bozzano MCimatti ARoveri M(2021)A Comprehensive Approach to On-board Autonomy Verification and ValidationACM Transactions on Intelligent Systems and Technology10.1145/347271512:4(1-29)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3472715
Balaban EJohnson SKochenderfer M(2019)Unifying system health management and automated decision makingJournal of Artificial Intelligence Research10.1613/jair.1.1136665:1(487-518)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1613/jair.1.11366
Hagen SKemper AChemouil PMehaoua AFestor OLupu E(2011)A performance and usability comparison of automated planners for IT change planningProceedings of the 7th International Conference on Network and Services Management10.5555/2147671.2147694(143-151)Online publication date: 24-Oct-2011
https://dl.acm.org/doi/10.5555/2147671.2147694
Nam WAlur R(2010)Active learning of plans for safety and reachability goals with partial observabilityIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics10.1109/TSMCB.2009.202565740:2(412-420)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1109/TSMCB.2009.2025657
Galuszka A(2009)Moving containers in small terminal as STRIPS planning problemProceedings of the 9th WSEAS international conference on Simulation, modelling and optimization10.5555/1627368.1627420(248-253)Online publication date: 3-Sep-2009
https://dl.acm.org/doi/10.5555/1627368.1627420
da Costa Pereira CTettamanzi A(2009)Reasoning about actions with imprecise and incomplete state descriptionsFuzzy Sets and Systems10.1016/j.fss.2008.11.019160:10(1383-1401)Online publication date: 15-May-2009
https://dl.acm.org/doi/10.1016/j.fss.2008.11.019
Shi LSun JLu SYin M(2009)Flexible planning using fuzzy description logicsApplied Soft Computing10.1016/j.asoc.2008.03.0139:1(142-148)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.1016/j.asoc.2008.03.013
Brenner MNebel B(2009)Continual planning and acting in dynamic multiagent environmentsAutonomous Agents and Multi-Agent Systems10.1007/s10458-009-9081-119:3(297-331)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1007/s10458-009-9081-1
Marquardt FUhrmacher AWiberg MZaslavsky A(2008)Evaluating AI planning for service composition in smart environmentsProceedings of the 7th International Conference on Mobile and Ubiquitous Multimedia10.1145/1543137.1543146(48-55)Online publication date: 3-Dec-2008
https://dl.acm.org/doi/10.1145/1543137.1543146
Zang PMehta MMateas MRam A(2007)Towards runtime behavior adaptation for embodied charactersProceedings of the 20th international joint conference on Artifical intelligence10.5555/1625275.1625527(1557-1562)Online publication date: 6-Jan-2007
https://dl.acm.org/doi/10.5555/1625275.1625527
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents