Analysis of partial order reduction techniques for automated planning

Abstract: Automated planning is an area of Artificial Intelligence (AI) that is closely related to decision making. Given a planning problem, which is described as an initial state (i.e., a start configuration of the problem), a set of actions, and a goal description, a planning algorithm is concerned with finding a sequence of actions or a strategy for achieving the goal conditions from the initial state. Planning, in all its variations, is a hard problem. Classical planning is one of the simplest forms of planning. Despite its simplicity, it is still computationally intractable. Therefore, planning problems cannot be solved by brute-force algorithms, but rather by goal-directed algorithms that tackle the complexity of planning. Planning as heuristic search is a prominent technique that has been considered in the area of automated planning. However, recent research has shown that planning as heuristic search needs the aid of orthogonal techniques. Partial order reduction is a well-known and reliable approach that has originally been introduced in the area of computer aided verification to tackle the state explosion problem. It is usually used for explicit state-space search to reduce the size of the generated state space. There are two categories of partial order reduction techniques: State reduction and transition reduction techniques. The former are specialized to prune some states that are guaranteed to be uncritical for reaching some final states (e.g., goal states in planning), while the latter are designed to prune only redundant states. Later, new partial order reduction techniques have been proposed for optimal planning algorithms. However, the formal relationships between the previous and later techniques were unclear, and furthermore, some of the novel techniques were faulty. In the context of classical planning, we investigate two variants of a powerful state reduction technique from the area of model checking, called stubborn sets. Furthermore, we propose a new definition of stubborn sets for Fully Observable Non-Deterministic planning (FOND). For classical planning, we show that stubborn sets are completeness and optimality preserving, whereas for FOND planning, we show that they are at least completeness preserving. In addition, we compare between stubborn sets and previous partial order reduction techniques proposed for optimal planning. Moreover, we study a transition reduction technique from the area of model checking, called sleep sets, and classify this method into four main variants. Then, we show the relationship between these variants and the different search algorithms. Precisely, we theoretically investigate which variants are safe for search algorithms like A∗, IDA∗, and breadth-first search. Like stubborn sets, we compare sleep sets with other transition reduction techniques for planning. In addition, we describe a family of generalization to the sleep sets method and evaluate the most general form for optimal planning. Finally, we experimentally evaluate the techniques we propose for planning. In summary, this thesis investigates sound partial order reduction techniques for automated planning, establishes the formal relationships between several partial order reduction techniques, and strengthens the theoretical proof by empirical evaluation

Angaben zum Objekt

• Standort: Deutsche Nationalbibliothek Frankfurt am Main
• Umfang: Online-Ressource
• Sprache: Englisch
• Anmerkungen: Universität Freiburg, Dissertation, 2017

Klassifikation und Themen

• Klassifikation: Mathematik
• Schlagwort: Planning ; Sleep ; Künstliche Intelligenz ; Entscheidungsfindung ; Algorithmus

Beteiligte, Orts- und Zeitangaben

• Ereignis: Veröffentlichung
• (wo): Freiburg
• (wer): Universität
• (wann): 2018
• Urheber: Al-Khazraji, Yusra
• Beteiligte Personen und Organisationen: Nebel, Bernhard ; Albert-Ludwigs-Universität Freiburg. Fakultät für Angewandte Wissenschaften

Weitere Informationen

• DOI: 10.6094/UNIFR/16093
• URN: urn:nbn:de:bsz:25-freidok-160931
• Rechteinformation: Kein Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Letzte Aktualisierung: 15.08.2025, 07:29 MESZ