FIT ČVUT Course Pages
BI-ZUM — Základy umělé inteligence
Jdi na navigaci předmětu

Plánování, jazyk PDDL

Zpět na výběr úloh

Úloha 1: Rover Perseverance na Marsu

task 1 map
Obrázek 1. Mapa okolí roveru Perseverance (rover se nachází na středu pole, kde je zobrazeno jeho tělo a je zvětšen pro snazší identifikaci)

Rover Perseverance se nachází na povrchu Marsu v oblasti kráteru Jezero. Okolí roveru zahrnuje různé terénní překážky a vědecké cíle. Prostředí je rozděleno do mřížky, kde každá buňka může obsahovat různé typy terénu (rovný povrch, kamenitý terén, písečné duny) a objekty (materiál určený k vědecké analýze, překážky). Jedna buňka může (zejména na přechodu dvou typů terénu) obsahovat více typů terénu (např. tak můžeme mít buňku s písečnými dunami i kamenitým terénem). Detailní průzkum terénu zajištuje vrtulník Ingenuity, který potřebuje k autonomnímu letu orientační body. Při navigaci je důležité, aby se rover příliš nevzdálil (více než 2 pole v pole v Manhattanské vzdálenosti) od orientačních bodů, které poskytuje rovný povrch či kamenitý terén a vrtulník mu tak mohl asistovat během cesty. Je potřeba, aby rover dojel na každé pole s materiálem určeným k vědecké analýze a odebral a analyzoval vzorek. Při pohybu se rover musí vyhnout polím s kamenitým terénem, kde by rover neprojel a jsou tedy pro rover překážkou. Pohyb roveru je zajištěn akcemi popojeď o 1 pole vpřed, otoč se doleva a otoč se doprava.

  1. Navrhněte doménu v jazyce PDDL
  2. Navrhněte úlohu podle mapy. A nechte ji vyřešit pomocí webového solveru.

Úloha 2: Úklid kancelářských prostor

Vaším úkolem je vytvořit PDDL popis domény a tři problémy v této doméně. Doména se bude týkat plánování úklidu kancelářských prostor. Kancelářské prostory obsahují různé místnosti, které je třeba uklidit, a různé typy úklidových činností, které je třeba provést. My se zaměříme na dva typy činností – oprašování prachovkou a vytírání mopem. Vždy je potřeba místnost nejprve zbavit prachu, než může být vytřena.

  1. Doména:
    • Definujte typy objektů (např. místnosti, úklidové nástroje mop a prachovku, úklidové činnosti oprášit a vytřít).
    • Definujte predikáty (např. je-čistá, je-oprášená má-nástroj, je-v-místnosti).
    • Definujte akce (např. zamést-místnost, přesunout-se, vytřít-místnost).
  2. Problémy:
    • Problém 1: Úklid jedné místnosti.
      • Popište počáteční stav (místnost je špinavá, úklidový pracovník je v místnosti, má k dispozici prachovku, mop je ve vedlejší místnosti, která už je čistá).
      • Popište cílový stav (místnost je čistá).
    • Problém 2: Úklid několika místností.
      • Popište počáteční stav (např. několik místností je špinavých, úklidový pracovník je v jedné z místností, má k dispozici prachovku a mop).
      • Popište cílový stav (např. všechny místnosti jsou čisté).
    • Problém 3: Úklid s rozdělením práce.
      • Popište počáteční stav (např. několik místností je špinavých, úklid dělají dva pracovníci, jeden s prachovkou, druhý s mopem).
      • Popište cílový stav (např. všechny místnosti jsou čisté).
  1. Doménu a problémy vytvořte ve formátu PDDL.
  2. Nechte problémy vyřešit pomocí webového solveru.

Úloha 3: Obchod s dovozem na prodejnu

Vaše firma má několik prodejen a jeden centrální sklad. Zboží může být buď v prodejně či ve skladu. Dopravu mezi skladem a vybranými prodejnami zajišťuje interní dopravce (spojení sklad-prodejna či prodejna-prodejna), který má na každém spoji pouze omezenou kapacitu. Zajímá nás, zda je možné zboží převézt.

  1. Navrhněte doménu v jazyce PDDL
  2. Máme centrální sklad a prodejny A, B, C, D a E.
    • Spoje mezi skladem a prodejnami:
      • Sklad ↔ Prodejna A: kapacita 15 přepravek
      • Sklad ↔ Prodejna B: kapacita 20 přepravek
      • Sklad ↔ Prodejna C: kapacita 12 přepravek
      • Sklad ↔ Prodejna D: kapacita 10 přepravek
      • Sklad ↔ Prodejna E: kapacita 18 přepravek
    • Spoje mezi prodejnami:
      • Prodejna A ↔ Prodejna B: kapacita 10 přepravek
      • Prodejna B ↔ Prodejna C: kapacita 15 přepravek
      • Prodejna C ↔ Prodejna D: kapacita 12 přepravek
      • Prodejna D ↔ Prodejna E: kapacita 10 přepravek
      • Prodejna A ↔ Prodejna C: kapacita 11 přepravek
      • Prodejna B ↔ Prodejna D: kapacita 13 přepravek
      • Prodejna C ↔ Prodejna E: kapacita 14 přepravek
    • Transportované výrobky a jejich velikost (v přepravkách):
      • Výrobek 1: 20 přepravek ze skladu do prodejny B
      • Výrobek 2: 14 přepravek ze skladu do prodejny B (všimněte si, že si zde nadkapacitní přeprava vynutí alternativní cestu)
      • Výrobek 3: 10 přepravek z prodejny C do prodejny E
      • Výrobek 4: 11 přepravek ze skladu do prodejny A
      • Výrobek 5: 15 přepravek ze skladu do prodejny A

Úlohu nechte vyřešit pomocí webového solveru.

Úloha 4: Jde to i bez skladu?

Prozkoumáváte možnost značné redukce vyrovnávací skladové kapacity vaší firmy. Ta má několik výrobních linek, kde dochází ke složení výrobků z dílů. Každá linka vyrábí jeden výrobek a potřebuje k němu přesně dané komponenty. Každá z komponent má jednoho či více dodavatelů. Někteří dodavatelé mají certifikaci rychlého přizpůsobení poptávce, kdy jsou schopni rychle nahradit výpadek jiného dodavatele. Tito dodavatelé jsou však zpravidla dražší. Chceme vědět, zda jsme schopni sestavit zásobování výrobní linky pouze z levnějších dodavatelů bez certifikace a zároveň pokrýt všechny komponenty linek alespoň jedním náhradním dodavatelem s certifikací.

  1. Navrhněte doménu v jazyce PDDL
  2. Vytvořte tři ukázkové úlohy, využívající danou doménu. Úlohy nechte vyřešit pomocí webového solveru.
  3. Některé výrobní linky musí běžet za každou cenu. Upravte úlohu, aby u označených linek vyžadovala alespoň dva různé certifikované dodavatele.

Úloha 5: Evakuace osob

Popis

Vaším úkolem je naplánovat evakuaci osob z různých místností budovy do bezpečného východu. Budova má několik místností a chodeb, které jsou propojené. Každá osoba se nachází v jiné místnosti a musí být evakuována do východu.

  1. Navrhněte doménu v jazyce PDDL
  2. Navrhněte úlohu v této doméně, s následujícími specifikacemi:
    • Objekty
      • Osoby: osoba1, osoba2, osoba3, osoba4
      • Místnosti: mistnost1, mistnost2, mistnost3, mistnost4
      • Chodby: chodba1, chodba2
      • Východ: vychod
    • Počáteční stav
      • osoba1 je v mistnost1
      • osoba2 je v mistnost2
      • osoba3 je v mistnost3
      • osoba4 je v mistnost4
      • mistnost1 je připojena k chodba1
      • mistnost2 je připojena k chodba1
      • mistnost3 je připojena k chodba2
      • mistnost4 je připojena k chodba2
      • chodba1 je připojena k chodba2
      • chodba2 je připojena k vychod
    • Cíl
      • osoba1, osoba2, osoba3 a osoba4 jsou ve vychod