Dergiler / Selçuk Üniversitesi Mühendislik Bilim ve Teknoloji Dergisi / 2019 / Cilt: 7 - Sayı: 1
Engelli Optimal Arama için Yaklaşımsal Dinamik Programlama
- Sayfa
- 89–104
- DOI
- —
Ö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.
Abstract
In this paper, we study a class of optimal search problems where the search regionincludes a target and an obstacle, each of which has some shape. The search region is divided intosmall grid cells and the searcher examines one of those cells at each time period with the objective offinding the target with minimum expected cost. The searcher may either take an action that is quickbut risky, or another one that is slow but safe, and incurs different cost for these actions. We formulatethese problems as Markov Decision Processes (MDPs), but because of the intractability of the statespace, we approximately solve the MDPs using an Approximate Dynamic Programming (ADP)technique and compare its performance against heuristic decision rules. Our numerical experimentsreveal 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. Thepercent improvement in those 17 problem sets is on average 7.3%.