[Proof Complexity] MIAO seminar Thu Jun 1 at 14:00 CET with Malte Helmert: Lower bound functions for optimal classical planning

[Jakob Nordström]

Dear all,

After a long break due to the semester programs at the Simons Institute at UC Berkeley, the MIAO seminars are back. On Thursday June 1 at 14:00, we will have a seminar with Malte Helmert titled "Lower bound functions for optimal classical planning". You find the abstract at the bottom of this message.

We will run this as a hybrid seminar at the University of Copenhagen. Local participants are warmly welcome on UCPH campus --- the exact location will be communicated later. Other participants are equally warmly welcome to join virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can be found at http://www.jakobnordstrom.se/miao-seminars/ . If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Tuesday Jun 1 at 14:00
Lower bound functions for optimal classical planning
(Malte Helmert,  University of Basel)

Optimal classical planning is the problem of finding shortest paths in factored state spaces, i.e., directed graphs that are compactly described by logic-based representations. The leading approaches are based on deriving lower-bound distance estimators a.k.a. "admissible heuristics" from these logic-based representations.

For a long time, the design of admissible heuristics was considered an ad-hoc activity with very little supporting theory. Modern developments, starting with Katz and Domshlak's seminal work on cost partitioning of abstraction heuristics, have changed this perception dramatically, shaping a comprehensive theory of admissible heuristics. In this talk we study these developments and highlight some interesting connections to linear and integer programming.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.jakobnordstrom.se