Ugrás a tartalomhoz

automated planning and scheduling

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

automated planning and scheduling (tsz. automated planning and schedulings)

  1. (informatika, mesterséges intelligencia) Az automated planning and scheduling (magyarul: automatizált tervezés és ütemezés) a mesterséges intelligencia egyik kulcsterülete, amely a jövőbeli cselekvéssorozatok automatikus megtervezésével foglalkozik, hogy egy rendszer elérjen egy kívánt célt egy adott környezetben. Alkalmazási területei széleskörűek: robotika, logisztika, gyártás, űrkutatás, videojátékok, egészségügy, stb.


2. Fogalmi alapok

a) Planning (tervezés)

A cél: megtalálni egy cselekvéssorozatot (akciók szekvenciája), amely egy kezdeti állapotból eljuttatja a rendszert egy kívánt célállapotba.

b) Scheduling (ütemezés)

A cél: megtervezni időbeli elrendezését a már meghatározott tevékenységeknek, figyelembe véve az erőforrásokat, korlátozásokat és prioritásokat.


3. Tervezési problémák általános modellje

Egy tipikus tervezési probléma formálisan leírható a következőkkel:

  • Állapotok halmaza (S): a világ lehetséges konfigurációi
  • Kezdeti állapot (s₀): a kiinduló helyzet
  • Célállapotok halmaza (G): az elfogadható végállapotok
  • Akciók halmaza (A): minden akció pre- és posztfeltételekkel rendelkezik (mit igényel, mit változtat)
  • Tranzíciós függvény: megadja, hogy egy akció hogyan változtatja meg az állapotot

A cél egy cselekvéssorozat megtalálása, amely:

  • indul s₀-ból
  • alkalmazható egymás után
  • eljuttat egy g ∈ G célállapotba


4. Példák gyakorlati alkalmazásokra

  • Robotika: egy robot megtervezi az útvonalát és cselekedeteit a környezetében.
  • Űrmissziók: a NASA használja például a Deep Space One fedélzeti autonóm irányításához.
  • Gyártásütemezés: gépek munkáinak optimalizálása erőforrás- és időhatékonyság szempontjából.
  • Intelligens asszisztensek: feladatlisták kezelése, meetingek időzítése.
  • Videójátékok: nem játékos karakterek (NPC-k) viselkedésének tervezése.


5. Tervezési technikák

a) Keresésen alapuló tervezés

  • State-space search: a rendszer bejárja az állapottér gráfját
    • Forward search: a kezdeti állapottól indul
    • Backward search: a célállapottól visszafelé halad
  • Heurisztikákat is alkalmazhat (pl. A* algoritmus)

b) Hierarchikus tervezés (HTN)

A célokat magas szintű tevékenységekre bontja le, amelyeket alacsonyabb szintű alfeladatokra hierarchikusan oszt le.

c) Partiális rendű tervezés (POP)

Nem kell az összes akciót lineáris sorrendbe állítani, elegendő a részleges sorrendiség – ez rugalmasságot ad.

d) Contingent Planning

Bizonytalan környezetben több forgatókönyvet vesz figyelembe (pl. mi van, ha egy ajtó zárva van?).

e) Probabilistic Planning

A világ nem determinisztikus, akciók eredménye valószínűségi eloszlással írható le (pl. Markov Decision Process).


6. Ütemezési problémák típikus elemei

  • Feladatok (task/job): elvégzendő egységek
  • Erőforrások (resource): gépek, munkások, időrés
  • Korlátok (constraints): például határidők, sorrendiség, kizárások

Példák:

  • Job-shop scheduling: gépeken végzendő műveletek időzítése
  • Task allocation: adott számú robot vagy gép között hogyan osszuk el a feladatokat
  • Timetabling: iskolai órarend készítése


7. Ütemezési algoritmusok

  • Prioritásos listás algoritmusok: egyszerű szabályokon alapuló (pl. legrövidebb határidő először)
  • Constraint programming: korlátok formális nyelvi leírása alapján keres megoldást
  • Integer Programming: egész számú változókat kezelő optimalizálási módszer
  • Metaheurisztikák: genetikus algoritmus, tabu search, simulated annealing


8. Planning vs. Scheduling összehasonlítás

Tulajdonság Tervezés (Planning) Ütemezés (Scheduling)
Mi a cél? Milyen akciókat hajtsunk végre? Mikor és melyik erőforrással?
Fő tényező Akciók logikai sorrendje Idő és erőforrás korlátok
Jellemző input Kezdő és célállapot, akciók Feladatok, határidők, erőforrás-korlátok
Példa Robot navigálása szobák között Robot útvonalának időbeli ütemezése


9. Kihívások és kutatási irányok

  • Skálázhatóság: nagy állapottér kezelése
  • Bizonytalanság: érzékelési hibák, véletlenszerű események
  • Tanulás és adaptáció: a rendszer idővel tanuljon, például megerősítéses tanulással
  • Kombinált modellek: tervezés + ütemezés együttes kezelése


10. Eszközök és keretrendszerek

  • PDDL (Planning Domain Definition Language): formális nyelv tervezési problémák leírására
  • STRIPS: az egyik első tervezőrendszer
  • Fast Downward: modern PDDL-alapú tervező
  • ROSPlan: robotikai környezetekre épülő tervezési modul
  • OptaPlanner: Java-alapú nyílt forráskódú ütemező motor


11. Összegzés

Az automatizált tervezés és ütemezés kritikus fontosságú minden olyan rendszer számára, amelynek önállóan kell döntéseket hoznia a célok elérése érdekében, figyelembe véve a környezetet, az időt és az erőforrásokat. A mesterséges intelligencia ezen területe képes a problémák formális modellezésére, hatékony algoritmusok alkalmazására, és egyre fontosabb szerepet kap az autonóm rendszerek világában.


További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=automated_planning_and_scheduling&oldid=3501883”