Zadání úlohy "Pac-Man"

Zadání soutěžní úlohy "Pac-Man"

Zadání úlohy - Pac-Man

Cílem úlohy je sestavit a naprogramovat robot (Pac-Man-a) tak, aby v časovém limitu 90s samostatně bez jakékoliv další pomoci (ovládání robota pomocí hlasu, bluetooth či jiných komunikačních kanálů není dovoleno) projel co největší část bludiště. V bludišti mohou být pohybující se roboti, kteří reprezentují duchy omezující volný pohyb soutěžního robota. O vítězství rozhoduje počet získaných bodů. Body robot získává průjezdem jednotlivými poli bludiště a odpovídají tak velikosti projeté plochy.

Vybavení pro řešení úlohy

Každý tým může použít při řešení soutěžní úlohy pouze díly ze stanovených souprav a dílů. Jsou možné následující varianty sestav souprav a dílů:

  • Základní souprava LEGO® MINDSTORMS® Education 45544 EV3, souprava doplňkových dílů 45560 EV3 a síťový adaptér (8887). Tuto sestavu doporučujeme.

nebo

  • Základní souprava LEGO® MINDSTORMS® Education (9797), souprava technických dílů (9648 nebo 9695) – doplňkové pasivní díly, síťový adaptéru (9833 nebo 8887) a jednoosý gyroskopický senzor (1044 NXT Gyroskop).

Každému týmu bude zapůjčen technický díl 3703 s vlisovanými třemi magnety (viz obr. 3). Tento díl slouží ke zjištění průjezdu robota příslušným polem bludiště (viz níže).

 

Konstrukce robota

Ke konstrukci robota lze využít pouze dílů z výše uvedených sestav. Za díly z dané sestavy lze považovat pouze takové díly, které jsou uvedeny v seznamu dílů obsažených v příslušné soupravě (vyobrazeny na kartách příslušných setů). Použití vázacích pásků a obalů, s nimiž jsou soupravy dodávány, není přípustné. Díly stavebnice mohou držet pohromadě pouze pomocí standardních spojovacích prvků LEGO.

Není povoleno používat kluzný podvozek. Za podvozek či jeho část je považována jakákoliv součást robota, která je při pohybu robota po rovině ve styku s pojezdovou plochou (i dočasně) a přenáší na pojezdovou plochu část váhy robota. Kluzný podvozek je takový, jehož libovolná část se po pojezdové ploše neodvaluje, ale klouže. Za porušení pravidel nebude považováno, pokud není kluzný podvozek součástí návrhu robota a vznikl pouze poškozením konstrukce v dané jízdě (např. nárazem do překážky). Porušením pravidla také není dotyk pevné části konstrukce s pojezdovou plochou, pokud se tak stává pouze nahodile (např. při prudkém zastavení) a jen krátce (méně než 1s).

UPOZORNĚNÍ: Použití lepidel, šroubů a jiných spojovacích materiálů není povoleno.

 

Programování robota

V rámci řešených úkolů a soutěže je povoleno využít libovolného programovacího jazyka k naprogramování EV3 nebo NXT kostky (řídicí jednotka LEGO® MINDSTORMS®). Řídicí jednotka při odevzdání (vrácení zapůjčené) musí obsahovat standardní firmware LEGO® MINDSTORMS®. Při programování EV3 nebo NXT kostky a testování robota lze využít k napájení akumulátor, vlastní baterie nebo síťový adaptér. Při vlastní soutěži je možné použít pouze akumulátor nebo baterie!

Pravidla soutěže předpokládají samostatnou práci účastníků (žáků/ studentů). Je dovoleno užívat cizí knihovny a části kódu, které implementují zejména standardní algoritmy. Takové knihovny a části kódu však musí být veřejně dostupné (např. na internetu) a to již před soutěží (alespoň měsíc). Je možné také využít rady třetí strany, ale výsledný program musí být prací členů týmu. Není dovoleno používat programy kolegů (dalších účastníků), pokud se nejedná o případ veřejně dostupného kódu. Členové týmu jsou povinni v případě pochybnosti autorství obhájit tak, že vysvětlí funkčnost dotčených částí programu.

 

Soutěžní plocha

Soutěžní plocha (hřiště) je vodorovná deska. Celkové rozměry soutěžní plochy (pojezdové plochy bludiště) jsou 2560 mm (délka) x 1720 mm (šířka). Podkladem soutěžní plochy je šedá laminátová deska ohraněná bočními lištami (laminátová deska), které tvoří nad pojezdovou plochou stěny o výšce 75mm. Soutěžní plocha (bludiště) je pomyslně rozdělena na 9 x 6 (celkem 54 čtverců o velikosti 280mm x 280mm). V každém čtverci může být umístěna překážka nebo je pojezdovou plochou bludiště. Příklad možného uspořádání bludiště je na obr. 1 a fotografie skutečného provedení pak na obr. 2. Konfigurace bludiště se může mezi jednotlivými jízdami změnit.

Obr. 1 Ilustrační obrázek uspořádání hracího hřiště

Obr. 2 Fotografie příkladu uspořádání hracího hřiště

Každý čtverec, který je pojezdovou plochou, je osazen elektronickým modulem kruhového tvaru o průměru 50mm. Modul je umístěn do laminátové desky tak, že nevyčnívá nad pojezdovou plochu. Vlastní elektronický modul je osazen řídicí elektronikou, LED indikací a Hallovými senzory. Hallovy senzory slouží k indikaci průjezdu robota. Průjezd je indikován na základě přítomnosti magnetu nad senzorem. Při průjezdu robota nad elektronickým modulem dojde prostřednictvím magnetu k aktivaci senzorů, zhasnutí LED indikace a robotu je připočten jeden bod.

Každý robot proto musí být vybaven magnetem/magnety. Na robotu bude umístěn technický díl 3703 (viz obr. 3), do kterého budou vlisovány 3 magnety. Technický díl by měl být umístěn na robotu tak, aby byl maximálně ve výšce 10mm nad pojezdovou plochou. Doporučujeme umístit technický díl tak, aby byl symetricky od středu osy robota.

Obr 3: Technický díl 3703 s vlisovanými magnety

Překážky tvoří čtvercové moduly o rozměrech 280 x 280 mm (+-2mm), které jsou slepeny ze třech ohraněných laminátových desek o tloušťce 25mm, takže celková výška je 75mm (viz obr. 4 – pohled ze shora a obr. 5 – pohled zespodu). Překážky jsou upraveny tak, aby se při běžném kontaktu s robotem nepohybovaly.

Obr. 4 Čtvercový modul bludiště o rozměrech 280mm x 280mm – pohled seshora

Obr. 5 Čtvercový modul bludiště o rozměrech 280mm x 280mm – pohled zespodu

 

Pravidla pro průjezd bludištěm

Úkolem robota v každé soutěžní jízdě je projet co největší část bludiště v daném časovém intervalu. První průjezd robota každým čtvercem osazeným elektronickým modulem, na něž je bludiště rozděleno, bude registrován a robotu bude připočten bod. Cílem je nasbírat co největší počet bodů. Bod bude robotu připočten jen v případě, že robot projede daný čtverec a bude aktivován magnetický senzor elektronického modulu. Tato skutečnost bude následně signalizována zhasnutím indikátoru daného čtverce.

Před začátkem každé soutěžní jízdy mají hráči na základě požádání k dispozici přípravný čas pro kalibraci senzorů či výběr programu z řídicí jednotky (NXT kostka). Přípravný čas je přitom limitován maximální délkou jedné minuty. Během tohoto času není dovoleno nahrávat řídicí programy do řídicí jednotky (NXT kostka).

Po přípravě soutěžící umístí svého robota do pozice označené START (viz obr. 6, obr. 7 a obr. 8).

Obr. 6 Neměnný startovní box

Obr. 7 Neměnný startovní box

Obr. 8 Neměnný startovní box

Robota soutěžící spustí stisknutím tlačítka (na řídicí jednotce NXT nebo pomocí dotykového senzoru) na pokyn hlavního rozhodčího (vyučujícího) soutěže. Zároveň bude spuštěna časomíra. Robot se po zahájení soutěžní jízdy musí pohybovat samostatně, ovládání robota pomocí hlasu, bluetooth či jiných komunikačních kanálů není dovoleno. V případě porušení pravidel je tým okamžitě diskvalifikován v dané soutěžní jízdě

Po spuštění časomíry má robot 90 sekund na nasbírání co největšího počtu bodů. Robotu není dovoleno překonávat jakýmkoliv způsobem překážky umístěné uvnitř bludiště a zkracovat si tak cestu, nebo se dostávat do jiných částí bludiště.

Robot nesmí mít v paměti zadán explicitně plán bludiště.

Soutěžní jízda bude ukončena dříve pokud:

  • Robot není schopen bez pomoci pokračovat
  • Robot opustí hrací plochu
  • Soutěžící se dotkne robota nebo ho odstraní z hrací plochy
  • Poruší pravidlo o překonávání překážek

Pokud je soutěžní jízda ukončena dříve, než uplyne časový limit, robot je odstraněn z hrací plochy a jsou mu přitom započteny doposud získané body.

Robot má celkem 3 životy. Pokud se v průběhu časového limitu dotkne nebo narazí do ducha v bludišti (o dotknutí nebo nárazu rozhoduje rozhodčí (vyučující)), ztrácí robot jeden život a soutěžící musí umístit robota do startovního boxu a robota opětovně spustit. Při spuštění je možné vybrat jiný program pro procházení bludiště. Po ztrátě všech tří životů soutěžící odstraní robota z hrací plochy a jsou mu přitom započteny doposud získané body.

 

Duchové v bludišti

Duchové jsou roboti, kteří mohou být barevně různorodí. Rozměr ducha (cca 200 x 200 x 240mm). Duchové jsou tak vždy vyšší než překážky v bludišti. Té to skutečnosti mohou soutěžící roboti využít k jejich rozpoznání a lokalizaci. Všichni duchové budou mít stejné rozměry. V bludišti může, ale nemusí, být umístěn jeden, nebo více duchů, kteří budou robotu ztěžovat pohyb. Duch nebo duchové se budou pohybovat po předem dané trajektorii s danou rychlostí a soutěžící robot by měl být schopen ducha detekovat a změnit odpovídajícím způsobem svůj pohyb. Na obrázcích 9 až 22 jsou fotografie možného provedení ducha. Maximální rychlost duchů je 7,5cm/s (odpovídá nastavené rychlosti 20 v grafickém programu).

Obr. 9 fotografie možného provedení ducha

Obr. 10 fotografie možného provedení ducha

Obr. 11 fotografie možného provedení ducha

Obr. 12 fotografie možného provedení ducha

Obr. 13 fotografie možného provedení ducha

Obr. 14 fotografie možného provedení ducha

Obr. 15 fotografie možného provedení ducha

Obr. 16 fotografie možného provedení ducha

Obr. 17 fotografie možného provedení ducha

Obr. 18 fotografie možného provedení ducha

Obr. 19 fotografie možného provedení ducha

Obr. 20 fotografie možného provedení ducha

Obr. 21 fotografie možného provedení ducha

Obr. 22 fotografie možného provedení ducha

Duchové se mohou pohybovat v bludišti následovně:
 

  • Duch bude stát na místě (obdoba překážky) - viz videa 01, 02 a03
     
  • Duch se bude pohybovat konstantní rychlostí kolem dokola překážky buď po směru hodinových ručiček, nebo proti směru hodinových ručiček.
     
  • Duch se bude pohybovat v krajní levé (levý sloupec) nebo v krajní pravé (pravý sloupec) části bludiště opakovaně od shora dolů a nazpátek s tím, že pokud bude v tomto sloupci použita překážka, bude se duch pohybovat opakovaně od shora dolů k překážce a nazpátek nebo opakovaně  od překážky dolů a nazpátek.
  • Duch se bude pohybovat v krajní horní (horní řádek) nebo v krajní dolní (dolní řádek) části bludiště opakovaně zprava doleva a nazpátek s tím, že pokud bude v tomto řádku použita překážka, bude se duch pohybovat opakovaně zprava doleva k překážce a nazpátek nebo opakovaně od překážky doleva a nazpátek.

V jedné jízdě může být použito více duchů při splnění výše uvedených podmínek. V jízdě nemusí být také duch použit vůbec.

Další informace najdete v Otázkách a odpovědích.

Video 01 - Řešení úlohy Pac-Man se stojícím duchem

Video 02 - Řešení úlohy Pac-Man se stojícím duchem

Video 03 - Řešení úlohy Pac-Man se stojícím duchem

Video 04 - Řešení úlohy Pac-Man bez duchů

Video 05 - Řešení úlohy Pac-Man bez duchů

Video 06 - Řešení úlohy Pac-Man bez duchů

 

Organizace soutěže

1. kolo soutěže

V prvním kole bude mít každý ze soutěžících týmů postupně 2 pokusy (absolvuje dva souboje) na hracím hřišti s cílem získat co největší počet bodů. Mezi oběma pokusy může dojít ke změně konfigurace bludiště.

Pořadí soubojů:

  • Tým č.1 a Tým č.2
  • Tým č.3 a Tým č.4
  • Tým č.5 a Tým č.6
  • Tým č.7 a Tým č.8
  • Tým č.9 a Tým č.10
  • Tým č.11 a Tým č.12
  • Tým č.13 a Tým č.14
  • Tým č.15 a Tým č.16
  • Tým č.17 a Tým č.18
  • Tým č.19 a Tým č.20
  • Tým č.21 a Tým č.22
  • Tým č.23 a Tým č.24
  • Tým č.25 a Tým č.26
  • Tým č.27 a Tým č.28
  • Tým č.29 a Tým č.30
  • Tým č.31 a Tým č.32
  • atd.

Stanovení pořadí týmů v prvním kole:

 Na základě součtu bodů získaných v obou pokusech (soubojích) daným robotem je určeno pořadí po prvním kole. Stanovovat pořadí se bude takto:

  1. Celkovým počtem bodů (součet obou pokusů (soubojů)).
  2. Při rovnosti bodů dvou nebo více týmů rozhoduje větší počet bodů získaných v jednotlivých pokusech (soubojích).
  3. Hod hrací kostkou (hozené vyšší číslo vyhrává, v případě rovnosti se hází opakovaně do rozhodnutí).

 

2. kolo soutěže

Do 2. kola soutěže mohou postoupit týmy, které v 1. kole soutěže v součtu získaly alespoň 20 bodů. Nejvýše však postupuje 24 týmů podle pořadí. Pokud bude postupujících týmů méně než 17, postupují všechny týmy přímo do 3. kola soutěže. V opačném případě postupuje nejlepších 8 týmů podle pořadí v 1. kole soutěže přímo do 3. kola soutěže a týmy na 9. až 24. místě se utkají o postup do 3. kola soutěže. 2. kolo soutěže bude organizováno jako vzájemné utkání na jednu jízdu, z níž vždy vítěz postoupí do 3. kola soutěže. Vítězem utkání se stává tým, který získá v jízdě více bodů. Jestliže oba týmy získají maximální počet bodů, zvítězí robot, který projel (získal maximální počet bodů) bludiště prokazatelně rychleji. Pokud nebude možné o vítězi rozhodnout, bude následovat druhá jízda a pokud ani ta nerozhodne o vítězi, bude následovat hod hrací kostkou (vyšší číslo vyhrává, v případě rovnosti se hází opakovaně do rozhodnutí).

Ve 2. kole soutěže se utkají týmy umístěné v pořadí po 1. kole následovně:

 

9. tým - 24. tým (vítěz bude nasazen ve 3. kole soutěže jako 9. tým pořadí)

10. tým - 23. tým (vítěz bude nasazen ve 3. kole soutěže jako 10. tým pořadí)

11. tým - 22. tým (vítěz bude nasazen ve 3. kole soutěže jako 11. tým pořadí)

12. tým - 21. tým (vítěz bude nasazen ve 3. kole soutěže jako 12. tým pořadí)

13. tým - 20. tým (vítěz bude nasazen ve 3. kole soutěže jako 13. tým pořadí)

14. tým - 19. tým (vítěz bude nasazen ve 3. kole soutěže jako 14. tým pořadí)

15. tým - 18. tým (vítěz bude nasazen ve 3. kole soutěže jako 15. tým pořadí)

16. tým - 17. tým (vítěz bude nasazen ve 3. kole soutěže jako 16. tým pořadí)

 

 3. kolo soutěže

 3. kolo soutěže bude probíhat ve formě vyřazovacího systému na dvě porážky. Vyřazovací systém na dvě porážky je méně obvyklá modifikace vyřazovacího systému, rozpisu utkání turnajů některých her a sportů (tzv. oboustranný pavouk). Turnajem nepostupují jen vítězové, ale i účastníci, kteří prohráli zatím jen jednou. Graf rozpisu utkání se skládá jak z části pro vítěze jako ve vyřazovacím systému, tak i části pro účastníky, kteří již jednou prohráli.

 

Páry účastníků do turnaje vstupují podobně jako ve vyřazovacím systému, tedy obvykle losem nebo s pomocí nasazování tak, aby se dva „papírově“ nejsilnější mohli sejít jako neporažení až ke konci turnaje. Na začátku jsou všichni ve větvi vítězů. Ti, co vyhrají, postupují do druhého kola. Ti, kteří prohrají, přecházejí na začátek větve poražených.

 

Vítěz každého kola ve větvi vítězů se v následujícím kole setká s dalším jiným vítězem z této větve. Poražený z tohoto duelu přechází do větve poražených. Vítěz každého kola ve větvi poražených se v následujícím kole setká s některým poraženým z větve vítězů. Pro poražené ve větvi poražených turnaj končí, neboť prohráli již podruhé.

 

Na konci turnaje se vítěz větve vítězů utká v zápase o celkové vítězství s vítězem větve poražených. Pokud v tomto utkání vyhraje vítěz větve poražených, hraje se ještě jeden zápas mezi těmito dvěma účastníky. Tím je zaručeno, že vítěz turnaje jako jediný neokusí porážku více než jednou.

 

3. kolo soutěže bude organizováno jako vzájemné utkání dvou robotů v jedné jízdě. Vítězem utkání se stává tým, který získá v této jízdě více bodů. Pokud týmy dosáhnou maximálního počtu bodů, zvítězí tým, který dosáhl tohoto maximálního počtu bodů prokazatelně dříve. Jestliže oba týmy získají stejný počet bodů za stejný čas (nebudeme schopni rozhodnout prokazatelně, který tým byl rychlejší), bude následovat druhá jízda a pokud ani ta nerozhodne o vítězi, bude následovat hod hrací kostkou (vyšší číslo vyhrává, v případě rovnosti se hází opakovaně do rozhodnutí).

 

Obecná ustanovení

Pokud není uvedeno jinak, vede porušení kteréhokoliv z uvedených pravidel k diskvalifikaci robota v dané jízdě (prohra v dané jízdě). O dodržení pravidel a diskvalifikaci rozhoduje hlavní rozhodčí (Martin Hlinovský nebo jím pověřený zástupce) dohlížející na průběh soutěže. Jeho rozhodnutí je konečné.

Kterýkoliv člen týmu může podat protest proti výsledku v dané jízdě ihned po jejím skončení (maximálně však do 60s od jejího skončení). Na protesty podané po tomto časovém limitu nebude brán zřetel.

Organizátor soutěže má právo ověřit autorství programu v robotovi formou dotazů k jeho funkcionalitě. Pokud ani jeden člen týmu nebude schopný odpovědět na otázky týkající se funkce robota, bude tím zpochybněno autorství programu a bude to považováno za porušení pravidel soutěže. Účastníci na požádání musí umožnit organizátorům nahlédnout do kódu programu za účelem ověření, zda odpovídá pravidlům soutěže. V těchto případech porušení pravidel si organizátor vyhrazuje právo takový tým vyloučit ze soutěže, a to kdykoliv v průběhu soutěže až do chvíle vyhlášení celkových výsledků. Vyloučený tým pak bude v další části soutěže nahrazen týmem, který byl naposledy vyřazen vyloučeným týmem.

Žák/ student se může účastnit soutěže pouze jako člen jednoho týmu. Změna týmu, v němž se dotčený soutěže účastní, je možná pouze na základě souhlasu organizátora (hlavního rozhodčího, Martin Hlinovský čí pověřený zástupce). Změna týmu není možná, pokud se již žák/ student soutěže zúčastnil jako člen jiného týmu (robot tímto týmem připravený se dostavil ke startu v první jízdě).

 

Odkazy

Webová stránka, na které je možné stáhnout LEGO® MINDSTORMS® Education EV3 Software

Základní informace o LEGO Mindstorms: pdf

Metodika práce s NXT-G: pdf,ppt
Základní návod na programování pomocí NXT-G: pdf,ppt
Referenčná príručka 1 ku grafickému jazyku NXT-G
Referenčná príručka 2 ku grafickému jazyku NXT-G

Základní prezentace - Programování LEGO robotů pomocí NXC
Základní návod na programování pomocí NXC: pdf,ppt
NXT tutorial sk
Programovacia príručka k stavebnici LEGO NXT Mindstorm

Základní prezentace - Srovnání LEGO Mindstorms NXT vs. EV3
Základní prezentace - regulátory: pdf,ppt

Základní prezentace - Robotický seminář pro střední školy