Robotika a multi-agentní systémy
Úloha 1: Vlastnosti robotů
Zodpovězte následující otázky pro každého z těchto robotů – Nao, Pepper, Ozobot, MBot Ranger a YuMi ABB IRB14000/0.5:
- Jaké mají tito roboti senzory a jaké efektory?
- Které z těchto senzorů jsou pasivní a které aktivní?
- Mají roboti nějaké proprioceptivní senzory?
- Které senzory robotů jsou exteroceptivní?
- Jaké je zorné pole a dosah senzorů?
- Kolik mají tito roboti stupňů volnosti?
Úloha 2: Dopředná kinematika robotického ramene
- Robotické rameno má jeden kloub, který se může otáčet kolem osy Z. Kloub je umístěn v bodě (0, 0, 0) a rameno má délku 400 mm. Určete polohu koncového efektoru, pokud je kloub otočen o 45°.
- Robotické rameno má tři klouby. První kloub se otáčí kolem osy Z, druhý kloub se otáčí kolem osy Y a třetí kloub se otáčí kolem osy X. Délky jednotlivých segmentů jsou 100, 400 a 300 mm. Určete polohu koncového efektoru, pokud jsou klouby otočeny o 45°, 30° a 60°.
Úloha 3: Převod úlohy tvorby rozvrhu do SAT
Máme pět předmětů (Matematika, Fyzika, Chemie, Biologie, Informatika) a tři časové sloty (Slot 1, Slot 2, Slot 3). Každý předmět musí být naplánován do jednoho z těchto časových slotů, přičemž některé předměty mohou být ve stejném časovém slotu, ale v různých místnostech (máme k dispozici místnosti A a B). Někteří studenti mají zapsané více předmětů, takže žádné dva předměty, které mají společné studenty, nesmí být naplánovány ve stejném časovém slotu a místnosti. Abychom zbytečně nenavyšovali náklady na výuku, každý předmět bychom rádi viděli v rozvrhu pouze jednou (počty přihlášených studentů zde nevyžadují více paralelek).
Studenti s více předměty:
- Student A má zapsané Matematiku a Fyziku.
- Student B má zapsanou Fyziku a Chemii.
- Student C má zapsanou Biologii a Informatiku.
- Student D má zapsanou Matematiku a Chemii.
- Vytvořte proměnné pro všechny kombinace slotů a místností – např.
xM1A
je Booleovská proměnná, kdetrue
indikuje, že Matematika je přiřazena do časového Slotu 1, místnosti A. - Sepište omezení
- Každý předmět musí být rozvržen: např. pro Matematiku
(xM1A ∨ xM1B ∨ xM2A ∨ xM2B ∨ xM3A ∨ xM3B)
- V jednom čase může v jedné místnosti probíhat max. jeden předmět – např. pro Slot 1 a místnost A bude tato podmínka
(¬xM1A ∨ ¬xF1A), (¬xM1A ∨ ¬xC1A), (¬xM1A ∨ ¬xB1A), (¬xM1A ∨ ¬xI1A), (¬xF1A ∨ ¬xC1A), (¬xF1A ∨ ¬xB1A), …
- Zamezení kolize v rozvrhu pro studenty – např. omezení na základě požadavků studenta A se odvodí následovně:
- Rozmísti předměty Matematika a Fyzika do místností a slotů tak, že alespoň jedna dvojice Matematiky a Fyziky není v jednom časovém slotu.
- Toto se nám díky požadavku max. jednoho předmětu v rozvrhu redukuje na: Rozmísti předměty Matematika a Fyzika do místností a slotů tak, že tyto dva předměty nejsou v jednom časovém slotu.
- Jednodušší podmínku pak zapíšeme jako:
(¬xM1A ∨ ¬xF1B), (¬xM1B ∨ ¬xF1A), (¬xM2A ∨ ¬xF2B), (¬xM2B ∨ ¬xF2A), (¬xM3A ∨ ¬xF3B), (¬xM3B ∨ ¬xF3A)
- Každý předmět musí být v rozrhu maximálně jednou – např. pro Matematiku
(¬xM1A ∨ ¬xM1B), (¬xM1A ∨ ¬xM2A), (¬xM1A ∨ ¬xM2B), (¬xM1A ∨ ¬xM3A), (¬xM1A ∨ ¬xM3B), (¬xM1B ∨ ¬xM2A), …
- Každý předmět musí být rozvržen: např. pro Matematiku
- Nechte problém vyřešit libovolným SAT řešičem.
Úloha 4: Převod úlohy barevnosti grafu do SAT
Máme neorientovaný graf G = (V, E), kde V je množina vrcholů a E je množina hran. Cílem je obarvit vrcholy grafu tak, aby žádné dva sousední vrcholy neměly stejnou barvu, a použít přitom nejvýše k barev.
Nechť má graf G 4 vrcholy V = {1, 2, 3, 4} a 5 hran E = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)}. Počet barev k = 3. Označme je třeba R, G, B.
- Vytvořte proměnné pro všechny kombinace uzlů a barev – např.
x1R
je Booleovská proměnná, kdetrue
indikuje, že vrchol 1 je obarven barvou R. - Sepište omezení
- Každý vrchol musí být obarven právě jednou barvou. Toto se rozdělí na dvě části
- Každý vrchol musí být obarven alespoň jednou barvou
- Každý vrchol musí být obarven max. jednou barvou
- Žádné dva sousední vrcholy nesmí mít stejnou barvu
- Každý vrchol musí být obarven právě jednou barvou. Toto se rozdělí na dvě části
- Nechte problém vyřešit libovolným SAT řešičem.
Úloha 5: Převod úlohy do CSP
Popis problému
Máme pět zdravotních sester (Anna, Barbora, Cecilie, Dana, Eva) a tři směny (Ranní, Odpolední, Noční). Každá směna musí být pokryta dvěma sestrami a každá sestra může pracovat maximálně dvě směny za den. Navíc, každá sestra má omezení, kdy může pracovat.
Proměnné
S_1
: Sestry pro Ranní směnuS_2
: Sestry pro Odpolední směnuS_3
: Sestry pro Noční směnu
Domény
D(S_1) = {(Anna, Barbora), (Anna, Cecilie), (Barbora, Cecilie), (Dana, Eva)}
D(S_2) = {(Anna, Dana), (Barbora, Eva), (Cecilie, Dana), (Eva, Anna)}
D(S_3) = {(Barbora, Cecilie), (Dana, Eva), (Anna, Eva), (Cecilie, Dana)}
Omezení
- Anna nemůže pracovat na Noční směně.
- Barbora může pracovat pouze na Ranní nebo Noční směně.
- Cecilie nemůže pracovat na Ranní směně.
- Dana může pracovat maximálně jednu směnu za den.
- Eva může pracovat na jakékoli směně, ale ne dvě směny po sobě.
- Zapište omezení ve formátu CSP
- Vyřešte problém pomocí libovolného CSP solveru (např. Choco-solver)