Příklady Pojmy Decentralizované myšlení Role modelování Modelování založené na agentech a decentralizované myšlení Radek Pelánek Příklady Pojmy Decentralizované myšlení Role modelování Terminologie standardní anglický pojem: agent-based modeling (ABM) česky též např. „multiagentní modelování Příklady Pojmy Decentralizované myšlení Role modelování Typy modelů deduktivní výpočetní „shora analytické makro modely systémové modely „zdola teorie her ABM (jeden z mnoha způsobů škatulkování modelů) Příklady Pojmy Decentralizované myšlení Role modelování Východiska buněčné automaty (decentralizace, lokální interakce) umělá inteligence (učení, vývoj) Příklady Pojmy Decentralizované myšlení Role modelování Postup ABM – spíše metodologie než fixně daný formalismus ilustrace především na příkladech následně shrnutí hlavních principů Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Dravec-kořist NetLogo: Biology / Wolf Sheep Predation základní předpoklady jako při systémovém modelování dravec se živí pouze kořistí, kořist regulována (pouze) dravcem modelujeme jednotlivé tvory, pravidla: náhodný pohyb požírání při kontaktu Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Model osidlování ostrova potravní řetězec: 3 rostliny, 2 býložravci, 1 masožravec ostrov na počátku holý, organismy imigrují, množí se parametry modelu: rychlost imigrace, příznivost podmínek, velikost ostrova účel modelu: ilustrovat vztahy mezi parametry a výslednou diverzitou a stabilitou na ostrově Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Hlenka (slime mold) Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Hlenka (slime mold) dva módy chování: hodně potravy ∼ mnoho samostatných jednobuněčných organismů málo potravy ∼ shlukne se a vytvoří jeden mnohobuněčný organismus jak se shlukuje? látka cAMP hypotéza pacemaker cells http://www.youtube.com/watch?v=bkVhLJLG7ug http://www.youtube.com/watch?v=leKI3Cv9YYw Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Model hlenky NetLogo: Biology / Slime abstraktní model shlukování buněk hlenky pravidla: náhodný pohyb buňky při pohybu vylučují feromon při pohybu upřednostňují místa s vyšším výskytem feromonu zpětné vazby: pozitivní: víc buněk, víc feromonu negativní: větší shluky, méně volných buněk Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Model hlenky ke shlukování dochází i bez přítomnosti pacemaker cells fázový přechod (phase transition): do určitého množství buněk/rychlosti vypařování feromonu nedochází k žádnému shlukování jakmile je překročena mez, dochází k velkému shlukování Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Hádanka Který živočišný druh: obývá všechny kontinenty kromě Antarktidy tvoří možná až 15 % hmotnosti všech živočichů tvoří rozsáhlá společenství s dělbou rolí provozuje zemědělství a otrokářství ? Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Mravenci jeden z nejúspěšnějších živočišných druhů oblíbený předmět pro studium decentralizovaných systémů mraveniště jako celek mají „inteligenci , „osobnost emergence – tyto vlastnosti nemají žádný odraz v jednotlivých mravencích (srovnej s neurony a mozkem) http://www.youtube.com/watch?v=A042J0IDQK4 http://www.ted.com/talks/deborah_gordon_digs_ants.html Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Mravenci: inteligence pokusy v laboratoři, omezená plocha umístění hřbitova, skládky: maximalizace vzdáleností hledání nejkratších cest k potravě mraveniště jako celek řeší netriviální matematické úlohy Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Mravenci: osobnost mraveniště jednotliví mravenci žijí krátkou dobu, mraveniště jako celek přežívá dlouho s věkem se mění charakter mraveniště (agresivní, dobyvačné → klidné, ustálené) průměrný věk mravenců je stále přibližně stejný Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Mravenci: model NetLogo: Biology / Ants prostředí: mraveniště + zdroje jídla pravidla: mravenci se pohybují náhodně po prostoru najdou jídlo ⇒ cestou zpět do mraveniště vypouští feromon hledání ⇒ upřednostňují místa s vyšší koncentrací feromonu Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Mravenci: poznámky k modelu Zpětné vazby: pozitivní: víc feromonu, víc mravenců negativní: větší shluky, méně volných mravenců; víc jídla, víc mravenců, rychlejší čerpání jídla Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Termiti NetLogo: Biology / Termites prostředí: rozházené kusy dřívek pravidla: termiti chodí náhodně po prostoru když termit narazí na dřívko: pokud zrovna nic nenese, tak dřívko zvedne pokud zrovna něco nese, tak dřívko položí a jde pryč Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Hejno představte si velké hejno ptáků zkuste vymyslet lokální pravidla pro ptáky, aby se celek choval jako „hejno http://www.youtube.com/watch?v=81wFZavdhPU Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Hejno (boids) Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Boids: poznámky velmi známý model mnoho rozšíření počítačová grafika NetLogo: Biology / Flocking http://www.red3d.com/cwr/boids/ http://www.youtube.com/watch?v=rN8DzlgMt3M – rozšířená verze Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Světlušky http://www.ted.com/talks/steven_strogatz_on_sync.html (cca 8:30) Příklady Pojmy Decentralizované myšlení Role modelování Přírodní systémy Světlušky NetLogo: Biology / Fireflies model globální synchronizace světlušek (projevuje se u některých druhů) pravidla světlušek: náhodný pohyb blikání v pravidelném intervalu drobné přizpůsobení blikání ostatním světluškám v okolí Příklady Pojmy Decentralizované myšlení Role modelování Lidské systémy Příklady Pojmy Decentralizované myšlení Role modelování Lidské systémy New York http://www.flickr.com/photos/walkingsf/sets/ 72157624812674967/ Příklady Pojmy Decentralizované myšlení Role modelování Lidské systémy Model segregace NetLogo: Social Science / Segregation Thomas Schelling – původní model prostředí: město tvaru mřížky, dva druhy obyvatel (červení, zelení) p – míra tolerance obyvatelé jsou spokojení, pokud p % sousedů je stejných nespokojený ⇒ přestěhování na náhodné volné pole Příklady Pojmy Decentralizované myšlení Role modelování Lidské systémy Model segregace: chování i při velké toleranci (stačí 30 % stejných): vytváření jednodruhových shluků (ghet) výrazná segregace obyvatel Příklady Pojmy Decentralizované myšlení Role modelování Lidské systémy Dopravní zácpa NetLogo: Social Science / Traffic Basic model decentralizovaného vzniku dopravní zácpy auta jedou po silnici, snaží se udržovat si drobný odstup od toho před sebou, ale jinak co nejrychleji Příklady Pojmy Decentralizované myšlení Role modelování Lidské systémy Dopravní zácpa: chování modelu při dostatečné hustotě aut se vytváří zácpa (i bez vnější příčiny) pomalu se „pohybuje proti směru pohybu aut Příklady Pojmy Decentralizované myšlení Role modelování Lidské systémy Videa k tématu http://www.youtube.com/watch?v=svPtt-6Kdy4 můj stručný výtah z dnešní přednášky mravenci, hlenka, hejno http://www.youtube.com/watch?v=uHboHI2_KKU Petr Jarušek rasová segregace Příklady Pojmy Decentralizované myšlení Role modelování Další aplikace Další aplikace ABM občanské nepokoje trhy ekosystémy epidemie válečné konflikty (ve velkém), souboje (v malém) (většina bude zmíněna podrobněji později) Příklady Pojmy Decentralizované myšlení Role modelování Další aplikace Další příklady decentralizovaných systémů úvodní cvičení Manchester – růst města Internet doporučující systémy (např. Amazon) Příklady Pojmy Decentralizované myšlení Role modelování Další aplikace Další zajímavé zdroje Swarming, swirling and stasis in sequestered bristle-bots https://www.youtube.com/watch?v=0uqsRGFLM20 Mick Mountz: The hidden world of box-packing http://www.ted.com/talks/mick_mountz_the_hidden_world_ of_box_packing.html Příklady Pojmy Decentralizované myšlení Role modelování Základy ABM Základní prvky modely založeny na autonomních agentech, tj. modelujeme zdola, agenti nedostávají žádné příkazy shora důležitou součástí modelů je prostředí, ve kterém se agenti pohybují (a které se může též měnit) interakce je pouze lokální agenti jsou (relativně) jednoduší agenti nejsou vázáni na pevné místo, pohybují se po prostředí agenti nejsou homogenní, mohou se i vyvíjet Příklady Pojmy Decentralizované myšlení Role modelování Základy ABM Realizace ABM počítačová simulace je klíčová přirozená implementace: objektové programování specializované nástroje, např: NetLogo (vlastní jednoduchý jazyk) RePast (Java) Swarm (Java) Příklady Pojmy Decentralizované myšlení Role modelování Srovnání s jinými přístupy Srovnání ABM a SD systémová dynamika modelování založené na agentech pohled „shora „zdola základní bloky sumární veličiny jednotlivci a interakce mezi nimi zpětné vazby explicitně vyjádřeny modelovány nepřímo centrum zájmu struktura systému pravidla pro chování agentů Příklady Pojmy Decentralizované myšlení Role modelování Srovnání s jinými přístupy Srovnání ABM a SD systémový přístup modelování založené na agentech přístup deduktivní: od struktury k chování induktivní: od chování jednotlivců k chování celku model v čase fixní agenti mohou být adaptivní čas většinou spojitý většinou diskrétní Příklady Pojmy Decentralizované myšlení Role modelování Studované vlastnosti systémů Studované vlastnosti systémů emergentní chování (emergence) chování na úrovni celku, které nemá přímý vzor v chování na úrovni jedinců samo-organizace (self-organization) nárůst interní organizace systému bez externího řízení fázový přechod (phase transition) prudká změna chování systému při postupné změně vnějších parametrů robustnost, efektivita Příklady Pojmy Decentralizované myšlení Role modelování Centralizované myšlení Centralizované vs. decentralizované myšlení lidé – přirozená tendence myslet centralizovaně komplexní systémy – často značně decentralizované Příklady Pojmy Decentralizované myšlení Role modelování Centralizované myšlení Centralizované myšlení důraz na negativní zpětnou vazbu, regulující schopnosti zjednodušené uvažování o příčinách a následcích (jednosměrné vazby místo zpětnovazebních cyklů) hledáme centralizované příčiny: vedení, semínka Příklady Pojmy Decentralizované myšlení Role modelování Centralizované myšlení Centralizované myšlení: příklady hlenka a „pacemaker cells mraveniště a královna, hejno (stádo) a vedoucí pták (beran) zácpy (kapitalistická) ekonomika a vliv vlády (výzkum izraelské děti) Příklady Pojmy Decentralizované myšlení Role modelování Tipy pro decentralizované myšlení Decentralizované myšlení pozitivní zpětné vazby role náhody při vytváření řádu rozlišování úrovní, celků: „hejno není velký pták „zácpa není soubor aut Termites, turtles, and traffic jams. Mitchel Resnick. The MIT Press, 1997. Příklady Pojmy Decentralizované myšlení Role modelování Tipy pro decentralizované myšlení Pozitivní zpětná vazba pozitivní zpětná vazba běžně vnímána jako destruktivní (nádor, epidemie, destabilizace) decentralizované systémy – vytváření a rozšiřování struktur příklady: hlenka, mravenci, hejno další: firmy (viz Polya process), vznik měst Příklady Pojmy Decentralizované myšlení Role modelování Tipy pro decentralizované myšlení Náhoda běžně vnímána jako destruktivní prvek intuitivní centralizovaná „semínka – často vznik díky náhodě často: náhoda + pozitivní zpětné vazba = řád může vést k překonání lokálního optima – viz hlenka další příklady: tleskání, ztracený mravenec Příklady Pojmy Decentralizované myšlení Role modelování Tipy pro decentralizované myšlení Hejno není velký pták rozlišování jednotlivých úrovní na úrovni celku můžeme dostat jiné chování než na úrovni jednotlivců (emergentní chování) příklad kytka: buňky rostou rychleji ve tmě kytka se tím naklání ke světlu Příklady Pojmy Decentralizované myšlení Role modelování Tipy pro decentralizované myšlení Zácpa není soubor aut běžné vnímání: celek = soubor částí, ale vlna není soubor molekul vody mraveniště není soubor mravenců člověk není soubor buněk zácpa se pohybuje opačným směrem než auta Příklady Pojmy Decentralizované myšlení Role modelování Tipy pro decentralizované myšlení Robustnost, efektivita centralizované decentralizované stroje přírodní systémy autokracie demokracie plánované hospodářství volný trh Příklady Pojmy Decentralizované myšlení Role modelování Tipy pro decentralizované myšlení Robustnost, efektivita Monarchie je jako nádherný koráb plující pod plnými plachtami majestátně vpřed. Najednou narazí na útes a klesne navždy ke dnu. Demokracie je jako vor. Nikdy, nikdy se nepotopí, ale proklatě, nohy máte furt ve vodě! Příklady Pojmy Decentralizované myšlení Role modelování Tipy pro decentralizované myšlení Fázový přechod Aktuální např. při vymírání živočišných druhů: na úrovni druhů (např. holub stěhovavý) na úrovni ekosystémů Příklady Pojmy Decentralizované myšlení Role modelování FIbot Soutěž FIbot programátorská soutěž na FI, 2. ročník (podzim 2006 + jaro 2007) návrh decentralizovaného systému spolupracujících autonomních agentů reálné příklady: autonomní navigace systémů pro objevování vesmíru (jedna z technologií testovaných u Deep Space 1, ve fázi návrhu jsou týmy autonomních robotů) internetoví agenti pro vyhledávání informací roboti pro záchranné akce při katastrofách týmy robotů hrající fotbal jedná se v podstatě o „abstraktní model uvedených reálných případů Příklady Pojmy Decentralizované myšlení Role modelování FIbot FIbot 2 Příklady Pojmy Decentralizované myšlení Role modelování FIbot Pravidla roboti se pohybují na mřížce (volná pole, zdi), omezená viditelnost cíl: nanosit co nejvíce pokladů na svoji základnu akce robotů: zvednout, položit poklad přesun na vedlejší pole zaslání zprávy všem robotům (10 bytů) Příklady Pojmy Decentralizované myšlení Role modelování FIbot Poznámky pravidla velice jednoduchá návrh dobrých strategií komplikovaný decentralizace, paralelismus ⇒ neintuitivnost, zdánlivě dobré nápady nefungují (a občas i naopak) náhoda může být elegantním řešením, např. řešení konfliktů, rozdělení rolí Příklady Pojmy Decentralizované myšlení Role modelování Role modelování a simulace u uvedených příkladů: nejde o předpovídání chování systémů nejde ani tak moc o přesné vysvětlení principů, na kterých systémy fungují jde zejména o styl uvažování o systémech vývoj nových koncepčních i výpočetních nástrojů podporujících decentralizované uvažování o systémech