Optimistic planning with constant control over multiple time steps (OSP)

Optimistic Planning for Deterministic Systems (OPD) is an algorithm designed to deal with very general control problems, usually at high computational costs. However, there exist specific classes of “simpler” problems to which OPD can be adapted, reaching good performance with less computation than the original OPD. This project focuses on one such type of adaptation: namely, to extend the OPD planning algorithm to the class of control problems that prefers long ranges of repeated actions. Specifically, we introduced an algorithm called Optimistic Planning with a limited number of Switches (OSP) that restricts the search to sequences that switch at most a limited number of times. We showed that this leads to polynomial complexity rather than the exponential complexity of OSP, where the degree of the polynomial is a meaningful measure of problem complexity. This algorithm worked well in simulation experiments involving mechanical systems as well as a model of HIV infection.

Start date (duration): 
October, 2011 to July, 2013
Project status and type: