Anthony R. Cassandra

UAI Conference 1999 Conference Paper

Solving POMDPs by Searching the Space of Finite Policies

• Nicolas Meuleau
• Kee-Eung Kim
• Leslie Pack Kaelbling
• Anthony R. Cassandra

Solving partially observable Markov decision processes (POMDPs) is highly intractable in general, at least in part because the optimal policy may be infinitely large. In this paper, we explore the problem of finding the optimal policy from a restricted set of policies, represented as finite state automata of a given size. This problem is also intractable, but we show that the complexity can be greatly reduced when the POMDP and/or policy are further constrained. We demonstrate good empirical results with a branch-and-bound method for finding globally optimal deterministic policies, and a gradient-ascent method for finding locally optimal stochastic policies.

AIJ Journal 1998 Journal Article

Planning and acting in partially observable stochastic domains

• Leslie Pack Kaelbling
• Michael L. Littman
• Anthony R. Cassandra

In this paper, we bring techniques from operations research to bear on the problem of choosing optimal actions in partially observable stochastic domains. We begin by introducing the theory of Markov decision processes (mdps) and partially observable MDPs (pomdps). We then outline a novel algorithm for solving pomdps off line and show how, in some cases, a finite-memory controller can be extracted from the solution to a POMDP. We conclude with a discussion of how our approach relates to previous work, the complexity of finding exact solutions to pomdps, and of some possibilities for finding approximate solutions.

UAI Conference 1997 Conference Paper

Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes

• Anthony R. Cassandra
• Michael L. Littman
• Nevin L. Zhang

IROS Conference 1996 Conference Paper

Acting under uncertainty: discrete Bayesian models for mobile-robot navigation

• Anthony R. Cassandra
• Leslie Pack Kaelbling
• James Kurien

Discrete Bayesian models have been used to model uncertainty for mobile-robot navigation, but the question of how actions should be chosen remains largely unexplored. This paper presents the optimal solution to the problem, formulated as a partially observable Markov decision process. Since solving for the optimal control policy is intractable, in general, it goes on to explore a variety of heuristic control strategies. The control strategies are compared experimentally, both in simulation and in runs on a robot.

ICML Conference 1995 Conference Paper

Learning Policies for Partially Observable Environments: Scaling Up

• Michael L. Littman
• Anthony R. Cassandra
• Leslie Pack Kaelbling

AAAI Conference 1994 Conference Paper

Acting Optimally in Partially Observable Stochastic Domains

• Anthony R. Cassandra

In this paper, we describe the partially observable Markov decision process (POMDP) approach to finding optimal or near-optimal control strategies for partially observable stochastic environments, given a complete model of the environment. The POMDP approach was originally developed in the operations research community and provides a formal basis for planning problems that have been of interest to the AI community. We found the existing algorithms for computing optimal control strategies to be highly computationally inefficient and have developed a new algorithm that is empirically more efficient. We sketch this algorithm and present preliminary results on several small problems that illustrate important properties of the POMDP approach.