Journals / Konya Journal of Engineering Sciences / 2019 / Cilt: 7 Sayı: 1

APPROXIMATE DYNAMIC PROGRAMMING FOR OPTIMAL SEARCH WITH AN OBSTACLE

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

Pages
89–104
Publication Date
2019-03-01
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

The percent improvement in those 17 problem sets is on average 7.3%.

📌 3 Key Takeaways

🎯
Objective & Hypothesis: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.
📊
Key Findings & Data: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.
💡
Conclusion & Impact:The percent improvement in those 17 problem sets is on average 7.3%.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Markov karar süreçleri · Optimal arama · Yaklaşımsal dinamik programlama

Abstract

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%.

Özet

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.

🔖

Cite This Article

GÖÇGÜN, Y. (2019). APPROXIMATE DYNAMIC PROGRAMMING FOR OPTIMAL SEARCH WITH AN OBSTACLE. Konya Journal of Engineering Sciences, Cilt: 7 Sayı: 1, 89–104. https://ajindex.com/articles/909253

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (18)

  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 environmen