Skip to main content

Isomorph-Free Branch and Bound Search for Finite State Controllers

Grzes, Marek, Poupart, Pascal, Hoey, Jesse (2013) Isomorph-Free Branch and Bound Search for Finite State Controllers. In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). .


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.

Item Type: Conference or workshop item (Paper)
Subjects: Q Science > Q Science (General)
Q Science > Q Science (General) > Q335 Artificial intelligence
Divisions: Faculties > Sciences > School of Computing
Faculties > Sciences > School of Computing > Computational Intelligence Group
Depositing User: Marek Grzes
Date Deposited: 26 May 2015 20:43 UTC
Last Modified: 29 May 2019 14:36 UTC
Resource URI: (The current URI for this page, for reference purposes)
  • Depositors only (login required):


Downloads per month over past year