Cvičenie 2

Riešenie tejto úlohy odvzajte v moodli do 9.10.2014 13:09:59.

Naprogramujte (všeobecný) "plánovač", ktorý načíta plánovací problém v nižšie špecifikovanom jazyku a vypíše jeden možný plán.

BONUS 1 (2b) Zapíšte v tomto jazyku problém vlka, kozy a kapusty a vyriešte ho pomocou vášho plánovača (pozn.: neviete vyjadriť, že sú niektoré stavy zakázané, ale to viete vyriešiť skomplikovaním predpokladov a vďaka tomu, že akcie, ktoré by nemali efekt budú ignorované).

Pre jednoduchosť predpokladajte, že vstupný problém má riešenie (jediná rozumne implementovateľná detekcia, či má riešenie, je obmedziť počet akcií, ktoré budeme skúšať. Po koľkých akciách určite nemá zmysel skúšať ďalej?)

Váš program načíta zo štandardného vstupu alebo zo súboru zadaného na command line plánovací problém (doménu, t.j. popis akcií; počiatočný stav a podmienku na cieľový stav) vo formáte uvedenom nižšie. Výstupom bude postupnosť akcií.

Vstupný formát: ACTIONje meno akcie, FLUENT, F1, F2,... PRE1, PRE2,... atď sú fluenty (reťazec neobsahujúci whitespace, začínajúci písmenom) alebo negované fluenty (znak "-" a reťazec ako pri fluente)

action ACTION : PRE1 PRE2 PRE3 ...  ? EFF1 EFF2 EFF3 ;
...
initial F1 F2 F3 .. Fn ;
goal F1 F2 ... ;

Najprv je viacre príkazov action, ktoré definujú efekt akcie za daných podmienok (može byť viacero takých príkazov s (možno) rôznoymi predpokladmi pre jednu akciu). PRE1... sú predpoklady, EFF1... sú efekty akcie (čo má platiť po akcii). Môžete predpokladať, že efekty akcií sú konzistentné.

Potom nasleduje jeden príkaz initial a jeden príkaz goal. Príkaz initial hovorí úplný, konzistentný stav (teda pre každý fluent uvádza jeho meno alebo negáciu). Považujte vstup za chybný, ak sa v popise akcii objaví fluent, ktorý sa nenachádza v príkaze initial.

Príkaz goal definuje podmienku pre cieľová stavy: musia v nich platiť fluenty (alebo negácie) vymenovaná v tomto príkaze.

Okolo znakov :, ? a pred znakom ; bude vždy (aspoň jedna) medzera.

Príklad:

action load : ? loaded ;
action shoot : loaded ? -alive ;
initial -loaded alive ;
goal -alive ;

Výstupný formát: Zoznam akcií, vždy jeden názov akcie na jednom riadku.

Príklad:

load
shoot

Niekoľko poznámok, ktoré by mohli pomôct:

Kostra riešenia by mala byť rovnaká ako v minulom cviku, akurát treba načítať vstup, zmeniť reprezentáciu akcií a stavov a zmeniť funkciu na vykonávacie akcie. Tiež nepotrebujeme teraz zisťovať, či je možné akciu vykonať a je dobré naozaj pridávať akciu (s výsledným stavom) do fronty iba ak má nejaký efekt (zmení stav).

Najjednoduchší spôsob reprezentácie stavu je mapa reťazec -> bool. Trochu efektívnejšie je hneď po/pri načítaní priradiť fluentom a akciám čísla, takže namiesto mapy stačí pole (resp std::vector ;). Ak je predpoklad, že väčšinu času bude len malá podmnožina fluentov pravdivá, môže byť efektívnejšia množina.

Popis domény (všetkých akcií) je tiež dobré držať v mape z akcí na pole (vektor) popisov jednotlivých efektov akcie (príkaz action zo vstupu)

V C++ používanie const & na správnych miestach vie zrýchliť program (hovorí kompilátoru, že nemusí kopírovať niektorú štruktúru, aj keď často šikovný kompilator so zapnutými optimalizáciami zistí, že sa tá štrukt. nemení a neskopíruje ju aj tak.