Mark Iwen, Amol D. Mali · 2003
Significant advances in plan synthesis under classical assumptions have occurred in the last seven years. Such efficient planners are all centralized planners. One very major development among these is the Graphplan planner. Its popularity is clear from its several efficient adaptations/extensions. Since several practical planning problems are solved in a distributed manner it is important to adapt Graphplan to distributed planning. This involves dealing with significant challenges like decomposing the goal and set of actions without losing completeness. We report two sound two-agent planners DGP (distributed Graphplan) and IG-DGP (interaction graph-based DGP). Decomposition of goal and action set in DGP is carried out manually and in IG-DGP it is carried out automatically based on a new representation called interaction graphs. Our empirical evaluation shows that both these distributed planners are faster than Graphplan. IG-DGP is orders of magnitude faster than Graphplan. IG-DGP benefits significantly from interaction graphs which allow decomposition of a problem into fully independent subproblems under certain conditions. IG-DGP is a hybrid planner in which a centralized planner processes a problem until it becomes separable into two independent subproblems that are passed to a distributed planner This paper also shows that advances in centralized planning can significantly benefit distributed planners.
Cited by 14
Social Science Microcomputer Review · 1985
Graphplan is an integrated spreadsheet and graphics package with statistical and sorting capabilities. The package supports pie charts, bar graphs, time-series plots, horizontal bars, and scatter diagrams. It is relatively easy to use and it quickly generates charts and tables. Major drawbacks include its exclusive reliance on the spreadsheet format and lack of capability to exchange data with other programs (except that Graphplan reports may be sent to a word processor).
Cited by 0
Subbarao Kambhampati Eric, Eric Parker, Eric Lambrecht · 1997
We provide a reconstruction of Blum and Furst's Graphplan algorithm, and use the reconstruction to extend and improve the original algorithm in several ways. In our reconstruction, the process of growing the planning-graph and inferring mutex relations corresponds to doing forward state-space refinement over disjunctively represented plans. The backward search phase of Graphplan corresponds to solving a binary dynamic constraint satisfaction problem. Our reconstruction sheds light on the sources of strength of Graphplan. We also use the reconstruction to explain how Graphplan can be made goaldirected, how it can be extended to handle actions with conditional effects, and how backward state-space refinement can be generalized to apply to disjunctive plans. Finally, we discuss how the backward search phase of Graphplan can be improved by applying techniques from CSP literature, and by teasing apart planning and scheduling (resource allocation) phases in Graphplan. 1.Introduct...
Cited by 0
Alfredo Milani, Stefano Marcugini, Marco Baioletti · 1998
Completion of partial plans is a subtask for many planning techniques such as plan reusing, replanning and accomplishing complex user goals. The new generation of fast planners such as Graphplan, Satplan and others, is characterized by very efficent planning algorithms which exploit techniques of multiple plans representation. Unfortunately it is fairly difficult to give Graphplan a partial plan fragment to complete, because the internal plan network representation, only represents ordered by levels and complete plans. On the other hand it is very easy and straigthforward to provide an initial partial plan to complete to a planner like UCPOP, because its planning algorithm completes a partial initial plan in the internal representation. We present an original technique for using Graphplan in order to solve partial plan completion problems. The technique, called domain embedding, modifies the problem domain in order to induce only solutions which are completion of the given partial pl...
Cited by 0
Eric Parker · Lecture notes in computer science · 2000
Cited by 11
Manifest Podcast · Bulletin of Miscellaneous Information (Royal Gardens Kew) · 2013
Cited by 0
Joseph Zalaket, Guy Camilleri · 2007
Due to its compact structure Graphplan has founded a new generation of planners. In addition to its performance in solving planning problems, many heuristics have been derived using its planning graph structure. Several extensions have been made to the Graphplan or to its planning graph to enhance their performance and to make them able to solve new type of knowledge like temporal and resources. The most of these extensions have handled the temporal and numeric resource knowledge as a peripheral part joined to the Graphplan structure. Our observation to the Graphplan structure showed us that this structure is able to deal with all kind of knowledge by the same way as with symbolic knowledge. Even more, this structure is able to handle black box functions which manipulate all kind of data. In this paper, we present a variation of Graphplan which supports the execution of external functions for numeric knowledge update. This variation allows Graphplan to run all kind of knowledge using its original planning graph as the base of the data structure.
Cited by 0
Subbarao Kambhampati, Eric Parker, Eric Lambrecht · Lecture notes in computer science · 1997
Cited by 78
Michel Cayrol, P. Régnier, Vincent Vidal · Artificial Intelligence · 2001
Cited by 23
Massimiliano Garagnani Department · 2007
this paper, an extension of Graphplan is proposed, which allows the system to solve planning problems containing domain axioms (in the form p 1 p 2 ... p n c) without employing conditional effects and without cluttering the planning state with extra deduction facts.
Cited by 0
Blum, Avrim, Langford, John C. · KiltHub Repository · 2000
The Graphplan planner has enjoyed considerable success as a planning algorithm for classical STRIPS domains. In this paper we explore the extent to which its representation can be used for probabilistic planning. In particular, we consider an MDP-style framework in which the state of the world is known but actions are probabilistic, and the objective is to produce a finite horizon contingent plan with highest probability of success within the horizon. We describe two extensions of Graphplan in this direction. The first, PGraphplan, produces an optimal contingent plan. It typically suffers a performance hit compared to Graphplan but still appears to be fast compared with other approaches to probabilistic planning problems. The second, TGraphplan, runs at essentially the same speed as Graphplan, but produces potentially sub-optimal policies: TGraphplan’s policy selects the first action on the highest probability trajectory from its current state to the goal. Ideally, we would like an optimal planner for probabilistic domains with the same speed that Graphplan would have if the domain were made deterministic. By comparing the speed and quality of these two planners to each other and to other existing planners, we are able to estimate how far off we are from our ideal. PGraphplan is based on a forward-chaining search, unlike the backward-chaining search of the standard Graphplan algorithm. Thus, one focus of this paper is exploring the extent to which Graphplan’s representation can be used to speed up forward search in addition to the backward search for which it was originally intended.
Cited by 0Open access
2008
Graphplan (Blum & Furst 1995) has proved a popular and successful basis for a succession of extensions. An extension to handle temporal planning is a natural one to consider, because of the seductively time-like structure of the layers in the plan graph. TGP (Smith & Weld 1999) and TPSys (Garrido, Onaindía, & Barber 2001; Garrido, Fox, & Long 2002) are both examples of temporal planners that have exploited the Graphplan foundation. However, both of these systems (including both versions of TPSys) exploit the graph to represent a uniform flow of time. In this paper we describe an alternative approach, in which the graph is used to represent the purely logical structuring of the plan, with temporal constraints being managed separately (although not independently). The approach uses a linear constraint solver to ensure that temporal durations are correctly respected. The resulting planner offers an interesting alternative to the other approaches, offering an important extension in expressive power.
Cited by 0
Yuhong Yan, Pascal Poizat, Ludeng Zhao · 2010
Service composition is nowadays mainly seen as a once-for-all activity. Supporting a dynamic service world, where both available services and needs may change, requires runtime adaptive features for service composition. In this paper we propose a repair technique for internal composition adaptation, as opposed to external adaptation. Moreover, setting up our proposal in the planning framework, we compare our repair technique with reference to re-composition, that is re-planning.
Cited by 24
Avrim Blum, John Langford · Lecture notes in computer science · 2000
Cited by 126Open access
Massimiliano Garagnani · 2007
this paper, an extension of Graphplan is proposed, which allows the system to solve planning problems containing domain axioms (in the form p 1 p 2 ... p n c) without employing conditional effects and without cluttering the planning state with extra deduction facts.
Cited by 0
Giroleti, Fernando Fuentes, Ramon Fraga Pereira · Research Explorer (The University of Manchester) · 2013
Inteligencia Articial (IA) e uma area da Ciencia da Computacao que tem como objetivo estudar e simular comportamentos de agentes 1 inteligentes, e possui diversas areas de aplicacao. Por exemplo: . Aprendizagem; . Automacao industrial; . Banco de dados dedutivos e mineracao de dados; . Escalonamento de tarefas; . Jogos; . Otimizacao e controle de processos; . Planejamento; . Sistemas especialistas. Sistemas de IA [17] funcionam de forma organizada e inteligente, ou seja, sao capazes de lidar com problemas complexos buscando aprender e aplicar o conhecimento adquirido reagindo rapido e adequadamente as novas situacoes. A subarea de IA que sera explorada neste trabalho e a de planejamento automatizado em ambientes deterministicos e completamente observaveis. Planejamento esta diretamente ligado ao raciocinio: e uma forma de escolher e organizar acoes perante situacoes, ou seja, escolhas que seguem condicoes para atingir objetivos. O ser humano possui uma importante habilidade, que e a capacidade de planejar suas acoes a m de levar a um determinado objetivo. Em IA, planejamento tambem e de suma importância, o qual esta relacionado a problemas de logistica, agentes inteligentes/deliberativos, planejamento de processos industriais, escalonamento, jogos de estrategia, e etc. Ao longo dos anos, a area de IA passou por transformacoes, onde muitas delas abrangem novas tecnicas para resolucao de determinados tipos de problema. Em 1995, Avrim Blum e Merrick Furst desenvolveram o GraphPlan : um algoritmo de planejamento automatico que realiza renamentos sucessivos em uma estrutura de dados em forma de grafo. O GraphPlan vem inuenciando no desenvolvimento de diversos algoritmos de planejamento ate hoje. Desde entao, muitos pesquisadores estudaram a ideia aplicando novos conceitos sobre ela (otimizacoes, alteracoes pontuais, tecnicas diversas, etc.) surgindo, assim, novos aprimoramentos a partir do GraphPlan original.
Cited by 0Open access
Daniel Weld, Corin R. Anderson, David E. Smith · 1998
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. 1 Introduction Classical planners make the unrealisti...
Cited by 0
Yu Han, Gu W.-X., Y. B. Li et al. · 2006
Cited by 0
Maria Fox, Derek Long · Strathprints: The University of Strathclyde institutional repository (University of Strathclyde) · 2002
Cited by 12
2008
We consider the problem of planning optimally in potentially concurrent probabilistic domains: actions have probabilistic effects and may execute in parallel under certain conditions; we seek a contingency plan that maximises the probability of reaching the goal. The Graphplan framework has proven to be highly successful at solving classical planning problems, but has not previously been applied to probabilistic planning in its entirety. We present an extension of the full framework to probabilistic domains that demonstrates a method of efficiently finding optimal contingency plans using a goal regression search. Paragraph, the resulting planner, is competitive with the state of the art, producing acyclic or cyclic plans that optionally exploit a problem’s potential for concurrency.
Cited by 0