APPROXIMATE DYNAMIC PROGRAMMING FOR OPTIMAL SEARCH WITH AN OBSTACLE

Öz

In this paper, we study a class of optimal search problems where the search region includes a target and an obstacle, each of which has some shape. The search region is divided into small grid cells and the searcher examines one of those cells at each time period with the objective of finding the target with minimum expected cost. The searcher may either take an action that is quick but risky, or another one that is slow but safe, and incurs different cost for these actions. We formulate these problems as Markov Decision Processes (MDPs), but because of the intractability of the state space, we approximately solve the MDPs using an Approximate Dynamic Programming (ADP) technique and compare its performance against heuristic decision rules. Our numerical experiments reveal that the ADP technique outperforms heuristics on majority of problem instances. Specifically, the ADP technique performs better than the best heuristic policy in 17 out of 24 problem sets. The percent improvement in those 17 problem sets is on average 7.3%. 

Anahtar Kelimeler

• Approximate dynamic programming,Markov decision processes,Optimal search

Engelli Optimal Arama için Yaklaşımsal Dinamik Programlama

Öz

Bu makalede her biri bir şekle sahip olan, arama bölgesi hedef ve engel içeren optimal arama problemlerini çalışmaktayız. Arama bölgesi küçük grid hücrelerine bölünmüştür ve araştırmacı her bir zaman peryodunda minimum maliyetle hedefi bulma amacıyla bu hücrelerden birini inceler. Araştırmacı hızlı ama riskli eylemi veya yavaş fakat güvenilir olanı seçebilir ve bu eylemler için farklı ücret öder. Bu problemleri Markov Karar Süreçleri (MKS) ile formüle etmekteyiz, fakat durum uzayının çetinliğinden dolayı MKS’leri bir Yaklaşımsal Dinamik Programlama (YDP) tekniği kullanarak yaklaşık olarak çözmekteyiz ve onun performansını sezgisel karar kurallarıyla karşılaştırmaktayız. Nümerik deneylerimiz problem örneklerinin çoğunda YDP tekniğinin sezgisel yöntemlerden üstün olduğunu ortaya çıkarmıştır. Spesifik olarak YDP tekniği 24 problem kümesinden 17’sinde en iyi sezgisel yöntemden daha iyi sonuç vermektedir. Bu 17 problem kümesindeki yüzde gelişme ortalama %7,3’tür.

Anahtar Kelimeler

• Markov karar süreçleri,Optimal arama,Yaklaşımsal dinamik programlama

Kaynakça

1. Adelman D. “Price-directed replenishment of subsets: methodology and its application to inventory routing”. Manufacturing and Service Operations Management. 5, 4, 348-371, 2003.
2. Adelman D. “A price-directed approach to stochastic inventory routing”. Operations Research. 52, 4, 499-514, 2004.
3. Benkoski S J. Monticino, M. G., Weisinger, J. R.. “A survey of the search theory literature”. Naval Research Logistics. 38, 469-494, 1991.
4. Bertsekas D, Tsitsiklis J. “Neuro-Dynamic Programming”, Athena Scientific, 1996.
5. Botea A, Baier J, Harabor D, Hernandez C. “Moving target search with compressed path databases”. In Proceedings of ICAPS-13, 2013.
6. Chang HS, Fu MC, Hu J, Marcus SI. “Simulation-based algorithms for Markov Decision Processes”, Springer, 2007.
7. Chung TH, Burdick JW. “A decision-making framework for control strategies in probabilistic search”. Proceedings of IEEE International Conference on Robotics and Automation, 2007.
8. Chung TH. “On probabilistic search decisions under searcher motion constraints”. Algorithmic Foundations of Robotics, 2010.

9. De Farias DP, Roy BV. “The linear programming approach to Approximate Dynamic Programming”. Operations Research. 51, 850-865, 2003.
10. Dell RF, Eagle JN. Martins, G. H. A., Santos, A. G. “Using multiple searchers in constrained-path, moving-target search problems”. Naval Research Logistics. 43, 463-480, 1996.
11. Derr K, Manic, M. “Multi-robot, multi-target particle swarm optimization search in noisy wireless environments”. Proceedings of the 2nd conference on human system interactions, Catania, Italy, 2009.
12. Dobbie JM. “A survey of search theory”. Operations Research. 16(3), 527–537, 1968.
13. Eagle JN, Yee JR. “An optimal branch-and-bound procedure for the constrained path, moving target search problem”, Operations Research. 38, 110-114, 1990.
14. El-Hadidy, M. A. A., El-Bagoury, A. A. H., “Optimal search strategy for a three-dimensional randomly located target”, International Journal of Operational Research. 29, 2015.
15. El-Hadidy, M. A. A. “Fuzzy Optimal Search Plan for N-Dimensional Randomly Moving Target”, International Journal of Computational Methods. 13, 2016.
16. Gabal, H. M. A., El-Hadidy, M. A. A., “Optimal searching for a randomly located target in a bounded known region”, International Journal of Computing Science and Mathematics. 6, 2015.
17. Haley WB, Stone LD. “Search Theory and Applications”, Plenum Press, New York, 1980.
18. Kulich M, Preucil L, Jose J, Bront M. “Single robot search for a stationary object in an unknown environment”, IEEE International Conference on Robotics Automation, 2014.
19. Lossner U, Wegener I. “Discrete sequential search with positive switch cost”. Mathematics of Operations Research. 7(3), 426–440, 1982.
20. Maxwell MS, Henderson SG, and Topaloglu H. “Tuning Approximate Dynamic Programming Policies for Ambulance Redeployment via Direct Search”. Stochastic Systems. 3, 1-40, 2013.
21. Najemnik J, Geisler WS. “Eye movement statistics in humans are consistent with an optimal search strategy”, J. Vis. 8, 1-14, 2008.
22. Nitinawarat, S., Veeravalli, V. V., “Universal scheme for optimal search and stop”, Bernoulli. 23, 1759-1783, 2017.
23. Powell WB. “Approximate Dynamic Programming: Solving the Curses of Dimensionality”, Wiley, 2007.
24. Ross SM. “A problem in optimal search and stop”. Operations Research. 17, 984–992, 1969.
25. Shechter SM, Ghassemi F, Gocgun Y, Puterman ML. “Trading off quick versus slow actions in optimal search”. Operations Research. 63, 353-362, 2015.
26. Singh S., Krishnamurthy, V. “The optimal search for a markovian target when the search path is constrained: the infinite-horizon case”. IEEE Transactions on Automatic Control, 2003.
27. Snider J. “Optimal random search for a single hidden target”. Physical Review. 83, 011105, 2011.
28. Stone LD. “Theory of Optimal Search”, Academic Press, 1975.
29. Suman B, Kumar B. “A survey of simulated annealing as a tool for single and multiobjective optimization”. Journal of the Operational Research Society. 57, 1143–1160, 2006.
30. Sutton RS, Barto AG. “Reinforcement Learning : an introduction”, MIT Press, 1998.
31. Washburn A.” Search and Detection”, Fourth Edition, Institute for Operations Research and the Management Sciences, 2002.
32. Wegener I. “The discrete sequential search problem with nonrandom cost and overlook probabilities”. Mathematics of Operations Research. 5, 373–380, 1980.
33. Wettergren TA. “Performance of search via track-before-detect for distributed sensor networks”, IEEE Transactions on Aerospace and Electronic Systems, 44, 2008.
34. Zhao Y, Patek SD, Beling PA. “Decentralized Bayesian Search Using Approximate Dynamic Programming Methods”. IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics, 38, 2008.