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

Robotika a multi-agentní systémy

Zpět na výběr úloh

Ú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:

  1. Jaké mají tito roboti senzory a jaké efektory?
  2. Které z těchto senzorů jsou pasivní a které aktivní?
  3. Mají roboti nějaké proprioceptivní senzory?
  4. Které senzory robotů jsou exteroceptivní?
  5. Jaké je zorné pole a dosah senzorů?
  6. Kolik mají tito roboti stupňů volnosti?

Úloha 2: Dopředná kinematika robotického ramene

  1. 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°.
  2. 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.
  1. Vytvořte proměnné pro všechny kombinace slotů a místností – např. xM1A je Booleovská proměnná, kde true indikuje, že Matematika je přiřazena do časového Slotu 1, místnosti A.
  2. 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), …​
  3. 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.

  1. Vytvořte proměnné pro všechny kombinace uzlů a barev – např. x1R je Booleovská proměnná, kde true indikuje, že vrchol 1 je obarven barvou R.
  2. 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
  3. 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ěnu
  • S_2: Sestry pro Odpolední směnu
  • S_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í

  1. Anna nemůže pracovat na Noční směně.
  2. Barbora může pracovat pouze na Ranní nebo Noční směně.
  3. Cecilie nemůže pracovat na Ranní směně.
  4. Dana může pracovat maximálně jednu směnu za den.
  5. Eva může pracovat na jakékoli směně, ale ne dvě směny po sobě.
  1. Zapište omezení ve formátu CSP
  2. Vyřešte problém pomocí libovolného CSP solveru (např. Choco-solver)