Otomatik planlama ve çizelgeleme - Automated planning and scheduling

Bir dizinin parçası
Yapay zeka

Otomatik planlama ve çizelgeleme, bazen basitçe ifade edilir AI planlaması,[1] bir dalı yapay zeka gerçekleştirilmesi ile ilgili stratejiler veya eylem dizileri, tipik olarak yürütme için akıllı ajanlar, otonom robotlar ve insansız araçlar. Klasiklerin aksine kontrol ve sınıflandırma sorunlar, çözümler karmaşıktır ve çok boyutlu uzayda keşfedilmeli ve optimize edilmelidir. Planlama şunlarla da ilgilidir: karar teorisi.

Mevcut modellerin olduğu bilinen ortamlarda, planlama çevrimdışı yapılabilir. Çözümler uygulama öncesinde bulunabilir ve değerlendirilebilir. Dinamik olarak bilinmeyen ortamlarda, strateji genellikle çevrimiçi olarak revize edilmesi gerekir. Modeller ve politikalar uyarlanmalıdır. Çözümler genellikle yinelemeye başvurur Deneme ve hata yaygın olarak görülen süreçler yapay zeka. Bunlar arasında dinamik program, pekiştirmeli öğrenme ve kombinatoryal optimizasyon. Planlama ve çizelgelemeyi açıklamak için kullanılan diller genellikle eylem dilleri.

Genel Bakış

Daha fazla bilgi: Durum alanı araması

Dünyanın olası başlangıç ​​durumlarının bir açıklaması, istenen hedeflerin bir açıklaması ve bir dizi olası eylemin açıklaması göz önüne alındığında, planlama sorunu garanti edilen bir planı sentezlemektir (başlangıç ​​durumlarından herhangi birine uygulandığında) istenen 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 birkaç boyutta sahip olduğu özelliklere bağlı olarak birkaç planlama problemi sınıfı tanımlanabilir.

  • Eylemler belirleyici veya deterministik olmayan? Belirsiz olmayan eylemler için, ilişkili olasılıklar mevcut mu?
  • Bunlar durum değişkenleri ayrık mı sürekli mi? Ayrık iseler, sadece sınırlı sayıda olası değerleri mi var?
  • Mevcut durum net bir şekilde gözlemlenebilir mi? Tam gözlemlenebilirlik ve kısmi gözlemlenebilirlik olabilir.
  • Kaç tane başlangıç ​​durumu vardır, sonlu veya keyfi olarak çok sayıda?
  • Eylemlerin süresi var mı?
  • Aynı anda birden fazla eylem yapılabilir mi, yoksa bir seferde yalnızca bir eylem mümkün müdür?
  • Bir planın amacı, belirlenmiş bir hedef durumuna ulaşmak veya bir ödül işlevi ?
  • Yalnızca bir temsilci mi var yoksa birden fazla aracı mı var? Temsilciler işbirlikçi mi yoksa bencil mi? Tüm temsilciler kendi planlarını ayrı ayrı mı oluşturuyor yoksa planlar tüm temsilciler için merkezi olarak mı inşa ediliyor?

Klasik Planlama Problemi olarak bilinen en basit olası planlama problemi şu şekilde belirlenir:

  • benzersiz bir bilinen başlangıç ​​durumu,
  • süresiz eylemler,
  • deterministik eylemler,
  • her seferinde sadece bir tane alınabilir,
  • ve tek bir ajan.

Başlangıç ​​durumu açık bir şekilde bilindiğinden ve tüm eylemler deterministik olduğundan, herhangi bir eylem dizisinden sonraki dünyanın durumu doğru bir şekilde tahmin edilebilir ve gözlemlenebilirlik sorunu klasik planlama ile ilgisizdir.

Ayrıca planlar, eylem dizileri olarak tanımlanabilir, çünkü her zaman önceden hangi eylemlere ihtiyaç duyulacağı bilinmektedir.

Belirleyici olmayan eylemler veya temsilcinin kontrolü dışındaki diğer olaylarla, olası yürütmeler bir ağaç oluşturur ve planların ağacın her düğümü için uygun eylemleri belirlemesi gerekir.

Ayrık zaman Markov karar süreçleri (MDP) şunlarla ilgili sorunları planlıyor:

  • süresiz eylemler,
  • olasılıklı belirleyici olmayan eylemler,
  • tam gözlemlenebilirlik,
  • bir ödül işlevinin maksimizasyonu,
  • ve tek bir ajan.

Tam gözlemlenebilirliğin yerini kısmi gözlemlenebilirlik aldığında, planlama şuna karşılık gelir: kısmen gözlemlenebilir Markov karar süreci (POMDP).

Birden fazla temsilci varsa, çok temsilcili planlama ile yakından ilgili olan oyun Teorisi.

Etki alanından bağımsız planlama

Yapay zeka planlamasında, planlamacılar tipik olarak bir alan modeli (alanı modelleyen bir dizi olası eylemin açıklaması) ve aynı zamanda çözülmesi gereken belirli problemi ilk durum ve hedef tarafından belirlenmemiş olanların aksine girerler. girdi alanı belirtildi. Bu tür planlayıcılar, planlama problemlerini çok çeşitli alanlardan çözebileceklerini vurgulamak için "alandan bağımsız" olarak adlandırılır. Tipik etki alanı örnekleri blok istifleme, lojistik, iş akışı yönetimi ve robot görev planlamasıdır. Bu nedenle, 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.

Alan modelleme dillerini planlama

Planlama alanlarını ve belirli planlama problemlerini temsil etmek için en yaygın kullanılan diller, örneğin ŞERİTLER ve PDDL Klasik Planlama için durum değişkenlerine dayalıdır. Dünyanın her olası durumu, durum değişkenlerine değerlerin atanmasıdır ve eylemler, bu eylem gerçekleştirildiğinde durum değişkenlerinin değerlerinin nasıl değiştiğini belirler. Bir dizi durum değişkeni, kümede üstel olan bir boyuta sahip bir durum uzayını indüklediğinden, planlama, diğer birçok hesaplama problemine benzer şekilde, boyutluluk laneti ve kombinatoryal patlama.

Planlama problemlerini tanımlamak için alternatif bir dil, hiyerarşik görev ağları, bir dizi görevin verildiği ve her bir görev ya ilkel bir eylemle gerçekleştirilebilir ya da bir dizi başka göreve ayrılabilir. Daha gerçekçi uygulamalarda durum değişkenleri görev ağlarının açıklamasını basitleştirse de, bu durum değişkenlerini içermek zorunda değildir.

Planlama için algoritmalar

Klasik planlama

Ayrıca bakınız: Sussman anomalisi

Diğer sorunlara indirgeme

  • indirgeme önerme tatmini sorun (uydu planı ).
  • indirgeme Model kontrolü - her ikisi de esasen durum uzaylarını geçme 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, bir süre eşzamanlı olarak alınan birkaç, zamansal olarak örtüşen eylem olasılığı nedeniyle, bir durumun tanımının mevcut mutlak zaman ve her bir etkin eylemin uygulanmasının ne kadar ilerlediğine ilişkin bilgileri içermesi gerektiğidir. Dahası, rasyonel veya gerçek zamanlı planlamada, klasik planlama veya tamsayı zamanlı planlamadan farklı olarak durum uzayı sonsuz olabilir. Zamansal planlama yakından ilgilidir zamanlama Zaman planlaması aynı zamanda şu terimlerle de anlaşılabilir: zamanlı otomata.

Olasılıklı planlama

Ana makaleler: Markov karar süreci ve Kısmen gözlemlenebilir Markov karar süreci

Olasılıksal planlama gibi yinelemeli yöntemlerle çözülebilir. değer yinelemesi ve politika yinelemesi Durum uzayı yeterince küçük olduğunda. Kısmi gözlemlenebilirlik ile, olasılıksal planlama benzer şekilde yinelemeli yöntemlerle çözülür, ancak durumlar yerine inançlar alanı için tanımlanan değer işlevlerinin bir temsilini kullanır.

Tercihe dayalı planlama

Ana makale: Tercihe dayalı planlama

Tercihe dayalı planlamada amaç sadece bir plan üretmek değil, aynı zamanda kullanıcının belirlediği tatmin etmektir. tercihler. Daha yaygın olan ödül temelli planlamadaki bir fark, örneğin MDP'lere karşılık gelen tercihlerin kesin bir sayısal değeri olması gerekmez.

Koşullu planlama

Deterministik planlama, ŞERİTLER hiyerarşik bir planlayıcı olan planlama sistemi. Eylem adları sırayla sıralanır ve bu robot için bir plandır. Hiyerarşik planlama, otomatik olarak oluşturulmuş bir davranış ağacı.[2] Dezavantajı, normal bir davranış ağacının bir bilgisayar programı gibi ifade edici olmamasıdır. Bu, bir davranış grafiğinin gösteriminin eylem komutları içerdiği, ancak döngüler veya eğer-ise-ifadeleri. Koşullu planlama, darboğazın üstesinden gelir ve aşağıdakine benzer ayrıntılı bir gösterim sunar. kontrol akışı, diğer programlama dillerinden bilinmektedir. Pascal. Çok benzer program sentezi Bu, bir planlayıcının bir yorumlayıcı tarafından çalıştırılabilen kaynak kodu ürettiği anlamına gelir.[3]

Koşullu planlayıcının erken bir örneği, 1970'lerin ortasında tanıtılan "Warplan-C" dir.[4] Normal bir sıra ile eğer-sonra-ifadeleri içeren karmaşık bir plan arasındaki fark nedir? Belirsizlikle ilgisi var Çalışma süresi bir planın. Buradaki fikir, bir planın tepki verebilmesidir. sensör sinyalleri planlayıcı için bilinmeyen. Planlayıcı önceden iki seçenek üretir. Örneğin, bir nesne algılanırsa, A eylemi yürütülür, bir nesne eksikse eylem B yürütülür.[5] Koşullu planlamanın önemli bir avantajı, kısmi planlar.[6] Bir temsilci her şeyi baştan sona planlamak zorunda değildir, ancak sorunu şu şekilde bölebilir: parçalar. Bu, durum alanını azaltmaya yardımcı olur ve çok daha karmaşık sorunları çözer.

Koşullu planlama

Çevre sensörler aracılığıyla gözlemlenebilir olduğunda "koşullu planlamadan" bahsediyoruz, bu hatalı olabilir. Dolayısıyla, planlama görevlisinin eksik bilgi altında hareket ettiği bir durumdur. Koşullu bir planlama problemi için, plan artık bir eylemler dizisi değil, karar ağacı çünkü planın her adımı, klasik planlama örneğinde olduğu gibi, mükemmel bir şekilde gözlemlenebilir tek bir durumdan ziyade bir dizi durumla temsil edilir.[7] Seçilen eylemler sistemin durumuna bağlıdır. Örneğin, yağmur yağarsa, ajan şemsiyeyi almayı seçer ve yağmur yağmazsa almamayı tercih edebilir.

Mikael L. Littman, 1998'de dallanma eylemleriyle planlama sorununun EXPTIME -tamamlayınız.[8][9] Belirli bir bitişik planlama durumu, "tamamen gözlemlenebilir ve deterministik olmayan" için FOND problemleriyle temsil edilir. Hedef LTLf'de belirtilmişse (sonlu izlemede doğrusal zaman mantığı), sorun her zaman EXPTIME-tamamlanmıştır[10] ve 2Hedef LDLf ile belirtilmişse EXPTIME-tamamlandı.

Uygun planlama

Uygun planlama, temsilcinin sistemin durumu hakkında emin olmadığı ve herhangi bir gözlem yapamadığı zamandır. Bu durumda temsilci, gerçek dünya hakkında inançlara sahip olur, ancak bunları örneğin algılama eylemleriyle doğrulayamaz. Bu sorunlar, klasik planlamaya benzer tekniklerle çözülür,[11][12] ancak durum uzayı, mevcut durum hakkındaki belirsizlik nedeniyle problemin boyutunda üsteldir. Uyumlu bir planlama probleminin çözümü, bir dizi eylemdir. Haslum ve Jonsson, uyumlu planlama sorununun EXPSPACE -tamamlayınız,[13] ve 2Başlangıçtaki durum belirsiz olduğunda ve eylemlerin sonuçlarında determinizm olmadığında EXPTIME-tamamlandı.[9]

Planlama sistemlerinin yerleştirilmesi

Ayrıca bakınız

Listeler

Referanslar

  1. ^ Ghallab, Malik; Nau, Dana S .; Traverso, Paolo (2004), Otomatik Planlama: Teori ve Uygulama, Morgan Kaufmann, ISBN  1-55860-856-7
  2. ^ Neufeld, Xenija ve Mostaghim, Sanaz ve Sancho-Pradel, Dario ve Brand, Sandy (2017). "Bir Planlayıcı Oluşturmak: Ticari Video Oyunlarında Kullanılan Planlama Sistemleri Üzerine Bir Araştırma". Oyunlarda IEEE İşlemleri. IEEE.CS1 bakım: birden çok isim: yazarlar listesi (bağlantı)
  3. ^ Sanelli, Valerio ve Cashmore, Michael ve Magazzeni, Daniele ve Iocchi, Luca (2017). Koşullu planlama ve yürütme yoluyla kısa vadeli insan robot etkileşimi. Proc. Uluslararası Otomatik Planlama ve Çizelgeleme Konferansı (ICAPS).CS1 bakım: birden çok isim: yazarlar listesi (bağlantı)
  4. ^ Peot, Mark A ve Smith, David E (1992). Koşullu doğrusal olmayan planlama (PDF). Yapay Zeka Planlama Sistemleri. Elsevier. s. 189–197.CS1 bakım: birden çok isim: yazarlar listesi (bağlantı)
  5. ^ Karlsson, Lars (2001). Belirsizlik altında koşullu aşamalı planlama. IJCAI. s. 431–438.
  6. ^ Liu, Daphne Hao (2008). Akıllı aracılarda planlama anketi: dışarıdan motive edilen sistemlerden dahili olarak motive edilen sistemlere (Teknik rapor). Teknik Rapor TR-2008-936, Bilgisayar Bilimleri Bölümü, Rochester Üniversitesi.
  7. ^ Alexandre Albore; Hector Palacios; Hector Geffner (2009). Koşullu Planlamaya Çeviriye Dayalı Bir Yaklaşım. Uluslararası Ortak Yapay Zeka Konferansı (IJCAI). Pasadena, CA: AAAI.
  8. ^ Littman, Michael L. (1997). Olasılıksal Önerme Planlama: Temsiller ve Karmaşıklık. Ondördüncü Ulusal Yapay Zeka Konferansı. MIT Basın. s. 748–754. Alındı 2019-02-10.
  9. ^ a b Jussi Rintanen (2004). Kısmi Gözlenebilirlik ile Planlamanın Karmaşıklığı (PDF). Int. Conf. Otomatik Planlama ve Çizelgeleme. AAAI.
  10. ^ De Giacomo, Giuseppe; Rubin Sasha (2018). LTLf ve LDLf Hedefleri için FOND Planlamasının Otomata-Teorik Temelleri. IJCAI. Alındı 2018-07-17.
  11. ^ Palacios, Hector; Geffner, Hector (2009). "Sınırlı genişliğe sahip uygun planlama problemlerinde belirsizliği derlemek". Yapay Zeka Araştırmaları Dergisi. 35: 623–675. doi:10.1613 / jair.2708.
  12. ^ Albore, Alexandre; Ramírez, Miquel; Geffner, Hector (2011). Eksik bilgilerle planlama için etkili buluşsal yöntemler ve inanç takibi. Otomatikleştirilmiş Planlama ve Çizelgeleme Üzerine Yirmi Birinci Uluslararası Konferans (ICAPS).
  13. ^ Haslum, Patrik; Jonsson, Peter (2000). "Eksik Bilgiyle Planlamanın Karmaşıklığına İlişkin Bazı Sonuçlar". AI Planlamadaki Son Gelişmeler. Bilgisayar Bilimlerinde Ders Notları. Springer Berlin Heidelberg. 1809: 308–318. doi:10.1007/10720246_24. ISBN  9783540446576.

daha fazla okuma

Dış bağlantılar