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.