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). . (KAR id:48657)

Language: English
Download (253kB)
[thumbnail of grzes13ijcai.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL:


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: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Marek Grzes
Date Deposited: 26 May 2015 20:43 UTC
Last Modified: 10 Dec 2022 02:18 UTC
Resource URI: (The current URI for this page, for reference purposes)
Grzes, Marek:
  • Depositors only (login required):


Downloads per month over past year