Domain-Independent planning is known to be a very hard search problem, and in the last three decades many search techniques and heuristics have been developed with the aim of efficiently solving such a task. These techniques and heuristics include the usage of landmarks, which are logical expressions consisting of facts that become true or actions that are executed in any solution plan. We propose the usage of landmarks for speeding up the search of the planner LPG, a system implementing a planning approach based on the use of local search in the space of the action graphs of the planning problem. The results of an experimental evaluation of the proposed techniques show that these techniques can improve the performance of LPG, obtaining a planning system that performs similarly to the state-of-the-art planner LAMA. Moreover, we introduce and experimentally evaluate the concept of “quasi-landmarks”; these are facts that are likely to become true in every solution plan, or facts that must become true in a subset of the solution plans.
BlumA. and FurstM., Fast planning through planning graph analysis, Artificial Intelligence90 (1997), 281–300.
2.
BonisoliA., GereviniA.E., SaettiA. and SerinaI., A privacypreserving model for the multi-agent propositional planning problem. In:
SchaubT.,
FriedrichG.,
O’SullivanB. (eds.) ECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Reublic. Frontiers in Artificial Intelligence and Applications, vol. 263, pp. 973–974. IOS Press, (2014).
3.
BonisoliA., GereviniA.E., SaettiA. and SerinaI., Effective plan retrieval in case-based planning for metric-temporal problems, J Exp Theor Artif Intell27(5) (2015), 603–647.
4.
BorrajoD., RoubíčckováA. and SerinaI., Progress in case-based planning. ACM Computing Surveys In press, (2014).
5.
FoxM., GereviniA., LongD. and SerinaI., Plan stability: Replanning versus plan repair. In: Proceedings of the 16th International Conference on Automated Planning and Scheduling. AAAI Press, Cumbria, UK (2006).
6.
FoxM. and LongD., PDDL2.1: An extension to PDDL for expressing temporal planning domains, Journal of Artificial Intelligence Research (JAIR)20 (2003), 61–124.
7.
GarridoA., MoralesL. and SerinaI., Using ai planning to enhance e-learning processes. In:
McCluskeyL.,
WilliamsB.,
SilvaJ.R.,
BonetB. (eds.) ICAPS. AAAI (2012).
8.
GarridoA., MoralesL. and SerinaI., On the use of case-based planning for e-learning personalization, Expert Syst Appl60 (2016), 1–15.
9.
GereviniA., KuterU., NauD., SaettiA. and WaisbrotN., Combining domain-independent planning and HTN planning: The Duet planner. In: Proceedings of the Eighteenth European Conference on Artificial Intelligence (ECAI-08), (2008).
10.
GereviniA., SaettiA. and SerinaI., Planning through stochastic local search and temporal action graphs, Journal of Artificial Intelligence Research (JAIR)20 (2003), 239–290.
11.
GereviniA., SaettiA. and SerinaI., An approach to temporal planning and scheduling in domains with predictable exogenous events, Journal of Artificial Intelligence Research (JAIR)25 (2006), 187–231.
12.
GereviniA., SaettiA. and SerinaI., An approach to efficient planning with numerical fluents and multi-criteria plan quality, Artificial Intelligence172(8-9) (2008), 899–944.
13.
GereviniA. and SerinaI., LPG: A planner based on local search for planning graphs with action costs. In: Proceedings of the 6th International Conference on Artificial Intelligence Planning and Scheduling (AIPS-02). pp. 281–290. AAAI Press/MIT Press, (2002).
14.
GereviniA., SerinaI., SaettiA. and SpinoniS., Local search techniques for temporal planning in LPG. In: Proceedings of the 13th International Conference on Automated Planning Scheduling (ICAPS03). pp. 62–71. AAAI Press, (2003).
15.
GereviniA., RoubíčckováA.,
SaettiA. and SerinaI., Offline and online plan library maintenance in case-based planning. In: Proceedings of the 13th Conference of the Italian Association for Artificial Intelligence. Springer, Turin, Italy, (2013).
16.
GereviniA., RoubíčkováA.,
SaettiA. and SerinaI., On the plan-library maintenance problem in a case-based planner. In: Proceedings of the 21st International Conference on Case- Based Reasoning, Springer, Saratoga Spring, NY, (2013).
17.
GereviniA. and SerinaI., Fast plan adaptation through planning graphs: Local and systematic search techniques. In: Proceedings of the 5th International Conference on Artificial Intelligence Planning Systems. AAAI Press, Breckenridge, CO, (2000).
18.
GnadD., SteinmetzM., JanyM., HoffmannJ., SerinaI. and GereviniA., Partial delete relaxation, unchained: On intractable red-black planning and its applications. In:
BaierJ.A., BoteaA. (eds.) Proceedings of the Ninth Annual Symposium on Combinatorial Search, SOCS 2016, Tarrytown, NY, USA, July 6-8, 2016. pp. 45–53. AAAI Press, (2016).
19.
HelmertM. and DomshlakC., Landmarks, critical paths and abstractions: What’s the difference anyway? In: GereviniA.,
HoweA.E.,
CestaA.,
RefanidisI. (eds.) Proceedings of the 19th International Conference on Automated Planning and Scheduling, ICAPS 2009, Thessaloniki, Greece, September 19-23, 2009. AAAI, (2009).
20.
HoffmannJ. and EdelkampS., The deterministic part of IPC-4: An overview, Journal of Artificial Intelligence Research (JAIR)24 (2005), 519–579.
21.
HoffmannJ., PorteousJ. and SebastiaL., Ordered landmarks in planning, J Artif Int Res22(1) (2004), 215–278.
22.
JimeenezS., FernãndezF. and BorrajoD., The PELA architecture: Integrating planning and learning to improve execution. In: Proceedings of the Twenty-Third National Conference on Artificial Intelligence (AAAI-08), (2008).
23.
KarpasE. and DomshlakC., Cost-optimal planning with landmarks. In:
BoutilierC. (ed.) IJCAI 2009Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009. pp. 1728–1733, (2009).
24.
KeyderE., RichterS. and HelmertM., Sound and complete landmarks for and/or graphs. In: Proceedings of the 2010 Conference on ECAI 2010:19th European Conference on Artificial Intelligence. pp. 335–340. IOS Press, Amsterdam, The Netherlands, The Netherlands, (2010).
25.
KolobovA., MausamM. and WeldD., Determinize, solve, and generalize: Classical planning for MDP heuristics, ICAPS- 09 Workshop on Heuristics for Domain-independent Planning, (2009).
26.
LiberatoreP., On the complexity of case-based planning, Journal of Experimental and Theoretical Artificial Intelligence17(3) (2005), 283–295.
27.
LongD. and FoxM., The 3rd International Planning Competition: Results and analysis, Journal of Artificial Intelligence Research (JAIR)20 (2003), 1–59.
28.
MoralesL., CastilloL., Fernandez-OlivaresJ. and Gonzalez-A., Ferrer, Automatic generation of user adapted learning designs: An AI-planning proposal. In: Proceedings of the Fifth International Conference on Adaptive Hypermedia and Adaptive Web-Based Systems (AH-08), (2008).
29.
NguyenT., DoM.B., KambhampatiD. and SrivastaB., Planning with partial preference models. In: Twenty-first International Joint Conference on Artificial Intelligence (IJCAI-09),(2009).
30.
NguyenT.A., DoM.B., GereviniA., SerinaI., SrivastavaB. and KambhampatiS., Generating diverse plans to handle unknown and partially known user preferences, Artificial Intelligence190 (2012), 1–31.
31.
OlayaA.G., LópezC.L. and JiménezS.C., Deterministic part of the 7th International Planning Competition IPC7. In: http://www.plg.inf.uc3m.es/ipc2011-deterministic. ICAPS, (2011).
32.
PorteousJ., SebastiaL., HoffmannJ., On the extraction, ordering and usage of landmarks in planning. In: European Conference of Planning (ECP’01), (2001), pp. 37–48.
33.
RichterS. and WestphalM., The LAMA planner: Guiding costbased anytime planning with landmarks. CoRR abs/1401.3839, (2014), http://arxiv.org/abs/1401.3839
34.
SelmanB., KautzH. and CohenB., Noise strategies for improving local search. In: Proceedings 12th National Conference on Artificial Intelligence. Morgan Kaufmann, Seattle, WA, (1994).
35.
SerinaI., Kernel functions for case-based planning, Artificial Intelligence174(16-17) (2010), 1369–1406.
36.
SrivastavaB., NguyenT.A., GereviniA., KambhampatiS., DoM.B. and SerinaI., Domain independent approaches for finding diverse plans. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence, (2007).
37.
VernhesS., InfantesG. and VidalV., Problem splitting using heuristic search in landmark orderings. In: IJCAI’13 (2013), pp. 1–1.
38.
VernhesS., InfantesG. and VidalV., Problem splitting using heuristic search in landmark orderings. In:
RossiF. (ed.) IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, IJCAI/ AAAI(2013).
39.
VrakasD., HatziO., BassiliadesN., AnagnostopoulosD. and VlahavasI., A visual programming tool for designing planning problems for semantic web service composition. In: Visual Languages for Interactive Computing: Definitions and Formalizations, (2008).
40.
ZhuL. and GivanR., Landmark Extraction via Planning Graph Propagation. In: Printed Notes of ICAPS’03 Doctoral Consortium (June 2003), trento, Italy.
