Long-term planning and reactive execution in highly dynamic environments

Abstract

In many highly dynamic environments artificial agents need to follow long-term goals and therefore are required to reason and to plan far into the future. At the same time, while following long-term plans, the agents are also required to stay reactive to environmental changes and to act deliberately while always maintaining robust and secure behaviors. In many cases, such agents act as parts of a larger system and need to collaborate while coordinating their actions. Generating agent behaviors that allow for long-term planning and reactive acting is a complex task, which becomes even more challenging with an increasing number of agents and an increasing size of the search space. This thesis focuses on video games as highly dynamic multi-agent environments proposing a solution that allows to combine long-term planning with reactive execution. On the one hand, existing literature proposes a variety of different planning approaches. However, plans that are executed in highly-dynamic environments are very likely to fail during their execution. This can lead to high replanning frequencies and delayed execution. On the other hand, there are various reactive decision-making approaches, which allow agents to quickly adjust their behaviors to environmental changes. However, usually such approaches do not allow for long-term planning. Inspired by various approaches observed in areas such as spacecraft control, robotics, and video games, this thesis proposes a hybrid approach. The general idea of the hybrid solution combines a Hierarchical Task Network (HTN) planner and a reactive approach in a three-layer architecture. The approach separates the decision-making responsibilities between a planner, which is responsible for abstract long-term planning, and a reactive approach that is responsible for local decision-making and task refinement at execution time. The major contribution of this work, which allows for such interleaved decision-making and continuous execution of long-term plans, is an extension of the plan tasks, which is used by the reactive approach at execution time. The thesis describes two different implementations of this solution using either Behavior Trees or Monte Carlo Tree Search (MCTS) as reactive approaches. It examines the effects of the interleaved decision-making in two different highly dynamic video game environ-ments and evaluates the performance of agents using the hybrid approaches comparing them to existing benchmark agents. Additionally, it proposes a possibility to automati-cally improve the execution of long-term tasks using an Evolutionary Algorithm.The results of the performed experiments show that the proposed solutions allow to reduce the global replanning frequencies and decrease the total execution time of multi-agent long-term plans while increasing the success rates of their execution when com-pared to a pure planning approach. Furthermore, the use of the extended high-level plan tasks allows to guide the search process of MCTS resulting in emergent agent behav-iors, which can be further improved by a learning mechanism such as an Evolutionary Algorithm.

In vielen hochdynamischen Umgebungen müssen Agenten Langzeitziele verfolgen und dafür weit in die Zukunft planen können. Während sie Langzeitpläne ausführen, müssen sie schnell auf Veränderungen in ihrer Umgebung reagieren können und stets bewusstes, robustes und sicheres Verhalten zeigen. In vielen Fällen agieren sie als Teile eines größeren Systems und müssen ihre Handlungen koordinieren. Die Generierung von Agentenverhalten, die sowohl die Verfolgung von Langzeitplänen als auch reaktives Han-deln ermöglichen, ist eine große Herausforderung, die mit steigender Agentenanzahl und steigender Größe des Suchraums noch komplexer wird. In dieser Thesis werden Videospiele als hochdynamische Multiagentenumgebungen untersucht und eine Lösung vorgeschlagen, die es erlaubt, die Verfolgung von Langzeitzielen mit reaktivem Handeln zu kombinieren. Einerseits beschreibt existierende Literatur eine Vielzahl an unterschiedlichen Planungs-ansätzen, jedoch scheitern Langzeitpläne oft bei ihrer Ausführung in hochdynamis-chen Umgebungen. Dies kann zu häufigen Neuplanungen führen und potenziell die Ausführung der Pläne verzögern. Andererseits existieren viele reaktive Entscheidungssys-teme, die schnelle Anpassungen an Agentenverhalten ermöglichen, jedoch nicht weit in die Zukunft planen können. Inspiriert von unterschiedlichen Ansätzen aus den Bereichen der Raumfahrt, der Robotik und der Videospiele wird in dieser Thesis ein hybrider Ansatz vorgeschlagen. In seiner Grundidee kombiniert der Ansatz einen Hierarchical Task Network Planer und ein reak-tives Entscheidungssystem in einer Drei-Schichten-Architektur. Die Entscheidungsver-antwortung wird zwischen dem Planer, welcher für abstrakte Langzeitplanung verant-wortlich ist, und einem reaktiven System, welches lokale Entscheidungen trifft und die abstrakten Aufgaben während der Ausführung verfeinert, aufgeteilt. Der Haupt-beitrag dieser Arbeit, der eine gekoppelte Entscheidungsfindung and eine ununterbroch-ene Ausführung ermöglicht, ist eine Erweiterung der Planungsdomäne, welche während der Ausführung von dem reaktiven System benutzt wird. Die Thesis beschreibt zwei konkrete Umsetzungen der vorgeschlagenen Lösung, die en-tweder Behavior Trees oder Monte Carlo Tree Search (MCTS) als reaktive Systeme einsetzen. Die Auswirkungen der kombinierten Entscheidungsfindung werden in zwei unterschiedlichen hochdynamischen Videospielumgebungen untersucht und die hybriden Agenten mit existierenden Benchmark-Agenten anhand ihrer Spielleistung verglichen. Außerdem wird eine Möglichkeit vorgeschlagen, die Ausführung von Langzeitaufgaben durch einen evolutionären Algorithmus zu verbessern.Experimentergebnisse zeigen, dass die vorgeschlagene Lösung die globale Häufigkeit der Neuplanungen sowie die Ausführzeit von Langzeitplänen im Vergleich zu einem reinen Planungsansatz verringern kann während die Erfolgsrate der Ausführungen erhöht wird. Die Erweiterung der Planungsdomäne erlaubt es außerdem den Suchprozess von MCTS zu lenken, wodurch emergente Verhalten entstehen, die durch einen Lernmechanismus wie einen evolutionären Algorithmus noch weiter angepasst werden können.