• View
• Edit
• History
• Print

Zadania

1.  Omówione propozycje projektów

Propozycje są tylko szkicem terytorium. Niektóre są bardziej jednorodne, niektóre mniej — te wymagają wyboru ścieżki, którą się chce pójść, np. bardziej teoretycznej, z implementacją prostego toy universe do testowania możliwości, albo bardziej technicznej, skupionej na “realistycznym” zastosowaniu.

1.1  Formacje

W wielu zadaniach interesuje nas doprowadzenie agentów (robotów) do rozmieszczenia o zadanym wzorze i/lub skoordynowane przemieszczanie się agentów, np. żeby w miarę możliwości utrzymywali dany wzór rozmieszczenia. Przeczytaj lub przejrzyj: Social Potentials for Scalable Multi-Robot Formations, Autonomous Initialization of Robot Formations, A General Algorithm for Robot Formations Using Local Sensing and Minimal Communication, Behavior-based Formation Control for Multi-robot Teams.

Zaprogramuj (“rozwiąż”) w OpenSteer różne zadania formacji boidów:

• “obsadzenie” zadanej konfiguracji: ułożenie boidów w zadany wzór i zatrzymanie ich; wzorem może być okrąg, romb, klucz (literka V), literka Y, itd.
• “obsadzenie” konfiguracji (wzoru jak wyżej) i poruszanie się w niej wzdłóż ścieżki, z wymijaniem przeszkód (czy można regulować stosunek ilości drogi nadłożonej przez poszczególne boidy do stopnia zaburzenia formacji?)
• dla zadań jak wyżej, włączanie do formacji świeżo przybywających boidów (wymaga to przegrupowania zazwyczaj)
• zmiana konfiguracji na inny wzór, np. po przekroczeniu przez grupę zadanego progu liczebności
• jeśli liczebność grupy przekroczy zadany próg, to formacja ma się przegrupować na dwie mniejsze (raczej zgrubsza równoliczne) formacje, o tym samym kształcie (ewentualnie o kształcie z zadanego zbioru kształtów, dobieranie kształtu dającego w danej sytuacji najlepszy czas przegrupowywania może być ciekawe)

Przeczytaj Impossibility of Gathering by a Set of Autonomous Mobile Robots, Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots. Zbadaj, jakie minimalne wymagania względem agentów uda ci się osiągnąć w rozwiązaniu poszczególnych zadań:

• pamięć zbiorowa (współdzielona pomiędzy agentami)
• pamięć indywidualnych agentów
• komunikacja przez przekazywanie wiadomości (nadawca wybiera odbiorcę, wiele wiadomości naraz - komunikacja asynchroniczna)
• komunikacja przez rozgłaszanie (odbiorca wybiera nadawcę, nadawca może rozgłaszać tylko jeden komunikat naraz)
• dostęp do agentów przez globalne identyfikatory
• dostęp do agentów tylko przez lokalizację “wizualną” (agent ma dostęp do anonimowych sąsiadów w zadanym promieniu, możliwe dodatkowe ograniczenie: tylko do agentów przed sobą, w ramach zadanego kąta widzenia)

1.2  Uczenie się (indukcja) sieci behawioralnych

Sieci zachowań są paradygmatem łączącym podejście “niskiego poziomu” sieci neuronowych, z podejściami symbolicznymi “wysokiego poziomu”. Elemantami sieci behawioralnej są możliwe zachowania agenta (zachowania “atomowe”, bazowe). Krawędziami sieci przepływa “energia aktywacyjna”: węzeł, który zgromadzi jej więcej, ma większą szansę na “odpalenie”, czyli wykonanie związanego z nim zachowania. Z zachowaniami związane są warunki wstępne, które muszą być spełnione, jeśli zachowanie ma być wykonane, oraz spodziewane rezultaty zachowania. Krawędzie łączą zachowania, jeśli rezultaty jednego przyczyniają się do spełnienia warunków wstępnych drugiego. W sieci są też uwzględnione cele agenta, krawędzie biegną od celów do zadań, które się do spełnienia tych celów przyczyniają. Przeczytaj How To Do the Right Thing, Pattie Maes (1989) oraz Extended Behavior Networks for Behavior Selection in Dynamic and Continuous Domains, może też Pronomes in Behavior Nets.

Budowanie skutecznej sieci behawioralnej może być bardzo czasochłonne. Fajnie byłoby, gdyby taka sieć mogła powstać automatycznie. Ten sam mechanizm pozwoliłby jej na bieżąco dostosowywać się do zmieniających się warunków środowiska. Przeczytaj Hugo deGaris, PhD Thesis, Chapter 9: Other Work, strony 22–23 (291–292 w pracy), dostosuj opisany mechanizm do “Extended Behavior Networks”. Przeczytaj też przeglądowy artykuł Modeling Adaptive Autonomous Agents. Możesz też przeczytać How Minds Work / Schema Mechanism (wersja multimedialna): włącz techniki “teorii schematów” w swój mechanizm uczenia sieci zachowań.

Możliwa dziedzina zastosowania: Uczenie się agentów zyskuje dodatkowy wymiar, gdy ich środowiskiem są inni agenci, przyjaźni (z pokrywającymi się celami) i wrodzy (z przeciwstawnymi celami). Wykorzystując RoboCup Soccer Simulator, lub OpenSteer, zaprogramuj uczących się graczy drużyny piłkarskiej. Przeczytaj Extended Behavior Networks for the magmaFreiburg Team, porównaj sieci behawioralne z architekturą zastosowaną w The Incremental Development of a Synthetic Multi-Agent System: The UvA Trilearn 2001 Robotic Soccer Simulation Team.

1.3  Naśladowanie

Zazwyczaj różni agenci dysponują różnymi możliwościami. Uniemożliwia to agentowi uczącemu się dokładną imitację zachowań. Przeczytaj Learning How to Do Things with Imitation. Ponadto, agent działa dla osiągnięcia swoich celów, które mogą się nie pokrywać z celami, dla których działa “nauczyciel”. Przeczytaj Reinforcement Learning with Imitation in Heterogeneous Multi-Agent Systems. Porównaj eksperymentalnie przedstawione w tych pracach algorytmy. Możesz zaproponować własny (ciekawszy) problem testowy.

Działanie przez naśladowanie często wykorzystuje się w robotyce lub środowiskach “rzeczywistości wirtualnej”. Celami “niskiego poziomu” tych działań (środkami do realizacji “wyższych” celów) są zadania “inverse kinematics”, ilustrując: “jak poruszyć ręką, aby chwycić kubek w pudełku”, albo bardziej złożone zadania (w animacji nazywane czasami “retargetting”, jeśli mamy rozwiązanie wzorcowe), np. jak poruszać kończynami, aby się przemieszczać. Zadania te możemy rozwiązywać budując zachowanie od podstaw, traktując problem jako zadanie optymalizacji nieliniowej (zapoznaj się z Introduction to Inverse Kinematics with Jacobian Transpose, Pseudoinverse and Damped Least Squares methods). Zachowanie możemy też składać łącząc i dostosowując zachowania prostsze; repertuar zachowań pierwotnych musimy wtedy zaprogramować ręcznie lub pozyskać innymi metodami (zadanie ciekawe same w sobie). Przeczytaj Primitive-Based Movement Classification for Humanoid Imitation. W jaki sposób wyniki z poprzedniego akapitu stosują się tutaj? W naśladowaniu zazwyczaj istotna jest segmentacja obserwowanych działań, zapoznaj się z Self-Segmentation of Sequences: Automatic Formation of Hierarchies of Sequential Behaviors (patrz też poniżej: zastosowano proste segmentowanie w momentach ustania ruchu). Zaprogramuj ramię z dwoma stawami naśladujące zachowanie ramienia z trzema stawami, lub ciekawszy problem, wykorzystując składanie zachowań bazowych.

Zachowania służą celom agentów, realizowanym w ramach społeczności agentów. Często obserwując zachowania wnioskujemy o celach agentów. Przeczytaj Imitation as a First Step to Social Learning in Synthetic Characters: A Graph-based Approach. Zaprogramuj środowisko analogiczne do zaprezentowanego w tej pracy. Agent może mieć różne strategie wyboru agentów do naśladowania, zapoznaj się z Human’s Meta-cognitive Capacities and Endogenization of Mimetic Rules in Multi-Agents Models lub Metareflexive Mimetism: The prisoner free of the dilemma. Możesz zaprogramować środowisko do testowania różnych strategii.

Dalsza literatura:

• Proceedings of the Third International Symposium on Imitation in Animals and Artifacts
• The progress drive hypothesis: an interpretation of early imitation

1.4  Information Retrieval Agents

Linki:

• GOOSE: a goal-oriented search engine with commonsense (slajdy)
• Juergen Schmidhuber’s Curious Agents
• Wyszukiwanie informacji w sieci, wykład Tomasza Jurdzińskiego
• Contexts, Oracles, and Relevance Akman, Varol and Surav, Mehmet (1995) We focus on how we should define the relevance of information to a context for information processing agents, such as oracles.
• If you could build the perfect search engine for you, what would it do? LinkedIn Answers
• Focused Web Crawling using an Auction-based Economy, E. B. Baum, Erik Kruus, Igor Durdanovic and John Hainsworth, October 2002
• Knowledge-Based Agents for Advanced Information Access

2.  Nowe propozycje projektów

2.1  Systemy wieloagentowe w ocenianiu / planowaniu / projektowaniu miast / budynków / etc.

• ASSESSING URBAN MICROCLIMATE USING MULTI-AGENT SIMULATIONS: A NEW APPROACH TO ANSWER AN OLD PROBLEM?, http://www.botworld.info/
• Integrated urban system modelling: methodology and case study using multi-agent systems
• Multi-Agent Systems for the Simulation of Land-Use and Land-Cover Change: A Review
• Curious Design Agents and Artificial Creativity: A Synthetic Approach to the Study of Creative Behaviour

2.2  Symulacje agentowe w antropologii poznawczej

• Computer-based Simulation Modelling for Anthropologists
• An Open Mind is not an Empty Mind: Experiments in the Meta-Noosphere
• Mnemonic Structure and Sociality: A Computational Agent-Based Simulation Model
• Bootstrapping grounded symbols by minimal autonomous robots Vogt, Paul (2000)

2.3  Psychologia poznawcza a hybrydowe architektury agentów

Projekt dotyczy związków architektury agentów i wyników psychologii poznawczej. Przypomnij sobie opowiadanie “Ananke” z cyklu “Przygody pilota Pirxa” Stanisława Lema. Zapoznaj się z jakąś całościową propozycją z dziedziny psychologii poznawczej, np.: książka “Czuję, myślę, jestem. Ówiadomość i procesy psychiczne w ujęciu poznawczym” Aliny Kolańczyk. Przeczytaj np. G53DIA Designing Intelligent Agents / Hybrid architectures i wybrane dalsze materiały o architekturach hybrydowych, np. A Hybrid Agent Architecture for Dynamic and Unpredictable Environments (przykład dla RoboCup); zapoznaj się z architekturami AGI, które siłą rzeczy są hybrydowe. Zaimplementuj agenta hybrydowego o architekturze opartej na obranej teorii psychologicznej oraz środowisko testowe i przetestuj przewidywania teorii. W przypadku proponowanej książki, zamodeluj świadomość w architekturze agenta, np. jej rolę w formowaniu pamięci epizodycznej.

Niektóre zagadnienia: A Survey of Cognitive and Agent Architectures.

3.  Początkowe propozycje zadań

1. (OpenSteer) Boidy poruszające się w formacjach. W programach nie wykorzystuj narzuconej z góry trajektorii ani nie przechowuj informacji o wszystkich boidach, posługuj się tylko “lokalnymi” obserwacjami boidów. Formacje powinny się dostosowywać do ilości boidów w grupie.
   1. Zaprogramuj boidy poruszające się w trzech wymiarach tak, aby samoczynnie formowały “klucze”.
   2. Zaprogramuj boidy poruszające się na płaszczyźnie tak, aby poruszające się grupy samoczynnie formowały okręgi (n-kąty foremne). Prędkość okręgu powinna zgrubsza pokrywać się z prędkością boidów (wykluczamy sytuację, w której boidy większość energii marnują na jeżdżenie w kółko).
2. (Włąsna implementacja) Zaprogramuj algorytm wychodzenia z labiryntu oraz wizualizację jego działania. (Wizualizacja powinna być prosta.)
3. (JADE) Zaprogramuj system dystrybucji zasobów obliczeniowych jako system aukcyjny (Vickrey’s Auction). Zadaniem obowiązkowym na pracownię jest zaprogramowanie jakiejś minimalnej, uproszczonej formy systemu.
   • Modelujemy sieć komputerową, w której każdy komputer ma określoną moc obliczeniową (dalej nazywaną MIPS) i określoną pamięć operacyjną.
   • Zadania wykonywane w sieci wymagają określonej ilości MI do wykonania, oraz dla uproszczenia określonej ilości pamięci w każdej chwili wykonywania.
   • Komputer może wykonywać n zadań jednocześnie, przy czym każdemu zadaniu przydziela ustaloną ilość mocy obliczeniowej, tak że ite zadanie wykonuje się w czasie \frac{MI_i}{MIPS_i}, oraz MIPS_1 + \dots + MIPS_n \leq MIPS. Podobnie suma pamięci wymaganych przez poszczególne zadania jest mniejsza od ilości pamięci dostępnej na komputerze.
   • Zleceniodawca zadania wyznacza minimalną moc obliczeniową jakiej wymaga oraz maksymalną cenę jaką może zapłacić.
   • Komputer, który chce i może wykonać zadanie, proponuje swoją cenę, nie znając propozycji innych komputerów.
   • Zleceniodawca wybiera komputer, który zaproponował najniższą cenę, ale wypłaca mu drugą najniższą kwotę (najniższą cenę spośród pozostałych propozycji).
   • Celem komputerów jest zarobienie jak najwięcej w dłuższym okresie.
   • Zaprogramuj agentów modelujących komputery w sieci i agentów modelujących zleceniodawców. Dla celów symulacji zaprogramuj generator zleceń.
   • Porównaj kilka strategii dla agentów-komputerów.
4. (RoboCup Soccer Simulator - preferowany, lub OpenSteer) Zaprogramuj graczy drużyny piłkarskiej. Porównaj strategie m.in.:
   • gry pozycyjnej (gracze mają przydzielone obszary aktywności)
   • krycia (gracze mają przydzielonych kontrgraczy)
   • aktywnego szukania wolnego pola gry