Closing the gap: Improved bounds on optimal POMDP solutions

POMDP algorithms have made significant progress in recent years by allowing practitioners to find good solutions to increasingly large problems. Most approaches (including point-based and policy iteration techniques) operate by refining a lower bound of the optimal value function. Several approaches (e.g., HSVI2, SARSOP, grid-based approaches and online forward search) also refine an upper bound. However, approximating the optimal value function by an upper bound is computationally expensive and therefore tightness is often sacrificed to improve efficiency (e.g., sawtooth approximation). In this paper, we describe a new approach to efficiently compute tighter bounds by i) conducting a prioritized breadth first search over the reachable beliefs, ii) propagating upper bound improvements with an augmented POMDP and iii) using exact linear programming (instead of the sawtooth approximation) for upper bound interpolation. As a result, we can represent the bounds more compactly and significantly reduce the gap between upper and lower bounds on several benchmark problems. Copyright © 2011, Association for the Advancement of Artificial Intelligence. All rights reserved.

Comparison of stochastic methods for control in air traffic management

This paper provides a direct comparison of two stochastic optimisation techniques (Markov Chain Monte Carlo and Sequential Monte Carlo) when applied to the problem of conflict resolution and aircraft trajectory control in air traffic management. The two methods are then also compared to another existing technique of Mixed-Integer Linear Programming which is also popular in distributed control. © 2011 IFAC.

Continuous dynamical systems that realize discrete optimization on the hypercube

We study the problem of finding a local minimum of a multilinear function E over the discrete set {0,1}n. The search is achieved by a gradient-like system in [0,1]n with cost function E. Under mild restrictions on the metric, the stable attractors of the gradient-like system are shown to produce solutions of the problem, even when they are not in the vicinity of the discrete set {0,1}n. Moreover, the gradient-like system connects with interior point methods for linear programming and with the analog neural network studied by Vidyasagar (IEEE Trans. Automat. Control 40 (8) (1995) 1359), in the same context. © 2004 Elsevier B.V. All rights reserved.