AAAI Publications, Workshops at the Twenty-Ninth AAAI Conference on Artificial Intelligence

Font Size: 
Algorithms for Stochastic Physical Search on General Graphs
Daniel S. Brown, Jeffrey Hudack, Bikramjit Banerjee

Last modified: 2015-04-01


Stochastic Physical Search (SPS) refers to the search for an item in a physical environment where the item's price is stochastic, and where the cost to obtain the item includes both travel and purchase costs. This type of problem models task planning scenarios where the cost of completing an objective at a location is drawn from a probability distribution, reflecting the influence of unknown factors. Prior work on this domain has focused on solutions where the expected cost is minimized. Recently, SPS problems with other objectives have been proposed and theoretically analyzed, in particular when either the budget or the desired probability of success is fixed. However, general optimal solvers for these new variants do not yet exist. We present algorithms for optimal solution of these variants on general graphs. We formulate them as mixed integer linear programming problems, and solve them using an off-the-shelf MILP solver. We then develop custom branch and bound algorithms which result in a dramatic reduction in computation speed. Using these algorithms, we generate empirical insights into the hardness landscape of the fixed budget and fixed probability of success SPS variants.


Physical search; Probabilistic planning; Reasoning under uncertainty; Mixed-integer linear programming; Branch and bound

Full Text: PDF