LPG swMATH ID: 20690 Software Authors: Alfonso E. Gerevini , Alessandro Saetti, Ivan Serina, Mauro Vallati Description: LPG: A planner based on local search for planning graphs. LPG (Local search for Planning Graphs) is a planner based on local search and planning graphs that handles PDDL2.1 domains involving numerical quantities and durations. The system can solve both plan generation and plan adaptation problems. The basic search scheme of LPG was inspired by Walksat, an efficient procedure to solve SAT-problems. The search space of LPG consists of ”action graphs”, particular subgraphs of the planning graph representing partial plans. The search steps are certain graph modifications transforming an action graph into another one. LPG exploits a compact representation of the planning graph to define the search neighborhood and to evaluate its elements using a parametrized function, where the parameters weight different types of inconsistencies in the current partial plan, and are dynamically evaluated during search using discrete Lagrange multipliers. The evaluation function uses some heuristics to estimate the ”search cost” and the ”execution cost” of achieving a (possibly numeric) precondition. Action durations and numerical quantities (e.g., fuel consumption) are represented in the actions graphs, and are modeled in the evaluation function. In temporal domains, actions are ordered using a ”precedence graph” that is maintained during search, and that takes into account the mutex relations of the planning graph. The system can produce good quality plans in terms of one or more criteria. This is achieved by an anytime process producing a sequence of plans, each of which is an improvement of the previous ones in terms of its quality. LPG is integrated with a best-first algorithm similar to the one used by FF. The system can automatically switch to best-first search after a certain number of search steps and ”restarts” have been performed. Finally, LPG can be used as a preprocessor to produce a quasi-solution that is then repaired by ADJ, a plan-analysis technique for fast plan-adaptation. Homepage: http://lpg.unibs.it/lpg/ Related Software: Graphplan; PDDL; Walksat; SAPA; STAN; VHPOP; AltAlt; MiniSat; UCPOP; TensorFlow; UPC++; AlexNet; AutoFolio; HPOlib; auto-sklearn; AClib; OpenTuner; Lingeling; SMAC; Auto-WEKA Cited in: 12 Publications all top 5 Cited by 36 Authors 1 Baioletti, Marco 1 Bartlett, Rodney J. 1 Byrd, Jason 1 Chen, Yixin 1 Coles, Andrew 1 Dasgupta, Pallab 1 Eggensperger, Katharina 1 Fox, Maria 1 Gerevini, Alfonso Emilio 1 Ghassem-Sani, Gholamreza 1 Ghosh, Kamalesh 1 Halsey, Keith 1 Hoos, Holger H. 1 Howe, Adele E. 1 Hutter, Frank 1 Jin, Kebing 1 Kambhampati, Subbarao 1 Komenda, Antonín 1 Leyton-Brown, Kevin 1 Lindauer, Marius 1 Long, Derek 1 Mahjoob, Ali 1 Milani, Alfredo 1 Poggioni, Valentina 1 Rankooh, Masood Feyzbakhsh 1 Roberts, Mark 1 Rossi, Fabio 1 Saetti, Alessandro 1 Sanders, Beverly A. 1 Serina, Ivan 1 Smith, Amanda P. 1 Štolba, Michal 1 Wah, Benjamin W.-S. 1 Wan, Hai 1 Xiao, Zhanhao 1 Zhuo, Hankz Hankui Cited in 5 Serials 5 Artificial Intelligence 2 Annals of Mathematics and Artificial Intelligence 1 Journal of Automated Reasoning 1 Machine Learning 1 The Journal of Artificial Intelligence Research (JAIR) Cited in 2 Fields 12 Computer science (68-XX) 1 Quantum theory (81-XX) Citations by Year