Automatická sekačka/cs

Tato stránka je výsledkem práce na výzkumné zprávě pro předmět 4IT495 Simulace systémů, LS 2011/2012. AUTOMATICKÁ SEKAČKA; VÝZKUMNÁ ZPRÁVA; PŘEDMĚT: 4IT495 Simulace systémů; AUTOR: Ladislav Dyntar; TYP MODELU: Multiagentní; PROVEDENO V: NetLogo [1]

Definice problému

V dnešní moderní době je snahou valné většiny lidí a organizací ušetřit si co nejvíce práce a/nebo nákladů. Vlastnictví rozlehlého pozemku s sebou, kromě mnoha radostí, přináší i řadu povinností. Jednou z nich je údržba travnatého porostu.

Cílem tohoto modelu je simulovat pohyb automatické sekačky (či sekaček) po rozsáhlé travnaté ploše, na jejíž údržbě chce majitel ušetřit náklady, aniž by při tom musel jakkoliv omezovat využívání daného prostoru. Příkladem takového prostoru může být městský park či hotelová zahrada.

Každá automatická sekačka bude po nastartování automaticky jezdit po vyhrazeném prostoru a sekat trávu. Při své práci se bude vyhybat překážkám, a to jak statickým (stromy, zahradní domek) tak dynamickým (lidé a zvířata) - ty se budou po mapě náhodně pohybovat.

Aby to nebylo tak jednoduché, ne vždy je účinnost sekačky 100%. A tak se může stát, že bude nutné přejet přes určité místo i vícekrát, aby bylo posekáno dle představ majitele trávníku. Pokud však naopak sekačka opakovaně přejede přes daný kus trávy a ten bude již zcela posekaný, bude se daný kus trávy opotřebovávat - tráva se poškodí.

Cílem simulace bude pozorovat vliv jednotlivých algoritmů (a jejich nastavení) na dobu trvání sečení a s tím související růst nákladů. Dále budeme pozorovat a četnost poškození trávníku vlivem zvoleného algoritmu. Přitom předpokládáme, že cílem majitele pozemku je posekat zcela celý pozemek a dosáhnout přitom co nejnižšího poškození za co nejmenších nákladů (času).

 

Metoda

Pro řešení problému formou multiagentního modelu jsem se rozhodl z několika důvodů. V zadání jsem hned na začátku identifikoval několik agentů, jejichž základní vlastností je reaktivní chování - dokáží reagovat na danou situaci a na stav okolních agentů. Každý agent je však nezávislý na těch ostatních, má svůj vlastní cíl. Mým cílem bylo vytvořit i několik základních algoritmů pohybu sekačky, které by reagovaly nejen na již zmiňovaný stav okolních agentů, ale zahrnovaly v sobě i prvky vlastního (náhodného) rozhodování. Systém se tím pádem stal natolik komplexním, že bez návrhu multiagentního systému by bylo téměř nemožné jej pozorovat a analyzovat krok po kroku.

Možnost živé simulace jsem předem zavrhl, a to z několika důvodů. Prvním byl výběr vhodných prostor; druhým časové omezení a s ním související možnost simulovat celý model opakovaně, navíc pokaždé s jinými atributy; a posledním pak technologické omezení, jelikož nedisponuji technikou ani znalostmi vhodnými k sestavení mnou navrhované automatické sekačky (jen pro upřesnění dodávám, že se mi, k mému překvapení, při hledání podařilo najít několik výrobců, kteří se podobnými sekačkami již zabývají).

Rozhodl jsem se tedy využít programu NetLogo verze 5.0, se kterým jsem se seznámil na hodinách předmětu 4IT495 Simulace systémů, vyučovaném v rámci VŠE v Praze.

NetLogo, díky svému jednoduchému, avšak plně upravitelnému grafickému rozhraní umožňuje uživateli navrhovaný systém sledovat přímo za běhu. Je tedy možné ověřit si důsledky jednotlivých nastavení už v rámci samotné simulace a není nutné analyzovat průběh simulace až po jejím ukončení.

Zároveň je třeba zmínit, že problém sekačky v této práci představuje hledání vhodného algoritmu na prohledávání stavového prostoru. Tuto NP-úplnou optimalizační ulohu mnoho lidí zná spíše pod pojmem Problém Obchodního Cestujícího (Traveling Salesman Problem - TSP). Jedná se o velice komplikovaný algoritmus, prakticky neřešitelný optimálně v polynomiálním čase.

Detailní popis modelu

Popis prostředí

Simulované prostředí představuje čtverec o rozměrech 65x65 patches, složený z menších čtverců o rozměrech 1x1. Pro účely naší simulace předpokládáme, že jedna délka představuje 1 metr v reálném světě.

Simulovaný svět je ze všech stran uzavřený, představme si to jako plot okolo pozemku. Tato hranice není vidět.

Každý čtverec je po úvodní inicializaci tmavě zelený. Tato barva představuje vysoký travní porost, který má automatická sekačka za úkol zkrátit. Barva takové neposekané dlaždice je určena jako "green". Jakmile dojde k posekání vybraného čtverce, přičemž pravděpodobnost, že bude čtverec posekán je označena jako "pst-posekani-spravne" je jeho barva nastavena na "green + 1".

Pokud přes již posekaný čtverec, označený jako "green + 1", sekačka přejede opět, s pradvěpodobností "pst-posekani-spatne1" dojde k lehkému poničení trávy vlivem opětovného přejetí sekačky a takový čtverec je následně označen barvou "green + 2".

Pokud přes již posekaný čtverec, označený jako "green + 2", sekačka přejede opět, s pradvěpodobností "pst-posekani-spatne2" dojde k střednímu poničení trávy vlivem opětovného přejetí sekačky a takový čtverec je následně označen barvou "green + 3".

Pokud přes již posekaný čtverec, označený jako "green + 3", sekačka přejede opět, s pradvěpodobností "pst-posekani-spatne3" dojde k závažnému poničení trávy vlivem opětovného přejetí sekačky a takový čtverec je následně označen barvou "green + 4".

Pokud přes již posekaný čtverec, označený jako "green + 4", sekačka přejede opět, s pradvěpodobností "pst-posekani-zniceno" dojde k naprostému zničení trávy vlivem opětovného přejetí sekačky a takový čtverec je následně označen barvou "yellow".

Na ohraničeném pozemku se ještě nachází řada překážek. Na mapu jsou náhodně umístěny stromy, které zabírají přesně 1 čtverec. Jejich barva je nastavena jako "brown" a v grafickém rozhraní je možné určit si, kolik stromů chceme vygenerovat.

Další překážkou je zahradní domek, který je na mapu umístěn pevně a představuje objekt o rozměrech 2*4 dlaždice. Jeho barva je taktéž nastavena na "brown".

Agenti

Lidé

Jsou generováni v počtu stanoveném uživatelem v grafickém rozhraní. Jejich rychlost pohybu je stanovena náhodně s normálním rozložením se střední hodnotou 2 a směrodatnou odchylkou 0.2. Pro přehlednost byli všichni lidé označení červenou barvou "red". Jejich umístění na mapě je generováno náhodně.

Zvířata

Zvířata jsou také generována na základě vstupu uživatele z grafického rozhraní. Na mapě se zobrazují s ikonou psa. Jejich rychlost pohybu po pozemku je generována náhodně s normálním rozdělením se střední hodnotou 1 a směrodatnou odchylkou 0.2. Jejich barva byla nastavena na "blue", tedy modrou. Jejich umístění na mapě je generováno náhodně.

Sekačky

Dalším a pravděpodobně nejdůležitějším agentem jsou samotné sekačky. V grafickém rozhraní lze zvolit jejich konkrétní počet. Pro celou skupinu sekaček máme možnost zvolit, zda se na mapě vygeneruje náhodně, v levém dolním rohu či na středu pozemku. Rychlost sekaček byla zvolena jako 1. Sekačkám je, kromě atributu rychlost, přiřazen ještě atribut vyjadřující jejich algoritmus pohybu.

Chování agentů

V každém ticku modelu jsou postupně volány metody "move-lidi", "move-zvirata" a "move-sekacky". Lidé i zvířata se pohybují na základě stejného algoritmu - pokud mohou jít rovně vpřed (nejsou na kraji pozemku, před nimi není žádná překážka ani jiný agent) jdou o jim vlastní rychlost vpřed. Pokud narazí, změní směr o "random 360" stupňů a pokračují opět rovně, dokud znovu nenarazí.

Zajímavé to začíná být až u pohybu samotné sekačky. Té v první fázi v grafickém rozhraní přidělíme jeden z navržených algoritmů, případně můžeme sáhnout po možnosti přidělit každému typu sekačky jeden z náhodných algoritmů ze seznamu algoritmů.

Sekaček se týkají i další grafické prvky v rozhraní - slider "uhel-otoceni" nám umožňuje zvolit úhel, o který se sekačka bude otáčet v případě, že narazí (implementace se liší v závislosti na zvoleném algoritmu).

Input box "zmena-polomeru-rozdeleni" je využit u kruhových algoritmů. Čím vyšší hodnota, tím rychleji se zvětšuje poloměr opisovaného kruhu sekačky.

Sekačky, stejně jako lidé i zvířata, v případě, že mohou pokračovat bez omezení ve svém směru (ať už je přímý či kruhový), v něm pokračují až do té doby, dokud jim to okolí umožňuje. Jakmile se před nimi ocitne překážka, provedou kroky definované ve svém algoritmu a pokračují dále v klasickém pohybu.

Sekačky při svém pohybu navíc ovlivňují patches, přes které zrovna přejíždí - seká na nich imaginární trávu. Pravidla pro sekání trávy sekačkou byla popsána výše v sekci Popis prostředí.

Sekačka eviduje spotřebu benzínů/energie, na každý jeden tick spotřebuje jednu jednotku. Převod jednotek na reálné hodnoty je díky tomu možné uskutečnit až dodatečně s ohledem na to, bude-li uživatel modelu pracovat s cenou elektřiny, benzínu či jiných zdrojů.

Popis algoritmů sekačky

Aktuálně je v kódu naprogramováno 5 algoritmů, není však nejmenší problém přidat v budoucnu další v případě zájmu o rozvoj modelu.

Algoritmus 1: uhel-otoceni

Tento velice jednoduchý algoritmus nejprve kontroluje, zda může pokračovat v cestě (tím budeme i dále v textu rozumět situaci, kdy sekačce v cestě nestojí žádná překážka, lidé, zvířata či se nenachází na kraji pozemku). Pokud je vše v pořádku, jede dopředu o rychlost sekačky "speed". Pokud narazí, otočí se doleva o úhel "uhel-otoceni" stanovený v grafickém prostředí.

Algoritmus 2: random-uhel-otoceni

Tento algoritmus je pouhým rozšířením prvního algoritmu. V případě, že narazí, otočí se sekačka o náhodný úhel "random uhel-otoceni", přičemž náhodně vybírá na základě vstupu uživatele z grafického rozhraní.

Algoritmus 3: random-360

Tento algoritmus je pouhým rozšířením prvního algoritmu. V případě, že narazí, otočí se sekačka o náhodný úhel "random 360".

Algoritmus 4: kruh

Algoritmus nazvaný kruh představuje již komplikovanější řešení problému pohybu sekačky. Po úvodní kontrole na možnost pohybu vpřed se, pokud je pohyb umožněn, sekačka posune vpřed a mírně se natočí směrem vlevo. Toto se stále opakuje, takže sekačka by se bez zásahu pohybovala stále v kruhu. Proto s postupem času snižuju úhel, o jaký se sekačka otáčí vlevo, aby se poloměr kruhu postupně zvětšoval a sekačka tak mohla pokrýt co největší prostor.

Jakmile při svém pohybu sekačka narazí na překážku, otočí se doleva o "180 - random uhel-otoceni" stupňů, na chvíli přeruší kroužení a odjede od překážky. Po 25 krocích se opět vrátí ke kroužení, začíná však opět s maximálním úhlem, který byl implicitně zvolen 45 stupňů.

Algoritmus 5: kruh s random dojezdem

Tento algoritmus představuje mírné upravení předchozího algoritmu "kruh". Vychází z předpokladu, že na začátku je pro sekačku výhodné kroužit v kruzích, ale v pozdější fázi je lepší vyhledávat neposekaná políčka náhodně. Proto se po několika nárazech změní algoritmus sekačky na "lt 180 - random uhel-otoceni".

Algoritmus 6: dlazdice

Poslední algoritmus je nazvaný dlaždice. Jeho náplní je totiž vyhledávat zatím neposekané patche a upřednostňovat je před ostatními, aby bylo co nejvíce minimalizováno opotřebení již posekaných částí pozemku. Algoritmus tedy již posekané dlaždice bere jako svou překážku a snaží se jim vyhybat (pokud je to možné).

Po úvodní kontrole na možnosti pohybu vpřed, pakliže je pohyb umožněn, se sekačka podívá, zda-li je dlaždice před ní neposekaná. Pokud je, přejde na ni. Pokud není, podívá se o "uhel-otocky-kontroly" vlevo. Pokud zde najde neposekaný patch, otočí se a čeká na další "tick", aby mohla provést cestu vpřed. Pokud však ani po tomto otočení nenalezne vhodný patch, opakuje hledání v rozmezí 360 stupňů. Pokud ani jeden z okolních patchů sekačky není volný, uskuteční sekačka krok vpřed na již posekaný trávník a zde opakuje hledání o 360 stupňů. Jakmile by zde našla neposekanou část, přesune se na ni. Pokud ji nenajde, opět přejde na již posekané místo a toto opakuje stále dokola.

Spuštění simulace

Prvotní nastavení modelu provedeme stisknutím tlačítka "setup". To provede inicializace všech proměných, nastavení mapy, vykreslí sekačky, lidi a zvířata. Spuštění samotné simulace je možné provést stisknutím tlačítka "go". Simulace se sama ukončí v moment, kdy jsou všechna políčka na mapě posekána - takový stav je cílem simulace.

Další omezení a předpoklady

Pro účely naší simulace byly stanoveny následující pravděpodobností hodnoty, určující pravděpodobnost, že dojde k poškození trávníku vlivem opakovaného pohybu sekačky na jedné a té samé dlaždici: set pst-posekani-spravne 90 set pst-posekani-spatne1 4 set pst-posekani-spatne2 3 set pst-posekani-spatne3 2 set pst-posekani-zniceno 1

Jak je vidět, jsme poměrně přísní. V reálném světě by se všechny tyto hodnoty blížili spíše k jednomu procentu a méně, pro účely naší simulace však záměrně ponecháme tato kritéria, abychom mohli lépe pozorovat nízkou efektivitu jednotlivých algoritmů. Naopak pravděpodobnost, že sekačka poseče daný patch správně by v reálu mohla dosahovat spíše vyšších hodnot, pro naše účely budeme předpokládat, že se jedná o novou technologii, prozatím s nízkou efektivitou 90 %.

Počet stromů pro všechny naše simulace jsme stanovili na 8; kůlnu vykreslíme vždy. Startovní pozice pro všechny simulace byla uprostřed. Sekačku jsme na trávník vpustili vždy jen jednu protože nepředpokládáme, že by si vlastník zahrady kupoval sekačky dvě.

Proměnná "škody" používaná v tabulkách níže znázorňuje součet všech jakkoliv poškozených dlaždic s trávou (posekano-spatne1-3 + posekano-zniceno).

Je nutné dále upozornit na to, že v modelu abstrahujeme od prvků jako je vliv počasí, nutnost doplňovat pohonné hmoty, poruchovost sekaček a jiné.  

Výsledky

Simulovali jsme opakovaně několikrát pro každý algoritmus. Simulace navíc proběhla ve dvou variantách - s 10 lidmi a 10 zvířaty na pozemku (označeno jako varianta B) a poté bez zvířat a bez lidí (označeno jako varianta B). Výsledky a specifika jednotlivých algoritmů si probereme níže.

 

Algoritmus 1: uhel-otoceni

Tento velice jednoduchý algoritmus se ukázal býti naprosto nevhodným pro pohyb v prostoru bez lidí a bez zvířat. Protože jsme se pohybovali ve čtvercovém prostředí, úhly jako 45, 90, 30 atd. stupňů se vůbec nedokončily. Průměr 96 961 ticků je nejhorším výsledkem, době strávené na pozemku pak odpovídal i počet zničených dlaždic s trávou, v průměru 2 170 zničených dlaždic. A to nebyl do průměru započítán výsledek hraničící s nekonečnem v případě úhlu 45 stupňů.

Ve variantě B dosahoval algoritmus stejně špatných výsledků, 128 327 ticků a průměrné poškození 2 313.

Špatné výsledky jsou dány hlavně absencí náhody ve variantě A a spoléháním na srážku s některým z ostatních agentů ve variantě B.  

Algoritmus 2: random-uhel-otoceni

Bylo až s překvapením, že jsme mírnou změnou výpočtu úhlu otočení (použitím náhodného generátoru) dokázali dosáhnout až o 1/3 lepších výsledků než u předešlé varianty algoritmu.

 

Algoritmus 3: random-360

Poměrně jednoduchý algoritmus odrážející se zcela náhodně od překážek produkoval poměrně stabilní výsledky jak u varianty A, tak B. Z pokusů bylo zřejmé, že pohyb překážek na pozemku algoritmu svědčí, docházelo tak k časté změně směru a lepšímu pokrytí plochy. Zvolený úhel u tohoto typu pohybu nehrál roli.

 

Algoritmus 6: dlazdice

Algoritmus dlaždice pro mě byl pravděpodobně největším zklamáním. Ačkoliv jsem do této metody vkládal hodně naděje, dosahovala pouze podprůměrných výsledků. Vinu přisuzuji části kódu metody, která reaguje na nenalezení dlaždice s neposekanou trávou, kde dochází k největšímu opotřebovávání okolních dlaždic.

Algoritmus 4: kruh

Algoritmus kruh se projevil býti velice citlivým na nastavení jednotlivých parametrů. Překvapil mě hlavně fakt, že čím větší poloměr kruhu sekačka opisovala, tím lepších výsledků algoritmus dosahoval. Tyto rozdíly vyjadřuje v tabulce střední hodnota, kterou jsme postupně volili 5, 10 a 20.

Pravděpodobně nejpříjemnějším překvapením zde byl fakt, že na algoritmus téměř nemělo vliv nastavení okolních dynamických agentů. Jak ve variantě A, tak ve variantě B, dosahoval velice podobných výsledků.

Algoritmus 5: kruh s random dojezdem

Algoritmus pojmenovaný "kruh s random dojezdem" vznikl prakticky náhodou, čím více jsem ale o něm přemýšlel, tím lepší variantou se jevil. Vycházel jsem z teorie, že na začátku, kdy je velká většina pozemku neposekaná, se sekačce vyplatí jezdit v kruzích a systematicky tak posekat co nejvíce plochy. Po nějaké době by však bylo vhodné, aby sekačka změnila svůj styl pohybu a začala se po dlaždicích pohybovat více náhodně, aby tak dokázala pokrýt zbývající neposekané části.

Tuto teorii následně prokázala i samotná měření, algoritmus dosahoval jasně nejlepších a hlavně nejstabilnějších výsledků.

Závěr

Cílem simulace bylo pozorovat vliv jednotlivých algoritmů a jejich nastavení na dobu trvání sečení a s tím související růst nákladů. Při volbě nejlepšího algoritmu bylo nutné zároveň sledovat poškození trávníku, jakého jednotlivé algoritmy dosahují.

Při plnění tohoto cíle jsme zjistili, že nejvhodnějším algoritmem je kruhový pohyb s přepnutím do náhodného módu, který podával stabilní výsledky při mnoha nastaveních a dosahoval nejlepšího času. Z výsledků jsme zároveň zjistili, že existuje přímá úměra mezi časem stráveným na pozemku a poškozeným trávníkem. Tento poměr se lišil pouze u algoritmu dlaždice, který měl na stejný čas méně poškozených dlaždic než ostatní. Byl by tedy vhodným řešením pro majitele, který neklade důraz na čas sečení, avšak disponuje ne příliš kvalitní sekačkou, která často trávník ničí.

Model nabízí řadu možností pro rozšíření. Kromě implementace nových prvků ovlivňujících model by například bylo vhodné sledovat, za jakou dobu sekačky dosáhnou pokrytí jistého poměru posekaných dlaždic, např. tedy jak rychle daný algoritmus zvládá posekat 90 % celé plochy. Další možností by bylo omezit dobu pobytu sekačky na pozemku a sledovat, kolik dlaždic za takto stanovenou dobu dokáže posekat.

Reference

[1] http://ccl.northwestern.edu/netlogo/ [1]

Kód

zdrojové soubory modelu [2]

Přílohy

celá zpráva v PDF [3]