Avtomatsko modeliranje večagentnih sistemov : doktorska disertacija

Bežek, Andraž (author), Bratko, Ivan (mentor), Gams, Matjaž (comentor)

Ena najtežjih, do sedaj nerešenih nalog večagentnega modeliranja je iz sledenja nizkonivojskega obnašanja skupine agentov in zgolj osnovnega domenskega znanja ugotoviti, kakšno skupno strategijo izvajajo. Ta naloga je zahtevna iz dveh ključnih razlogov. Prvič, agenti so samostojne entitete, ki skušajo v nenehni interakciji s sodelujočimi agenti, nasprotnikovimi agenti ter okoljem skladno izvajati vnaprej dogovorjeno strategijo. Iz nizkonivojskega opisa delovanja posameznih agentov je zato težko izluščiti visokonivojsko strategijo skupine agentov. Drugič, pri učenju ima sistem poleg opazovanja nizkonivojskega obnašanja na voljo le osnovno domensko znanje. Tako osnovno domensko znanje je običajno na razpolago, naloga pa zahteva odkrivanje bolj poglobljenega znanja, kakršnega imajo le domenski strokovnjaki. V disertaciji je predstavljen izvirni algoritem za strateško modeliranje MASDA (angl. Multi-Agent Strategy Discovering Algorithm), ki skuša iz sledenja nizkonivojskega obnašanja skupine agentov in zgolj osnovnega domenskega znanja ugotoviti, kakšno skupno strategijo izvajajo. MASDA uporablja postopek abstrakcije, ki omogoča ločevanje modelov agentnega delovanja, ki so posledica izvrševanja večagentne strategije, od modelov, ki so posledica agentnih odzivov na lokalne spremembe okolja. Zgrajeni model opisuje sodelovanje agentov, predstavljeno v grafični in simbolni obliki; grafični opis omogoča vizualno predstavitev večagentnega delovanja, simbolni opis pa na človeku razumljiv način predstavi pomembne značilnosti večagentne interakcije. S tem je omogočena človeška analiza, razlaga ter avtomatska klasifikacija. Uspešnost algoritma smo v disertaciji prikazal na dveh večagentnih domenah. V domeni robotskega nogometa RoboCup zgrajeni modeli po mnenju domenskega strokovnjaka vsebinsko opisujejo del nogometne strategije. Meritve z osnovnimi kriteriji strojnega učenja na osnovi: klasifikacijske točnosti, priklica in natančnosti, potrjujejo primernost uporabe modelov MASDA pri avtomatski klasifikaciji. V domeni agentnega podajanja žoge 3vs2 Keepaway je bila deklarativna uspešnost modela potrjena v primerjavi z izvorno kodo treh znanih strategij, ujemanje posnemanja igranja pa s primerjanjem časovne uspešnosti ter s strojnim in človeškim primerjanjem ujemanja izvajanih akcij.

• Language: Slovenian
• Keywords: večagentni sistemi, modeliranje, agent, strategija, interakcija
• Work type: Dissertation
• Typology: 2.08 - Doctoral Dissertation
• Organization: FRI - Faculty of Computer and Information Science
• Publisher: [A. Bežek]
• Year: 2006
• Number of pages: XV, 144 str.
• PID: 20.500.12556/RUL-68071
• UDC: 004.4:004.8
• COBISS.SI-ID: 20477735
• Publication date in RUL: 10.07.2015

Secondary language

• Language: English
• Title: Automatic modeling of multiagent

Abstract

One of the most difficult unsolved tasks in the field of multi-agent modeling is to discover common agent strategy by knowing only low-level agent behavior and basic domain knowledge. This task is difficult for the following two reasons. First, agents are autonomous entities that try to accomplish in advance given strategy, while continuously interacting with team-agents, adversary-agents, and the environment. By giving only low-level descriptions of single agent behaviors, high-level strategy is therefore difficult to discover. Second, in addition to low-level agent behavior, the system utilizes only basic domain knowledge. Such knowledge is often available and the task is to discover high-level knowledge, usually available only to experts. This dissertation presents a novel algorithm for strategic modeling MASDA (Multi-Agent Strategy Discovering Algorithm). By tracking low-level behavior of a group of agents and using only basic domain knowledge, it tries to discover common agent strategy. MASDA incorporates an abstraction process, which enables MASDA to separate models that are due to following of agent strategy, from models that are due to agent reactions to local environment changes. The created model describes collaboration of agents in a graphical and symbolical manner. Graphic descriptions visually present multi-agent activity, while symbolic descriptions present important characteristics of multi-agent interaction in a human-comprehendible way. By that human analysis, interpretation and automatic classification is possible. Efficiency of the algorithm was shown on two multi-agent domains. In the domain of robotic soccer – RoboCup, the human expert confirmed that the created model semantically describes part of real-life soccer strategy. Measurements of classification accuracy, recall, and precision confirm suitability of MASDA models for computer classification. In the domain of ball keep away problem – 3vs2 Keepaway, the declarative efficiency of the model was confirmed by comparing it with source code for three known strategies and the strategy imitation performance was shown by measuring time efficiency and by human and computer comparison of played actions.

• Keywords: multi agent systems, modelling, agent, strategy, interaction