Isomorph-Free Branch and Bound Search for Finite State Controllers

The recent proliferation of smart-phones and other wearable devices has lead

to a surge of new mobile applications. Partially observable Markov decision

processes provide a natural framework to design applications that

continuously make decisions based on noisy sensor measurements. However,

given the limited battery life, there is a need to minimize the amount of

online computation. This can be achieved by compiling a policy into a

finite state controller since there is no need for belief monitoring or

online search. In this paper, we propose a new branch and bound technique

to search for a good controller. In contrast to many existing algorithms

for controllers, our search technique is not subject to local optima. We

also show how to reduce the amount of search by avoiding the enumeration of

isomorphic controllers and by taking advantage of suitable upper and lower

bounds. The approach is demonstrated on several benchmark problems as well

as a smart-phone application to assist persons with Alzheimer's to wayfind.