Data Entry: Please note that the research database will be replaced by UNIverse by the end of October 2023. Please enter your data into the system https://universe-intern.unibas.ch. Thanks

Login for users with Unibas email account...

Login for registered users without Unibas email account...

 
Lagrangian Decomposition for Optimal Cost Partitioning
ConferencePaper (Artikel, die in Tagungsbänden erschienen sind)
 
ID 4527423
Author(s) Pommerening, Florian; Röger, Gabriele; Helmert, Malte; Cambazard, Hadrien; Rousseau, Louis-Martin; Salvagnin, Domenico
Author(s) at UniBasel Pommerening, Florian
Röger, Gabriele
Helmert, Malte
Year 2019
Title Lagrangian Decomposition for Optimal Cost Partitioning
Editor(s) Benton, J.; Lipovetzky, Nir; Onaindia, Eva; Smith, David E.; Srivastava, Siddharth
Book title (Conference Proceedings) Proceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS 2019)
Volume 29
Place of Conference Berkeley, CA, USA
Publisher AAAI Press
Pages 338-347
ISSN/ISBN 2334-0843
Abstract Optimal cost partitioning of classical planning heuristics has been shown to lead to excellent heuristic values but is often prohibitively expensive to compute. Lagrangian decomposition and Lagrangian relaxation are classical tools in mathematical programming that apply to optimization problems with a special block structure. We analyze the application of Lagrangian decomposition to cost partitioning in the context of operator-counting heuristics and interpret Lagrangian multipliers as cost functions for the combined heuristics. This allows us to view the computation of an optimal cost partitioning as an iterative process that can be seeded with any cost partitioning and improves over time. We derive an any-time algorithm to compute an optimal non-negative cost partitioning of abstraction heuristics without involving an LP solver. In each iteration, the computation reduces to independent shortest path problems in all abstractions. Finally, we discuss the extension to general cost functions.
URL https://aaai.org/ojs/index.php/ICAPS/article/view/3496/3364
edoc-URL https://edoc.unibas.ch/75020/
Full Text on edoc Available
 
   

MCSS v5.8 PRO. 0.343 sec, queries - 0.000 sec ©Universität Basel  |  Impressum   |    
29/03/2024