Abstract
Multi-agent planning approaches are employed for many problems including task allocation, surveillance and video games. In the first part of my thesis, we study two multi-robot planning problems, i.e. patrolling and task allocation. For the patrolling problem, we present a novel stochastic search technique, Monte Carlo Tree Search with Useful Cycles, that can generate optimal cyclic patrol policies with theoretical convergence guarantees. For the multi-robot task allocation problem, we propose an Monte Carlo Tree Search based satisficing method using branch and bound paradigm along with a novel search parallelization technique. In the second part of my thesis, we develop a stochastic multi-agent narrative planner employing MCTS along with new heuristic and pruning methods applicable for other planning domains as well.
Introduction
Planning for multiple agents in large environments is notoriously difficult. Whether coordinating a fleet of robots to patrol a facility or generating a believable story for a video game, the number of possible actions and outcomes grows exponentially. These problems are often NP-hard, meaning there is no known way to find the perfect solution quickly as the problem scales. This research identifies three specific challenges: multi-robot patrolling for optimal coverage, efficient task allocation to minimize travel distance, and coherent narrative generation with real-time user influence.
Methodology
The core engine used throughout this work is Monte Carlo Tree Search (MCTS), a stochastic search algorithm that builds a search tree by sampling possible futures. To adapt MCTS for these complex domains, several key innovations were introduced:
Multi-Robot Patrolling and Task Allocation
For patrolling, the MCTS-UC (Useful Cycles) method introduces "artificial cyclic nodes," allowing the search tree to represent infinite-length cyclic policies compactly. For task allocation, MCTS is combined with a branch and bound paradigm to prune suboptimal branches.
Furthermore, a novel Parameterized Root Parallelization technique was developed. By running separate search trees with different exploration parameters across multiple CPU threads, the system allows "exploitative" threads to find decent solutions quickly, which in turn helps "explorative" threads prune their search space more effectively.
Narrative Generation
In the domain of digital storytelling, the planner uses believability heuristics. Search biasing and pruning are based on PDDL-based logic and "believability" scores assigned to character actions, ensuring that the generated plots remain coherent and engaging.
Key Results and Insights
The proposed methods demonstrate significant performance across diverse benchmarks:
- Near-Optimality: In task allocation, the parallelized MCTS approach achieved an approximation rate of 1.03 (within 3% of the theoretical optimum) on existing benchmarks within one hour.
- Efficiency: The narrative planner generated complex, multi-character stories in less than a minute.
- Versatility: The success of the same underlying MCTS framework across physical robotics and digital storytelling highlights the flexibility of simulation-driven stochastic search.
A major insight is that MCTS does not require a perfect mathematical model; it only requires a simulator. This allows for easy swapping of "intruder models" in patrolling or "character motivations" in storytelling without altering the core algorithm.
Conclusion
While the results are promising, future work will focus on integrating high-level planning with low-level control theory to bridge the gap between decision-making and physical movement. Additionally, exploring more sophisticated information-sharing mechanisms in parallel search and improving the user interface for real-time narrative interaction remain key areas for development.
Summary updated