Многоагентные системы принятия решений Pałka

Spis tresci

1 Wprowadzenie 13

1.1 Rys historyczny . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2 Dzisiejsza rzeczywistosc . . . . . . . . . . . . . . . . . . . . . 14

1.3 Układ pracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 Podstawowe pojecia 17

2.1 Aktor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2 Aktywny obiekt . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3 Aktywny komponent . . . . . . . . . . . . . . . . . . . . . . . 18

2.4 Agent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.5 System agentowy . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.6 System wieloagentowy . . . . . . . . . . . . . . . . . . . . . . 20

2.7 Modele oparte na agentach (ang. agent-based models) . . . . . 21

2.8 Model Belief-Desire-Intention . . . . . . . . . . . . . . . . . . 21

2.9 Holon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.10 Róznice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.11 Podsumowanie . . . . . . . . . . . . . . . . . . . . . . . . . . 23

I Tworzenie systemów wieloagentowych 25

3 Komunikacja 27

3.1 Komunikat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.2 Teoria aktów mowy . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2.1 Akt mowy (lingwistycznie) . . . . . . . . . . . . . . . 28

3.2.2 Performatywa . . . . . . . . . . . . . . . . . . . . . . . 29

3.3 Struktura wiadomosci . . . . . . . . . . . . . . . . . . . . . . 30

3.4 Jezyki komunikacji agentów . . . . . . . . . . . . . . . . . . . 31

3.4.1 FIPA . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.4.2 Jezyk komunikacji FIPA-ACL . . . . . . . . . . . . . . 33

3.4.3 Struktura wiadomosci wg FIPA . . . . . . . . . . . . . 34

7

3.5 Jezyki tresci . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.5.1 Sposoby przekazywania tresci . . . . . . . . . . . . . . 35

3.6 Akty komunikacyjne . . . . . . . . . . . . . . . . . . . . . . . 39

3.7 Protokoły interakcji . . . . . . . . . . . . . . . . . . . . . . . 42

3.8 Podsumowanie . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4 Metody słuzace do projektowania systemów agentowych 45

4.1 Prometheus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.1.1 Specyfikacja systemu . . . . . . . . . . . . . . . . . . . 47

4.1.2 Projektowanie architektoniczne . . . . . . . . . . . . . 48

4.1.3 Projektowanie szczegółowe . . . . . . . . . . . . . . . 49

4.1.4 Diagramy . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.2 Gaia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.2.1 Faza analizy . . . . . . . . . . . . . . . . . . . . . . . . 53

4.2.2 Faza projektowania . . . . . . . . . . . . . . . . . . . . 62

4.3 AUML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4.3.1 Diagram protokołu . . . . . . . . . . . . . . . . . . . . 66

4.3.2 Konektory . . . . . . . . . . . . . . . . . . . . . . . . . 67

4.3.3 Zagniezdzona i przeplatana interakcja . . . . . . . . . 67

4.3.4 Rozszerzone znaczenie komunikatów . . . . . . . . . . 69

4.4 AML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

4.4.1 Semi-encje AML . . . . . . . . . . . . . . . . . . . . . 70

4.4.2 Encje AML . . . . . . . . . . . . . . . . . . . . . . . . 71

4.4.3 Modelowanie aspektów społecznych systemu wieloagentowego

. . . . . . . . . . . . . . . . . . . . . . . . 72

4.4.4 Modelowanie interakcji . . . . . . . . . . . . . . . . . . 74

4.4.5 Modelowanie zachowan i zdolnosci . . . . . . . . . . . 77

4.5 Tropos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

4.5.1 Modelowanie aktora . . . . . . . . . . . . . . . . . . . 80

4.5.2 Modelowanie zaleznosci . . . . . . . . . . . . . . . . . 80

4.5.3 Modelowanie celów . . . . . . . . . . . . . . . . . . . . 80

4.5.4 Modelowanie planów . . . . . . . . . . . . . . . . . . . 81

4.5.5 Modelowanie zdolnosci . . . . . . . . . . . . . . . . . . 81

4.5.6 Graficzna reprezentacja modelu . . . . . . . . . . . . . 81

4.6 Podsumowanie . . . . . . . . . . . . . . . . . . . . . . . . . . 81

5 Platformy i jezyki agentowe 83

5.1 Platformy agentowe ogólnego zastosowania . . . . . . . . . . . 83

5.1.1 Java Agent DEvelopment framework . . . . . . . . . . 83

5.1.2 SPADE . . . . . . . . . . . . . . . . . . . . . . . . . . 99

5.1.3 Eve . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

5.2 Platformy i jezyki w podejsciu BDI . . . . . . . . . . . . . . . 104

8

5.2.1 JACK Inteligent Agents . . . . . . . . . . . . . . . . . 104

5.2.2 Jadex . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

5.2.3 Jason . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

5.3 Platformy symulacyjne . . . . . . . . . . . . . . . . . . . . . . 108

5.3.1 GAMA: agent-based, spatially explicit, modeling and

simulation platform . . . . . . . . . . . . . . . . . . . 108

5.3.2 NetLogo . . . . . . . . . . . . . . . . . . . . . . . . . . 110

5.3.3 Repast . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

5.4 Jezyk SARL i platforma holoniczna Janus . . . . . . . . . . 111

5.4.1 SARL . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

5.4.2 Janus . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

5.5 Podsumowanie . . . . . . . . . . . . . . . . . . . . . . . . . . 115

II Zastosowanie systemów wieloagentowych 117

6 Komercyjne aplikacje agentowe 119

6.1 Telecom Italia Group . . . . . . . . . . . . . . . . . . . . . . . 119

6.2 Agent Oriented Software Pty. Ltd. . . . . . . . . . . . . . . . 120

6.2.1 Rational Information Broker . . . . . . . . . . . . . . 120

6.2.2 Wsparcie dla handlu ropa naftowa i zarzadzaniem

operacyjnym . . . . . . . . . . . . . . . . . . . . . . . 121

6.2.3 Surveillance Agent . . . . . . . . . . . . . . . . . . . . 121

6.3 Magenta Technology . . . . . . . . . . . . . . . . . . . . . . . 122

6.4 Whitestein Technologies AG . . . . . . . . . . . . . . . . . . . 123

6.5 Eurobios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

7 Aplikacje agentowe w projektach niekomercyjnych 125

7.1 Aplikacje słuzace do układania planów . . . . . . . . . . . . . 125

7.2 Wsparcie transportu . . . . . . . . . . . . . . . . . . . . . . . 126

7.3 Wieloagentowa platforma handlowa . . . . . . . . . . . . . . . 126

7.3.1 Koncepcja wieloagentowej platformy wymiany towarowej

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

7.3.2 Struktura agentów . . . . . . . . . . . . . . . . . . . . 128

7.3.3 Mechanizm ofertowania . . . . . . . . . . . . . . . . . 129

7.3.4 Komunikacja miedzyagentowa . . . . . . . . . . . . . . 129

7.3.5 Protokół wymiany komunikatów . . . . . . . . . . . . 129

7.3.6 Jezyk komunikacji agentów . . . . . . . . . . . . . . . 131

7.4 Handel na rynku pozwoleniami na emisje gazów cieplarnianych132

7.4.1 Role agentów i ich opis . . . . . . . . . . . . . . . . . . 132

7.4.2 Implementacja w JADE . . . . . . . . . . . . . . . . . 134

7.5 Carpooling w warszawskim Mordorze . . . . . . . . . . . . . . 136

9

7.5.1 Warszawski Mordor . . . . . . . . . . . . . . . . . . . 136

7.5.2 Agent ork . . . . . . . . . . . . . . . . . . . . . . . . . 138

7.5.3 Model przejsc agenta . . . . . . . . . . . . . . . . . . . 139

7.5.4 Wyniki testów . . . . . . . . . . . . . . . . . . . . . . 141

7.6 Bilansowanie niedoborów i nadmiarów energii w mikrosieci . . 145

7.6.1 Podział urzadzen w systemie . . . . . . . . . . . . . . 145

7.6.2 Role agentów . . . . . . . . . . . . . . . . . . . . . . . 147

7.6.3 Diagram konwersacji systemu . . . . . . . . . . . . . . 148

7.6.4 Diagram choreografii dla systemu . . . . . . . . . . . . 149

7.6.5 Diagram kolaboracji . . . . . . . . . . . . . . . . . . . 150

7.6.6 Implementacja i przykładowe wyniki testów . . . . . . 151

III Algorytmy wspomagania decyzji w systemach wieloagentowych

153

8 Algorytmy stosowane w systemach wieloagentowych 155

8.1 Rozproszone spełnianie ograniczen . . . . . . . . . . . . . . . 156

8.1.1 Problem spełniania ograniczen . . . . . . . . . . . . . 156

8.1.2 Algorytm z nawrotami . . . . . . . . . . . . . . . . . . 158

8.1.3 Rozproszony problem spełniania ograniczen . . . . . . 160

8.1.4 Asynchroniczny algorytm z nawrotami (ang. asynchronous

backtracking) . . . . . . . . . . . . . . . . . . 161

8.1.5 Zastosowania . . . . . . . . . . . . . . . . . . . . . . . 165

8.2 Algorytmy aukcyjne . . . . . . . . . . . . . . . . . . . . . . . 166

8.2.1 Problem przydziału – problem liniowy . . . . . . . . . 166

8.2.2 Zadanie szeregowania – problem całkowitoliczbowoliniowy

mieszany . . . . . . . . . . . . . . . . . . . . . 171

8.3 Protokół tworzenia sieci kontraktów (ang. Contract Net Protocol

) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

8.3.1 Etapy protokołu . . . . . . . . . . . . . . . . . . . . . 175

8.3.2 Tworzenie sieci wykonawców . . . . . . . . . . . . . . 176

8.3.3 Wykorzystanie w procesach handlowych . . . . . . . . 177

8.3.4 Zastosowania . . . . . . . . . . . . . . . . . . . . . . . 178

8.4 Algorytmy inteligencji stadnej . . . . . . . . . . . . . . . . . . 178

8.4.1 Samoorganizacja społecznosci . . . . . . . . . . . . . . 180

8.4.2 Algorytm kolonii mrówek (ang. ant colony optimization)180

8.4.3 Algorytm pszczelej kolonii (ang. artificial bee colony) . 181

8.4.4 Algorytm szarego wilka (ang. gray wolf optimizer) . . 183

8.4.5 Model boida . . . . . . . . . . . . . . . . . . . . . . . 184

8.4.6 Metoda roju czastek (ang. particle swarm optimization)185

8.4.7 Zastosowania . . . . . . . . . . . . . . . . . . . . . . . 187

10

8.5 Podsumowanie . . . . . . . . . . . . . . . . . . . . . . . . . . 187

9 Wspomaganie decyzji przy wykorzystaniu agentów 189

9.1 Preferencje i uzytecznosc . . . . . . . . . . . . . . . . . . . . . 189

9.1.1 Teoria preferencji . . . . . . . . . . . . . . . . . . . . . 189

9.1.2 Funkcja uzytecznosci . . . . . . . . . . . . . . . . . . . 192

9.2 Negocjacje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

9.2.1 Wybrane protokoły prowadzenia negocjacji . . . . . . 194

9.2.2 Rodzaje ustepstw w negocjacjach wielostronnych . . . 195

9.2.3 Strategie negocjacyjne . . . . . . . . . . . . . . . . . . 196

9.2.4 Zastosowanie negocjacji . . . . . . . . . . . . . . . . . 198

9.3 Głosowanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

9.3.1 Głosowanie wiekszosciowe . . . . . . . . . . . . . . . . 199

9.3.2 Kryterium Condorceta . . . . . . . . . . . . . . . . . . 199

9.3.3 Głosowanie kumulatywne . . . . . . . . . . . . . . . . 200

9.3.4 Głosowanie aprobujace . . . . . . . . . . . . . . . . . . 200

9.3.5 Głosowanie wiekszosciowe z eliminacja . . . . . . . . . 200

9.3.6 Głosowanie Bordy . . . . . . . . . . . . . . . . . . . . 200

9.3.7 Głosowanie Nansona . . . . . . . . . . . . . . . . . . . 200

9.3.8 Kryterium Smitha . . . . . . . . . . . . . . . . . . . . 201

9.3.9 Głosowanie metoda Shulzego . . . . . . . . . . . . . . 201

9.3.10 Zastosowania . . . . . . . . . . . . . . . . . . . . . . . 202

9.4 Gry niekooperacyjne . . . . . . . . . . . . . . . . . . . . . . . 202

9.4.1 Postacie gier . . . . . . . . . . . . . . . . . . . . . . . 203

9.4.2 Gry przeciwko naturze . . . . . . . . . . . . . . . . . . 205

9.4.3 Gry dwuosobowe . . . . . . . . . . . . . . . . . . . . . 208

9.4.4 Gra o sumie niezerowej . . . . . . . . . . . . . . . . . 210

9.4.5 Rozwiazanie gry . . . . . . . . . . . . . . . . . . . . . 213

9.4.6 Zastosowania . . . . . . . . . . . . . . . . . . . . . . . 215

9.5 Gry kooperacyjne . . . . . . . . . . . . . . . . . . . . . . . . . 215

9.5.1 Formowanie koalicji . . . . . . . . . . . . . . . . . . . 217

9.5.2 Przeszukiwanie grafu struktur koalicji . . . . . . . . . 218

9.5.3 Wybrane własnosci gier koalicyjnych . . . . . . . . . . 219

9.5.4 Rozdział wartosci wewnatrz wielkiej koalicji . . . . . . 220

9.5.5 Rdzen . . . . . . . . . . . . . . . . . . . . . . . . . . . 221

9.5.6 Zastosowania . . . . . . . . . . . . . . . . . . . . . . . 224

9.6 Programowanie zorientowane rynkowo . . . . . . . . . . . . . 224

9.6.1 Model danych rynkowych M3 . . . . . . . . . . . . . . 225

9.6.2 Złozonosc towarów wyrazanych w ofertach handlu

wielotowarowego . . . . . . . . . . . . . . . . . . . . . 227

9.6.3 Programowanie zorientowane rynkowo z dodatkowymi

ograniczeniami . . . . . . . . . . . . . . . . . . . . 229

11

9.6.4 Zastosowania . . . . . . . . . . . . . . . . . . . . . . . 230

9.7 Mechanizmy rynkowe . . . . . . . . . . . . . . . . . . . . . . . 230

9.7.1 Teoria mechanizmów rynkowych . . . . . . . . . . . . 231

9.7.2 Wybrane własnosci mechanizmu . . . . . . . . . . . . 233

9.7.3 Zastosowania . . . . . . . . . . . . . . . . . . . . . . . 235

9.8 Podsumowanie . . . . . . . . . . . . . . . . . . . . . . . . . . 236

10 Podsumowanie 237

Skorowidz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

Spis rysunków . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

Spis tabel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

Bibliografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248

12