Bazen basitçe AI planlama olarak ifade edilen otomatik planlama ve zamanlama[1], tipik olarak akıllı aracılar, otonom robotlar ve insansız araçlar tarafından yürütülmek üzere stratejilerin veya eylem dizilerinin gerçekleştirilmesine ilişkin bir yapay zeka dalıdır. Klasik kontrol ve sınıflandırma problemlerinin aksine, çözümler karmaşıktır ve çok boyutlu uzayda keşfedilmeli ve optimize edilmelidir. Planlama ayrıca karar teorisi ile de ilgilidir.
Kullanılabilir modellere sahip bilinen ortamlarda, planlama çevrimdışı yapılabilir. Uygulamadan önce çözümler bulunabilir ve değerlendirilebilir. Dinamik olarak bilinmeyen ortamlarda, stratejinin genellikle çevrimiçi olarak revize edilmesi gerekir. Modeller ve politikalar uyarlanmalıdır. Çözümler genellikle yapay zekada yaygın olarak görülen yinelemeli deneme yanılma süreçlerine başvurur. Bunlar arasında dinamik programlama, takviyeli öğrenme ve kombinatoryal optimizasyon yer alır. Planlama ve programlamayı tanımlamak için kullanılan dillere genellikle eylem dilleri denir.
Genel bakış
Dünyanın olası ilk durumlarının bir açıklaması, istenen hedeflerin bir açıklaması ve bir dizi olası eylemin bir açıklaması verildiğinde, planlama problemi, garanti edilen bir planın sentezlenmesidir (başlangıç durumlarından herhangi birine uygulandığında). İstenen hedefleri içeren bir durum oluşturmak için (böyle bir duruma hedef durum denir).
Planlamanın zorluğu kullanılan basitleştirici varsayımlara bağlıdır. Problemlerin çeşitli boyutlarda sahip olduğu özelliklere bağlı olarak, birkaç planlama problemi sınıfı tanımlanabilir.
Eylemler deterministik mi yoksa deterministik değil mi? Deterministik olmayan eylemler için ilgili olasılıklar mevcut mu?
Durum değişkenleri kesikli mi yoksa sürekli mi? Ayrıklarsa, yalnızca sınırlı sayıda olası değerleri mi var?
Mevcut durum açık bir şekilde gözlemlenebiliyor mu? Tam gözlemlenebilirlik ve kısmi gözlemlenebilirlik olabilir.
Sonlu veya keyfi olarak kaç tane başlangıç durumu vardır?
Eylemlerin bir süresi var mı?
Aynı anda birkaç işlem yapılabilir mi, yoksa aynı anda yalnızca bir işlem mi yapılabilir?
Bir planın amacı, belirlenmiş bir hedef durumuna ulaşmak mı, yoksa bir ödül fonksiyonunu maksimize etmek mi?
Sadece bir ajan mı var yoksa birkaç ajan mı var? Ajanlar işbirlikçi mi yoksa bencil mi? Tüm temsilciler kendi planlarını ayrı ayrı mı oluşturuyor yoksa planlar tüm aracılar için merkezi olarak mı oluşturuluyor?
Klasik Planlama Problemi olarak bilinen mümkün olan en basit planlama problemi şu şekilde belirlenir:
benzersiz bir bilinen başlangıç durumu,
süresiz eylemler,
deterministik eylemler,
bir seferde sadece bir tane alınabilir,
ve tek bir ajan.
İlk durum açık bir şekilde bilindiğinden ve tüm eylemler deterministik olduğundan, herhangi bir eylem dizisinden sonra dünyanın durumu doğru bir şekilde tahmin edilebilir ve gözlemlenebilirlik sorunu klasik planlama için ilgisizdir.
Ayrıca planlar, eylemler dizisi olarak tanımlanabilir, çünkü hangi eylemlerin gerekli olacağı her zaman önceden bilinir.
Aracının kontrolü dışındaki deterministik olmayan eylemler veya diğer olaylarla, olası yürütmeler bir ağaç oluşturur ve planlar, ağacın her düğümü için uygun eylemleri belirlemelidir.
Ayrık zamanlı Markov karar süreçleri (MDP) aşağıdakilerle ilgili planlama sorunlarıdır:
süresiz eylemler,
olasılıklarla deterministik olmayan eylemler,
tam gözlemlenebilirlik,
bir ödül fonksiyonunun maksimize edilmesi,
ve tek bir ajan.
Tam gözlemlenebilirlik kısmi gözlemlenebilirlikle değiştirildiğinde, planlama kısmen gözlemlenebilir Markov karar sürecine (POMDP) karşılık gelir.
Birden fazla ajan varsa, oyun teorisi ile yakından ilgili olan çoklu ajan planlamamız var.
Etki alanından bağımsız planlama
Yapay zeka planlamasında, planlayıcılar tipik olarak bir alan modeli (alanı modelleyen bir dizi olası eylemin açıklaması) ve bunun yanı sıra başlangıç durumu ve hedef tarafından belirtilen çözülecek belirli sorunu girerler. giriş alanı belirtildi. Bu tür planlayıcılar, planlama problemlerini çok çeşitli alanlardan çözebileceklerini vurgulamak için “alan bağımsız” olarak adlandırılır. Etki alanlarının tipik örnekleri, blok istifleme, lojistik, iş akışı yönetimi ve robot görev planlamasıdır. Dolayısıyla, tüm bu çeşitli alanlardaki planlama problemlerini çözmek için tek bir alandan bağımsız planlayıcı kullanılabilir. Öte yandan, bir rota planlayıcı, alana özgü bir planlayıcı için tipiktir.
Planlama alanı modelleme dilleri
STRIPS ve Klasik Planlama için PDDL gibi planlama alanlarını ve belirli planlama problemlerini temsil etmek için en sık kullanılan diller, durum değişkenlerine dayalıdır. Dünyanın her olası durumu, durum değişkenlerine bir değer atamasıdır ve eylemler, bu eylem yapıldığında durum değişkenlerinin değerlerinin nasıl değişeceğini belirler. Bir dizi durum değişkeni, kümede üstel olan bir boyuta sahip bir durum uzayını tetiklediğinden, planlama, diğer birçok hesaplama problemine benzer şekilde, boyutsallık lanetinden ve kombinatoryal patlamadan muzdariptir.
Planlama problemlerini tanımlamak için alternatif bir dil, içinde bir dizi görevin verildiği ve her görevin ya ilkel bir eylemle gerçekleştirilebileceği ya da bir dizi başka göreve ayrıştırılabileceği hiyerarşik görev ağlarıdır. Daha gerçekçi uygulamalarda durum değişkenleri görev ağlarının tanımını basitleştirse de, bu mutlaka durum değişkenlerini içermez.
Planlama için algoritmalar
Klasik planlama
muhtemelen buluşsal yöntemlerle geliştirilmiş ileri zincirleme durum alanı araması
muhtemelen durum kısıtlamalarının kullanımıyla geliştirilmiş geriye doğru zincirleme arama (bkz. STRIPS, grafik plan)
kısmi sipariş planlaması
Ayrıca bakınız: Sussman anomalisi
Diğer sorunlara azalma
Önermesel tatmin problemine (satplan) indirgeme.
Model kontrolüne indirgeme – her ikisi de temelde durum uzaylarını çaprazlama problemleridir ve klasik planlama problemi, model kontrol problemlerinin bir alt sınıfına karşılık gelir.
Zamansal planlama
Zamansal planlama, klasik planlamaya benzer yöntemlerle çözülebilir. Temel fark, eşzamanlı olarak alınan bir süre ile geçici olarak örtüşen birkaç eylem olasılığı nedeniyle, bir durum tanımının mevcut mutlak süre ve her bir etkin eylemin yürütülmesinin ne kadar ilerlediği hakkında bilgi içermesi gerektiğidir. Ayrıca, klasik planlama veya tamsayı zamanlı planlamanın aksine, rasyonel veya gerçek zamanlı planlamada durum uzayı sonsuz olabilir. Zamansal planlama, belirsizlik söz konusu olduğunda çizelgeleme problemleriyle yakından ilgilidir ve zamanlanmış otomatlar açısından da anlaşılabilir. Belirsizlikli Basit Zamansal Ağ (STNU), kontrol edilebilir eylemleri, belirsiz olayları ve zamansal kısıtlamaları içeren bir çizelgeleme problemidir. Bu tür problemler için Dinamik Kontrol Edilebilirlik, belirsiz olaylar gözlenirken kontrol edilebilir eylemleri tepkisel olarak etkinleştirmek için geçici bir planlama stratejisi gerektiren bir çizelgeleme türüdür, böylece tüm kısıtlamaların karşılanması garanti edilir. [2]
Olasılıksal planlama
Olasılıksal planlama, durum alanı yeterince küçük olduğunda, değer yineleme ve politika yineleme gibi yinelemeli yöntemlerle çözülebilir. Kısmi gözlemlenebilirlikle, olasılıksal planlama benzer şekilde yinelemeli yöntemlerle çözülür, ancak durumlar yerine inançlar alanı için tanımlanan değer fonksiyonlarının bir temsili kullanılır.
Tercihe dayalı planlama
Tercihe dayalı planlamada amaç sadece bir plan üretmek değil, aynı zamanda kullanıcı tarafından belirlenen tercihleri de tatmin etmektir. Örneğin MDP’lere karşılık gelen daha yaygın ödül tabanlı planlamadan bir fark olarak, tercihlerin kesin bir sayısal değeri olması gerekmez.
Koşullu planlama
Hiyerarşik bir planlayıcı olan STRIPS planlama sistemi ile deterministik planlamaya geçilmiştir. Eylem adları bir sırayla sıralanır ve bu robot için bir plandır. Hiyerarşik planlama, otomatik olarak oluşturulmuş bir davranış ağacıyla karşılaştırılabilir.[3] Dezavantajı, normal bir davranış ağacının bir bilgisayar programı kadar ifade edici olmamasıdır. Bu, bir davranış grafiğinin gösteriminin eylem komutları içerdiği, ancak döngüler veya if-then-deyimleri içermediği anlamına gelir. Koşullu planlama darboğazın üstesinden gelir ve Pascal gibi diğer programlama dillerinden bilinen bir kontrol akışına benzer ayrıntılı bir gösterim sunar. Program sentezine çok benzer, bu da bir planlayıcının bir tercüman tarafından yürütülebilen kaynak kodu ürettiği anlamına gelir.[4]
Koşullu planlayıcının erken bir örneği, 1970’lerin ortalarında tanıtılan “Warplan-C”dir.[5] Normal bir dizi ile if-then-ifadelerini içeren karmaşık bir plan arasındaki fark nedir? Bir planın çalışma zamanındaki belirsizlikle ilgisi var. Buradaki fikir, bir planın, planlayıcı için bilinmeyen sensör sinyallerine tepki verebilmesidir. Planlayıcı önceden iki seçenek oluşturur. Örneğin, bir nesne algılandıysa A eylemi, nesne eksikse B eylemi yürütülür.[6] Koşullu planlamanın önemli bir avantajı, kısmi planları işleme yeteneğidir.[7] Bir temsilci, baştan sona her şeyi planlamak zorunda değildir, ancak sorunu parçalara ayırabilir. Bu, durum uzayını azaltmaya yardımcı olur ve çok daha karmaşık sorunları çözer.
koşullu planlama
Çevre, hatalı olabilen sensörler aracılığıyla gözlemlenebildiğinde “olasılık planlamasından” bahsediyoruz. Dolayısıyla, planlama ajanının eksik bilgi altında hareket ettiği bir durumdur. Koşullu bir planlama problemi için, bir plan artık bir eylemler dizisi değil, bir karar ağacıdır, çünkü planın her adımı, klasik planlamada olduğu gibi, mükemmel şekilde gözlemlenebilir tek bir durum yerine bir dizi durum tarafından temsil edilir.[8 ] Seçilen eylemler, sistemin durumuna bağlıdır. Örneğin, eğer yağmur yağarsa temsilci şemsiyeyi almayı seçer, yağmur yağmazsa almamayı seçebilir.
Michael L. Littman, 1998’de dallanma eylemleriyle planlama probleminin EXPTIME-complete olduğunu gösterdi.[9][10] Belirli bir bitişik planlama durumu, “tamamen gözlemlenebilir ve deterministik olmayan” için FOND problemleriyle temsil edilir. Hedef LTLf’de (sonlu izlemede doğrusal zaman mantığı) belirtilirse, sorun her zaman EXPTIME-complete[11] ve hedef LDLf ile belirtilmişse 2EXPTIME-complete olur.
Uyumlu planlama
Uyumlu planlama, ajanın sistemin durumu hakkında emin olmadığı ve herhangi bir gözlem yapamadığı zamandır. Ajan daha sonra gerçek dünya hakkında inançlara sahiptir, ancak bunları örneğin duyusal eylemlerle doğrulayamaz. Bu problemler, klasik planlamaya benzer tekniklerle çözülür, ancak mevcut durumla ilgili belirsizlik nedeniyle durum uzayı problemin boyutunda üsteldir. Uyumlu bir planlama problemi için bir çözüm, bir dizidir eylemlerin e. Haslum ve Jonsson, uyumlu planlama probleminin EXPSPACE-complete[14] ve 2EXPTIME-complete olduğunu, başlangıç durumu belirsiz olduğunda ve eylem sonuçlarında determinizm olmadığında göstermiştir.[10]
Planlama sistemlerinin devreye alınması
Hubble Uzay Teleskobu, SPSS adlı kısa vadeli bir sistem ve Spike[ adlı uzun vadeli bir planlama sistemi kullanır.
Kaynak:
https://en.wikipedia.org/wiki/Automated_planning_and_scheduling
Wiki Kaynaklar:
1)Ghallab, Malik; Nau, Dana S.; Traverso, Paolo (2004), Automated Planning: Theory and Practice, Morgan Kaufmann, ISBN 1-55860-856-7
2)Vidal, Thierry (January 1999). “Handling contingency in temporal constraint networks: from consistency to controllabilities”. Journal of Experimental & Theoretical Artificial Intelligence. 11 (1): 23–45. CiteSeerX 10.1.1.107.1065. doi:10.1080/095281399146607.
3)Neufeld, Xenija and Mostaghim, Sanaz and Sancho-Pradel, Dario and Brand, Sandy (2017). “Building a Planner: A Survey of Planning Systems Used in Commercial Video Games”. IEEE Transactions on Games. IEEE.
4)Sanelli, Valerio and Cashmore, Michael and Magazzeni, Daniele and Iocchi, Luca (2017). Short-term human robot interaction through conditional planning and execution. Proc. of International Conference on Automated Planning and Scheduling (ICAPS).
5)Peot, Mark A and Smith, David E (1992). Conditional nonlinear planning (PDF). Artificial Intelligence Planning Systems. Elsevier. pp. 189–197.
6)Karlsson, Lars (2001). Conditional progressive planning under uncertainty. IJCAI. pp. 431–438.
7)Liu, Daphne Hao (2008). A survey of planning in intelligent agents: from externally motivated to internally motivated systems (Technical report). Technical Report TR-2008-936, Department of Computer Science, University of Rochester.
8)Alexandre Albore; Hector Palacios; Hector Geffner (2009). A Translation-Based Approach to Contingent Planning. International Joint Conference of Artificial Intelligence (IJCAI). Pasadena, CA: AAAI.
9)Littman, Michael L. (1997). Probabilistic Propositional Planning: Representations and Complexity. Fourteenth National Conference on Artificial Intelligence. MIT Press. pp. 748–754. Retrieved 2019-02-10.
10)Jussi Rintanen (2004). Complexity of Planning with Partial Observability (PDF). Int. Conf. Automated Planning and Scheduling. AAAI.
11)De Giacomo, Giuseppe; Rubin, Sasha (2018). Automata-Theoretic Foundations of FOND Planning for LTLf and LDLf Goals. IJCAI. Retrieved 2018-07-17.
12)Palacios, Hector; Geffner, Hector (2009). “Compiling uncertainty away in conformant planning problems with bounded width”. Journal of Artificial Intelligence Research. 35: 623–675. doi:10.1613/jair.2708.
13)Albore, Alexandre; Ramírez, Miquel; Geffner, Hector (2011). Effective heuristics and belief tracking for planning with incomplete information. Twenty-First International Conference on Automated Planning and Scheduling (ICAPS).
14)Haslum, Patrik; Jonsson, Peter (2000). “Some Results on the Complexity of Planning with Incomplete Information”. Recent Advances in AI Planning. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 1809: 308–318. doi:10.1007/10720246_24. ISBN 9783540446576.
