Online Planning for Interactive-POMDPs using Nested Monte Carlo Tree Search

Abstract

The ability to make good decisions in partially observed non-cooperative multi-agent scenarios is important for robots to interact effectively in human environments. A robust framework for such decision-making problems is the Interactive Partially Observable Markov Decision Processes (I-POMDPs), which explicitly models the other agents' beliefs up to a finite reasoning level in order to more accurately predict their actions. This paper proposes a new online approximate solver for I-POMDPs, called Interactive Nested Tree Monte-Carlo Planning (I-NTMCP), that combines Monte Carlo Tree Search with the finite nested-reasoning construction of I-POMDPs. Unlike existing full-width I-POMDP planners, I-NTMCP focuses planning on the set of beliefs at each nesting level which are reachable under an optimal policy and uses sampling to construct and update policies at each nesting level, online. This strategy enables I-NTMCP to plan effectively in significantly larger I-POMDP problems and to deeper reasoning levels than has previously been possible. We demonstrate I-NTMCP's effectiveness on two competitive environments. The results indicate that I-NTMCP can generate substantially better policies up to more than 50× faster than I-POMDP Lite - one of the fastest I-POMDP solvers today. In the pursuit-evasion domain, we show I-NTMCP can plan effectively in a complex problem with over 88K states, which is two orders of magnitude larger than existing I-POMDP planning benchmark problems.