Homomorphisms of Lifted Planning Tasks: The Case for Delete-Free Relaxation Heuristics

Introduction Delete Relaxation h + Heuristic h add and h max Relaxed Plan Heuristic FDR Conclusion References Agenda 1 Introduction 2 The Delete Relaxation 3 What We Really Want is h + 4 The Additive and Max Heuristics 5 The Relaxed Plan Heuristic 6 What about FDR Planning? 7 Conclusion Álvaro Torralba, Cosmina Croitoru AI Planning Chapter 9: Delete Relaxation Heuristics 2/65 Introduction Delete Relaxation h + Heuristic h add and h max Relaxed Plan Heuristic FDR Conclusion References We Need Heuristic Functions! → Delete relaxation is a method to relax planning tasks, and thus automatically compute heuristic functions h. We cover the 4 different methods currently known: path heuristics: Done. → Chapter 8 Delete relaxation: → This Chapter, and Chapter 10 Abstractions: → Chapter 11-13 Landmarks: → Chapter 14 → Each of these have advantages and disadvantages. (We will do a formal comparison in Chapter 17.) → Delete relaxation is very wide-spread, and highly successful for satisficing planning! See Conclusion section and Chapter 21. Álvaro Torralba, Cosmina Croitoru AI Planning Chapter 9: Delete Relaxation Heuristics 4/65 Pretending Things Can Only Get Better "What was once true remains true forever." Relaxed world: (after) Álvaro Torralba, Cosmina Croitoru AI Planning Chapter 9: Delete Relaxation Heuristics 5/65 → Relaxed plan for this task? getTiger , jumpTiger getTiger , tameTiger , jumpTamedTiger works as well, but the previous one is "better" :-) Álvaro Torralba, Cosmina Croitoru AI Planning Chapter 9: Delete Relaxation Heuristics 9/65 Proof. (i) is trivial. (ii) by induction over the length n of a. Base case n = 0 is trivial. Inductive case n → n + 1 follows directly from induction hypothesis and the definition of s a . → It is always better to have more facts true.