Bikramjit Banerjee's Publications

• Selected Publications • All Sorted by Date • All Classified by Publication Type •

Exact and Heuristic Algorithms for Risk-Aware Stochastic Physical Search

D. S. Brown, J. Hudack, N. Gemelli, and B. Banerjee. Exact and Heuristic Algorithms for Risk-Aware Stochastic Physical Search. Computational Intelligence, 33(3):524–553, Wiley, 2017.

Download

[PDF] 

Abstract

We consider an intelligent agent seeking to obtain an item from one of several physical locations, where the cost to obtain the item at each location is stochastic. We study risk-aware stochastic physical search (RA-SPS), where both the cost to travel and the cost to obtain the item are taken from the same budget and where the objective is to maximize the probability of success while minimizing the required budget. This type of problem models many task-planning scenarios, such as space exploration, shopping, or surveillance. In these types of scenarios, the actual cost of completing an objective at a location may only be revealed when an agent physically arrives at the location, and the agent may need to use a single resource to both search for and acquire the item of interest. We present exact and heuristic algorithms for solving RA-SPS problems on complete metric graphs. We first formulate the problem as mixed integer linear programming problem. We then develop custom branch and bound algorithms that result in a dramatic reduction in computation time. Using these algorithms, we generate empirical insights into the hardness landscape of the RA-SPS problem and compare the performance of several heuristics.

BibTeX

@Article{Brown16:Exact,
  author = 	 {D. S. Brown and J. Hudack and N. Gemelli and B.
                 Banerjee},
  title = 	 {Exact and Heuristic Algorithms for Risk-Aware Stochastic


                 Physical Search},
  journal = 	 {Computational Intelligence},
  year = 	 {2017},
  volume = 	 {33},
  number = 	 {3},
  pages = 	 {524--553},
  publisher =    {Wiley},
  abstract =     {We consider an intelligent agent seeking to obtain an
 item from one of several physical locations, where the cost to obtain the
 item at each location is stochastic. We study risk-aware stochastic
 physical search (RA-SPS), where both the cost to travel and the cost to
 obtain the item are taken from the same budget and where the objective is
 to maximize the probability of success while minimizing the required
 budget. This type of problem models many task-planning scenarios, such as
 space exploration, shopping, or surveillance. In these types of
 scenarios, the actual cost of completing an objective at a location may
 only be revealed when an agent physically arrives at the location, and
 the agent may need to use a single resource to both search for and
 acquire the item of interest. We present exact and heuristic algorithms
 for solving RA-SPS problems on complete metric graphs. We first formulate
 the problem as mixed integer linear programming problem. We then develop
 custom branch and bound algorithms that result in a dramatic reduction in
 computation time. Using these algorithms, we generate empirical insights
 into the hardness landscape of the RA-SPS problem and compare the
 performance of several heuristics.},
}

---

Generated by bib2html.pl (written by Patrick Riley ) on Sat May 29, 2021 15:48:22