Stochastic Planning in Large Search Spaces

1 Introduction

Large-scale planning has many application areas such as surveillance, patrolling, and games. There has been great improvement in large-scale planning with sampling based methods. One example is Monte Carlo Tree Search (MCTS), an anytime stochastic search algorithm shown to perform well for large planning domains. Particularly, the Go game has been one of the most challenging problems in AI lately and recently an MCTS based approach remarkably beat a top human professional on a full size Go board [Silver et al., 2016].

Throughout my PhD work I have studied various applications of large-scale stochastic planning, including multirobot patrolling [Kartal et al., 2015], multi-robot task allocation [Kartal et al., 2016], and multi-agent narrative generation [Kartal et al., 2013; 2014]. The multi-robot planning problems, particularly patrolling and task allocation, require high coordination among the robots for efficient behavior. Both patrolling and task allocation problems are NP-hard and the multi-robot task allocation problem is a much more generalized version of many multi-robot coordination problems. The multi-agent narrative generation problem aims to generate coherent and believable narratives which are potentially applicable in entertainment, education, and training systems.

My thesis will show that sampling-based stochastic search techniques can be adapted to efficiently find approximate solutions to large-scale multi-agent planning problems that arise in a variety of domains including both physical planning for robot patrolling, and task allocation and abstract planning for narrative generation. Sparse sampling based stochastic approaches can be successfully applied to domains with large state spaces, and their sampling-based nature allows flexibility in the details of the problem formulation and supports quick feedback for the user-in-the-loop interaction.

2 Contributions

The stochastic planning techniques developed as part of my thesis has many important applications (Figure 1).

2.1 Multi-Robot Patrolling Problem

We proposed Monte Carlo Tree Search with Useful Cycles (MCTS-UC) [Kartal et al., 2015], a novel stochastic search technique that can generate infinite length cyclic policies with theoretical convergence guarantees for nonadversarial patrolling problem with probabilistic intrusion models. Our approach expands the state space with artificial cyclic nodes to compactly represent infinite length policies. Our approach improves the state of the art in the sense that it can be easily adapted to different intrusion models and arbitrary environments as long as an MDP simulator exists for the formulated problem. A video presenting patrolling policies in different environments can be seen at http://motion.cs.umn.edu/r/MCTS-UC.

2.2 Multi-Robot Task Allocation

We proposed an efficient, satisficing and centralized Monte Carlo Tree Search based algorithm using the branch and bound paradigm with a novel search parallelization method to solve the multi-robot task allocation problem. We proposed a new evaluation function to balance between task completion and total traveled distance minimization. We coupled our evaluation function with a novel search parallelization technique, parameterized root parallelization. Here, we create a separate search tree per thread with varying exploration parameters with a globally shared best complete policy distance. The design idea is that highly exploiting threads can find a sub-optimal solution completing all the tasks very early during the search. Since this solution is shared among all threads, both this will better calibrate all the threads' search directions and bounding many branches guaranteed to be not better than the best found will improve memory efficiency due to pruning. Unlike previous heuristics tailored for specific problems, our approach is general, it has asymptotic convergence guarantees, and it finds near-optimal solutions for non-trivial problems in an existing test benchmarks within an hour.

2.3 Multi-Agent Narrative Generation

We modeled the narrative generation problem as a multiagent planning problem and proposed an MCTS based userdriven story planner along with several heuristics based on search biasing and tree pruning. Our approach [Kartal et al., 2013; 2014] aims to generate more believable narratives given user defined story goals. We assumed an expert user has authored a PDDL based logic relations for the story actions along with believability of different actions. We present an example output of our planner for the Detective story domain in Figure 2. The main novelty of our approach improving the state-of-the art is its ability to allow the user to interact with the planner by changing believability of actions and interact with the planner in real-time as MCTS is an anytime approach. A video showing our story planner running can be found at: http://motion.cs.umn.edu/r/StoryMCTS.

Alice picked up a vase from her house. Bob picked up a rifle from his house. Bob went to Alices house. While there, greed got the better of him and Bob stole Alices vase! This made Alice furious. Alice pilfered Bobs vase! This made Bob furious. Bob slayed Alice with a rifle! Bob fled to downtown. Bob executed Inspector Lestrade with a rifle! Charlie took a baseball bat from Bobs house. Sherlock went to Alices house. Sherlock searched Alices house and found a clue about the recent crime. Bob fled to Alices house. Sherlock wrestled the rifle from Bob! This made Bob furious. Sherlock performed a citizens arrest of Bob with his rifle and took Bob to jail.

Figure 2: A story generated in less than a minute.

3 Conclusions and FutureWork

The main contributions of my thesis is to show how samplingbased stochastic search methods can be efficiently adapted for multi-agent problems both in physical domains for the multirobot patrolling and task allocation, and in abstract domain for the computer narrative generation problem. We show that the sampling based nature proves to be very useful for planning problems as simulation-driven mechanisms permit modification to planning problem details with no changes to the algorithm, e.g. different intruder models can be used for the patrolling problem, and action believabilities can be altered for the narrative generation problem. This ability renders the approach more general and easily adaptable to different problem variants. Also, the MCTS algorithm is a complete search method guaranteeing optimality along with the anytime property for flexible computation cost. There are many avenues for future work such as exploring new parallelization techniques and integration of MCTS with control theory.