Artificial Intelligence as a field concerns itself with the study and design of intelligent agents. Such agents or systems perceive their environment, reason over their accumulated perceptions and through this reasoning, derive a course of action which achieves their goals or maximizes their performance measure. In many cases this planning process boils down to a principled evaluation of potential sequences of actions by exploring the resulting anticipated situations of the agent and its environment, that is to some form of combinatorial search in an implicit graph representing the interdependencies of agent actions and potential situations. This thesis focuses on the search algorithms that implement this reasoning process for intel- ligent agents. The first part covers a novel subclass of such reasoning problems where a goal driven agent must find a sequence of actions to achieve its goal such that some value function of the sequence is closest to a reference value. Such problems occur for example in recom- mender systems and self-diagnosing agents. The contribution here is an algorithm and a family of heuristic functions based on memoization that improves on the current state-of-the-art by several orders of magnitude. The second part focuses on cost- and step-optimal planning for goal-driven agents in which the problem is to derive the least-cost action sequence which achieves the agent’s goals. Here, dynamic programming can be employed to avoid redundant evaluations. The contributions of this thesis address two challenges associated with the use of dynamic programming algo- rithms. The first challenge is the memory consumption of these techniques. At the heart of such search algorithms lies a memoization component that keeps track of all generated situations and the best known way to attain them which is used to derive potential new situations. In practice the rapid growth of this component is the limiting factor for the applicability of this class of algorithms, relegating their use to problems of lower complexity or instances where the necessary graph traversal can be limited by other means such as very strong but often computationally expensive heuristics. The contribution in this thesis is a data structure that significantly reduces the necessary amount of memory to represent such a memoization component and which can be integrated into a wide range of search algorithms. Another challenge lies in the parallelization of such algorithms to take advantage of con- current hardware. Conceptually their soundness relies on maintaining a coherent memoization state across all participating threads or processes. As a state-of-the-art planner can explore on the order of millions of planning states per second, each of which have to be tested against and potentially update said state, standard synchronization primitives generally result in pro- hibitive overhead. The second contribution describes a technique that allows to adaptively compartmentalizing this state based on problem structure guaranteeing consistency across participating threads with negligible synchronization overhead. Both techniques are applica- ble to a wide range of search algorithms. In combination they allow to exploit the significant computational advantages of dynamic programming on problems of higher complexity while profiting from the inherent parallelism in current and future computing platforms.     «

Artificial Intelligence as a field concerns itself with the study and design of intelligent agents. Such agents or systems perceive their environment, reason over their accumulated perceptions and through this reasoning, derive a course of action which achieves their goals or maximizes their performance measure. In many cases this planning process boils down to a principled evaluation of potential sequences of actions by exploring the resulting anticipated situations of the agent and its environ...     »

Intelligente Software-Agenten zeichnen sich durch die Fähigkeit aus durch Schlussfolgerungsprozesse und Umgebungswissen eigenständig Aktionen auszuwählen und durchzuführen, die geeignet sind ihre vorgegebenen Ziele zu erreichen. In vielen Fällen sind diese Schlussprozesse im Kern als heuristische Suche über einem Umgebungs- und Aktionsmodell implementiert, wobei die Skalierbarkeit dieser Suche sowohl die mögliche Umgebungskomplexität als auch die Qualität des Agentenverhaltens direkt beeinflusst. Diese Dissertation greift dieses Skalierungsproblem auf und beschreibt im ersten Teil ein neuartiges Suchverfahren für eine Klasse von komplexen Suchproblemen die im Kontext selbstdiagnostizierender Agenten auftreten und im zweiten Teil eine neuartige Datenstruktur und Parallelisierungstechnik für auf Dynamischer Programmierung basierender Suchverfahren, die ihren Einsatz in komplexeren Umgebungen ermöglicht.      «

Intelligente Software-Agenten zeichnen sich durch die Fähigkeit aus durch Schlussfolgerungsprozesse und Umgebungswissen eigenständig Aktionen auszuwählen und durchzuführen, die geeignet sind ihre vorgegebenen Ziele zu erreichen. In vielen Fällen sind diese Schlussprozesse im Kern als heuristische Suche über einem Umgebungs- und Aktionsmodell implementiert, wobei die Skalierbarkeit dieser Suche sowohl die mögliche Umgebungskomplexität als auch die Qualität des Agentenverhaltens direkt beeinflusst...     »