Automatizált tervezés és ütemezés - Automated planning and scheduling

Sorozat része
Mesterséges intelligencia
Főbb célok
Megközelít
Filozófia
Történelem
Technológia
Szójegyzék

Az automatizált tervezés és ütemezés , amelyet néha egyszerűen AI-tervezésnek neveznek, a mesterséges intelligencia olyan ága, amely stratégiák vagy cselekvési szekvenciák megvalósítását érinti , általában intelligens ügynökök , autonóm robotok és pilóta nélküli járművek általi végrehajtásra . A klasszikus ellenőrzési és osztályozási problémáktól eltérően a megoldások összetettek, és ezeket többdimenziós térben kell felfedezni és optimalizálni. A tervezés a döntéselmélettel is összefügg .

A rendelkezésre álló modellekkel rendelkező ismert környezetekben a tervezés offline is elvégezhető. A megoldások megtalálhatók és kiértékelhetők a végrehajtás előtt. Dinamikusan ismeretlen környezetekben a stratégiát gyakran online kell felülvizsgálni. A modelleket és irányelveket ki kell igazítani. A megoldások általában a mesterséges intelligenciában gyakran előforduló iteratív próba- és hibafolyamatokhoz folyamodnak . Ezek közé tartozik a dinamikus programozás , a megerősítő tanulás és a kombinatorikus optimalizálás . A tervezés és az ütemezés leírására használt nyelveket gyakran cselekvési nyelveknek nevezik .

Áttekintés

További információ: Állami űrkutatás

A világ lehetséges kezdeti állapotainak leírása, a kívánt célok leírása és a lehetséges cselekvések halmazának leírása alapján a tervezési probléma egy garantált terv szintetizálása (ha bármelyik kezdeti állapotra alkalmazzák). olyan állapot létrehozása, amely tartalmazza a kívánt célokat (ezt az állapotot célállapotnak hívják).

A tervezés nehézsége az alkalmazott egyszerűsítő feltételezésektől függ. A tervezési problémák több osztályát lehet megkülönböztetni a problémák több dimenzióban lévő tulajdonságaitól függően.

  • A cselekvések determinisztikusak vagy nem determinisztikusak? A nemdeterminisztikus cselekvésekhez rendelkezésre állnak-e a kapcsolódó valószínűségek?
  • Az állapotváltozók diszkrétek vagy folytonosak? Ha diszkrétek, akkor csak véges számú lehetséges értékük van?
  • Megfigyelhető-e egyértelműen a jelenlegi állapot? Lehet teljes megfigyelhetőség és részleges megfigyelhetőség.
  • Hány kezdeti állapot van, véges vagy önkényesen sok?
  • Van-e időtartama a cselekvéseknek?
  • Lehetséges-e egyidejűleg több művelet végrehajtása, vagy egyszerre csak egy művelet lehetséges?
  • A terv célja a kijelölt célállapot elérése, vagy a jutalomfüggvény maximalizálása ?
  • Csak egy ügynök van, vagy több ügynök van? Az ügynökök kooperatívak vagy önzőek? Az összes ügynök külön elkészíti a saját tervét, vagy a terveket központilag állítják össze az összes ügynök számára?

A lehető legegyszerűbb tervezési problémát, amelyet klasszikus tervezési problémának nevezünk, a következők határozzák meg:

  • egyedi ismert kezdeti állapot,
  • tartós akciók,
  • determinisztikus cselekedetek,
  • amelyet egyszerre csak egyet lehet venni,
  • és egyetlen ügynök.

Mivel a kezdeti állapot egyértelműen ismert, és minden cselekvés determinisztikus, a cselekvéssorozatok utáni világállapot pontosan megjósolható, és a megfigyelhetőség kérdése a klasszikus tervezés szempontjából irreleváns.

Ezenkívül a tervek meghatározhatók mint műveletsorozatok, mivel mindig előre lehet tudni, hogy mely cselekvésekre lesz szükség.

A nem determinisztikus cselekedetek vagy az ügynök hatáskörén kívül eső egyéb események esetén a lehetséges kivégzések fát alkotnak, és a terveknek meg kell határozniuk a fa minden csomópontjának megfelelő műveleteket.

A diszkrét idejű Markov döntési folyamatok (MDP) problémákat terveznek:

  • tartós akciók,
  • nemdeterminisztikus valószínűségű cselekvések,
  • teljes megfigyelhetőség,
  • a jutalom függvény maximalizálása,
  • és egyetlen ügynök.

Amikor a teljes megfigyelhetőséget részleges megfigyelhetőség váltja fel, a tervezés megfelel a részben megfigyelhető Markov-döntési folyamatnak (POMDP).

Ha egynél több ügynök van, akkor több ügynököt tervezünk , amely szorosan összefügg a játékelmélettel .

Tartománytól független tervezés

Az AI-tervezés során a tervezők általában bevetnek egy tartományi modellt (a tartományt modellező lehetséges cselekvések halmazának leírását), valamint a kezdeti állapot és a cél által meghatározott megoldandó problémát, ellentétben azokkal, amelyekben nincs bemeneti tartomány megadva. Az ilyen tervezőket "tartományfüggetleneknek" nevezik, hogy hangsúlyozzák azt a tényt, hogy a tervezési problémákat sokféle tartományból képesek megoldani. A tartományok tipikus példái a blokk-egymásra rakás, logisztika, munkafolyamat-kezelés és robotfeladat-tervezés. Ezért egyetlen tartománytól független tervező használható a tervezési problémák megoldására ezekben a különböző területeken. Másrészt az útvonaltervező jellemző a tartományspecifikus tervezőkre.

Domainmodellező nyelvek tervezése


A leggyakrabban használt nyelvek képviselő tervezés tartományok és a konkrét tervezési problémák, mint például frízek és PDDL A klasszikus tervezés, alapul állapotváltozók. A világ minden lehetséges állapota az értékek hozzárendelése az állapotváltozókhoz, és a műveletek határozzák meg, hogyan változnak az állapotváltozók értékei, amikor ezt a műveletet végrehajtják. Mivel az állapotváltozók halmaza olyan állapotteret indukál, amelynek mérete a halmazban exponenciális, a tervezés, hasonlóan sok más számítási problémához, szenved a dimenzió átkától és a kombinatorikus robbanástól .

A tervezési problémák leírásának alternatív nyelve a hierarchikus feladathálózatok nyelve, amelyben feladatsor kerül megadásra, és mindegyik feladat primitív művelettel megvalósítható, vagy más feladatok halmazává bontható. Ez nem feltétlenül tartalmaz állapotváltozókat, bár a reálisabb alkalmazásokban az állapotváltozók leegyszerűsítik a feladathálózatok leírását.

Algoritmusok a tervezéshez

Klasszikus tervezés

Lásd még: Sussman anomália

Csökkentés más problémákra

  • redukció a propozíciós elégedettség problémájára ( satplan ).
  • csökkentés a modellellenőrzésre - mindkettő lényegében az állapotterek bejárásának problémája, és a klasszikus tervezési probléma megfelel a modellellenőrzési problémák egyik alosztályának.

Időbeli tervezés

Az időbeli tervezés a klasszikus tervezéshez hasonló módszerekkel oldható meg. A legfőbb különbség az a lehetőség, hogy több időbeli átfedésben lévő időtartam egyidejűleg végezhető, és hogy az állapot meghatározásának tartalmaznia kell az aktuális abszolút időre vonatkozó információkat és azt, hogy az egyes aktív műveletek végrehajtása mennyire haladt előre. Továbbá, a racionális vagy valós idejű tervezés során az állapottér végtelen lehet, ellentétben a klasszikus tervezéssel vagy az egész idővel történő tervezéssel. Az időbeli tervezés szorosan kapcsolódik az ütemezési problémákhoz. Az időbeli tervezés az időzített automaták szempontjából is érthető .

Valószínűségi tervezés

Fő cikkek: Markov döntési folyamata és részben megfigyelhető Markov döntési folyamat

A valószínűségi tervezés olyan iteratív módszerekkel oldható meg, mint az érték-iteráció és a politikai iteráció , amikor az állapottér kellően kicsi. Részleges megfigyelhetőséggel a valószínűségi tervezés hasonlóan megoldható iteratív módszerekkel, de állapotok helyett a hiedelmek terére meghatározott értékfüggvények ábrázolását használja.

Preferenciákon alapuló tervezés

Fő cikk: Preferenciákon alapuló tervezés

A preferencia-alapú tervezésnél a cél nemcsak egy terv elkészítése, hanem a felhasználó által megadott preferenciák kielégítése is . Különbség a gyakoribb jutalomalapú tervezésben, például az MDP-knek megfelelően, a preferenciáknak nem feltétlenül van pontos számértéke.

Feltételes tervezés

A determinisztikus tervezés bevezetése a STRIPS tervezési rendszerrel történt, amely egy hierarchikus tervező. Az akciónevek sorrendben vannak rendezve, és ez a robot terve. A hierarchikus tervezés összehasonlítható egy automatikusan generált viselkedési fával . Hátránya, hogy a normális viselkedésfa nem annyira kifejező, mint egy számítógépes program. Ez azt jelenti, hogy egy viselkedési gráf jelölése műveletparancsokat tartalmaz, de nem tartalmaz ciklusokat vagy if-then-utasításokat. A feltételes tervezés leküzdi a szűk keresztmetszetet, és bevezet egy kidolgozott jelölést, amely hasonló a vezérlési folyamathoz , amely más programozási nyelvekből, például a Pascalból ismert . Nagyon hasonlít a programszintézishez , ami azt jelenti, hogy a tervező forráskódot állít elő , amelyet egy tolmács hajthat végre.

A feltételes tervező korai példája a „Warplan-C”, amelyet az 1970-es évek közepén vezettek be. Mi a különbség a normál sorrend és a bonyolult terv között, amely if-then-utasításokat tartalmaz? Ennek köze van a terv futásidejű bizonytalanságához . Az elképzelés az, hogy egy terv reagálhat olyan érzékelő jelekre, amelyek ismeretlenek a tervező számára. A tervező két választási lehetőséget generál előre. Például, ha egy objektumot észleltek, akkor az A műveletet hajtják végre, ha egy objektum hiányzik, akkor a B műveletet hajtják végre. A feltételes tervezés fő előnye a részleges tervek kezelésének képessége . Az ügynök nem kénytelen mindent megtervezni az elejétől a végéig, de darabokra oszthatja a problémát . Ez segít csökkenteni az állapotot és sokkal összetettebb problémákat old meg.

Kontingens tervezés

"Kontingens tervezésről" beszélünk, amikor a környezet érzékelőkön keresztül megfigyelhető, ami hibás lehet. Ez tehát egy olyan helyzet, amikor a tervező ügynök hiányos információk alatt jár el. Egy esetleges tervezési probléma esetén a terv már nem egy cselekvéssorozat, hanem egy döntési fa, mert a terv minden egyes lépését állapotok halmaza képviseli, nem pedig egyetlen tökéletesen megfigyelhető állapot, mint például a klasszikus tervezés esetében. A kiválasztott műveletek a rendszer állapotától függenek. Például, ha esik az eső, az ügynök úgy dönt, hogy elveszi az esernyőt, és ha nem, akkor dönthet úgy, hogy nem veszi.

Michael L. Littman 1998-ban megmutatta, hogy az elágazó akciókkal a tervezési probléma EXPTIME-teljessé válik . Az összefüggő tervezés egy konkrét esetét FOND problémák jelentik - "teljesen megfigyelhető és nem determinisztikus" értelemben. Ha a cél az LTLf-ben van megadva (lineáris időlogika a véges nyomon), akkor a probléma mindig EXPTIME-teljes és 2EXPTIME-teljes, ha a célt LDLf-vel adjuk meg.

Megfelelő tervezés

A megfelelő tervezés az, amikor az ügynök bizonytalan a rendszer állapotában, és nem tehet észrevételeket. Az ügynöknek akkor meggyőződése van a való világról, de például érzékelési cselekedetekkel nem tudja igazolni őket. Ezeket a problémákat a klasszikus tervezéshez hasonló technikákkal oldják meg, de ahol az állapottér a probléma méretében exponenciális, a jelenlegi állapot bizonytalansága miatt. Megfelelő tervezési probléma megoldása a műveletsor. Haslum és Jonsson bebizonyították, hogy a probléma az alkalmazkodó tervezés EXPSPACE -teljes és 2EXPTIME-teljes, ha a kezdeti helyzet bizonytalan, és van nem determinizmus az akciók kimenetelét.

Tervezési rendszerek kiépítése

Lásd még

Listák

Hivatkozások

További irodalom

Külső linkek