Algorithms for Stochastic Physical Search on General Graphs

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