Przegląd metod tworzenia systemów wieloagentowych- mas



Pobieranie 74.88 Kb.
Data28.04.2016
Rozmiar74.88 Kb.
Wykład 11

Przegląd metod tworzenia systemów wieloagentowych- MAS


Agent-Oriented Software Engineering (AOSE)


Podział za względu na analizę systemów-zdobycie informacji potrzebnej do utworzenia agentów w fazie projektowania
1. Pozyskiwanie i strukturalizacja wyników: wzorce analizy

(Kendall & Zhao 1998)


Mapa wzorców analizy (model iteracyjny i rozwojowy)
Wzorce:

1)Pozyskiwanie celów- początkowy kontekst systemu np. system jest odpowiedzialny za tworzenie list grup studenckich, w których bierze się pod uwagę konflikty między prowadzącymi zajęcia, studentami i dostępnością sal.



  1. Przypadki celów:

2.1) tworzenie listy klas

2.2) eliminowanie konfliktów w listach



  1. Strukturalizacja przypadków celów w postaci diagramu drzewa:


Strukturalizacja przypadków celów

4) Przypadki celów jako obiekty: stabilny schemat zorientowany na cele, stabilniejszy w porównaniu z systemami opartymi na zadaniach lub czynnościach



1. Metodologia zorientowana obiektowo w fazie analizy i projektowania MAAD (Wooldridge, Jennings & Kinny 1999)

Przesłanki metodologii:



  1. agenty żądają znaczną ilość zasobów obliczeniowych, w przybliżeniu tyle, ile proces w systemie UNIX

  2. celem MAS jest maksymalizacja globalnych miar, co nie musi być optymalne z punktu widzenia komponentów systemu

  3. agenty są heterogeniczne, co oznacza, że mogą być implementowane za pomocą różnych języków i technik programowania

  4. początkowy MAS zawiera stosunkowo mało agentów



Abstrakcyjna hierarchia analizy
Organizacja składa się z dwóch modeli, zawierający te same informacje co metoda BDI


Przekształcanie analizy do projektowania

  • Usuwanie redundancji

  • Przekształcanie ról do typów agentów

  • Przekształcanie celów do ról agenta lub agentów

  • Definiowanie konwersacji między agentami

2. Podział za względu na projekt systemów-wykonanie agentów
Przesłanki projektowania agentów:

  • klasyfikowanie

  • wzorce agentów


2.1. Role i modele ról


Model wzorca roli mediatora

Np. Mediator: webserver proces,


Współpracownik: zapytanie bazy danych, połączenie do systemu


Administratora


Wzorzec biurokracji

2.2. Metodologia i technika modelowania dla systemów z agentami BDI


(Kinny, Georgeff & Rao 1996)
BDI (Belief-Desire-Intension) agenty są zdefiniowane za pomocą stanu mentalnego, sformułowane za pomocą trzech faktów:

  • zaufaniu (beliefs) czyli wiedzy o środowisku

  • pragnieniu (desires) czyli celach agentów

  • zamiarach (intension) czyli działaniach, określonych w wyniku planowania w oparciu o wiedzę o środowisku, umożliwiających spełnienie celów agentów

Metodologia opiera się na zbiorze modeli, które definiują system agentowy oparty na agentach BDI:



  • modele zewnętrznego punktu widzenia zorientowane na zamiary i reprezentujące interakcje między agentami, zawierające relacje dziedziczenia i komunikacje

  • modele wewnętrznego punktu widzenia skupione na klasie agenta specyfikujące ich BDI


Modele zewnętrznego punktu widzenia:

  • Model Agenta: reprezentujący liczbę aktualnych klientów i relacje miedzy nimi

  • Model Interakcji: reprezentują komunikację i sterowanie między klasami agentów

Metodologia tworzenia modeli zewnętrznego punktu widzenia składa się z następujących czterech kroków:

  1. Identyfikacja ról

  2. Identyfikacja odpowiedzialności i usług dla każdej roli

  3. Identyfikacja interakcji (komunikacji) dla każdej usługi

  4. Udoskonalenie hierarchii przez wprowadzenia nowych klas agentów, klas złożonych i utworzenie wystąpień nowych agentów


Modele wewnętrznego punktu widzenia:

    • Model Belief - model statyczny- zbiór informacji o środowisku

    • Model Goals - model statyczny- zbiór celów, które agent ma osiągnąć

    • Model Plans - model dynamiczny- zbiór planów (zamiarów) w celu osiągnięcia celów

Metodologia tworzenia modeli wewnętrznego punktu widzenia jest silnie oparta na paradygmatach BDI

Metodologia tworzenia modeli wewnętrznego punktu widzenia składa się z następujących dwóch kroków:



  1. Analiza znaczenia osiągnięcia celów: porządek i warunki

  2. Budowa wiedzy o systemie

2.3. Metodologia agentowo zorientowanej analizy i projektowania MAAD- faza projektowania

Faza projektowania składa się z trzech modeli:



  1. Model agenta identyfikuje typy agentów i ich wystąpienia

  2. Model usług identyfikuje usługi związane z każdym typem agenta

3) Model znajomości, który zawiera wszystkie możliwe ścieżki komunikacyjne

Metodologia łączy analizę i projektowanie używając role zdefiniowane w modelu ról utworzonym w fazie analizy. Metodologia umożliwia dużą dowolność w odwzorowaniu modelu ról w modele agentów.

Metodologia ta jest podobna do metodologii agentów BDI:


  • Praca na poziome systemu i agenta

  • Role agentów są związane z odpowiedzialnością agentów

  • Każdy proces jest przenoszony z poziomu analizy do poziomu implementacji

  • Każdy proces jest rozwijany w kolejnych iteracjach osiągając nowy poziom

2.4. Inżynieria prototypu systemu wieloagentowego MaSE (DeLoach 1999)

Cele metodologii:



  • Opracowanie kompletnej metodologii i języka do projektowania MAS

  • Umożliwienie zautomatyzowania procesu tworzenia MAS

Metodologia składa się z czterech kroków:

Prototypy MaSE


  1. Poziom projektowania dziedziny problemu: język AgMl wspomaga:

    1. identyfikację typów agentów

    2. identyfikację możliwych interakcji między agentami

    3. definiowanie protokołów koordynujących każdy typ interakcji

Tworzone są diagramy:

  • diagram agentów zawierający połączenia odpowiadające konwersacjom

  • diagram hierarchii komunikacji przedstawiający w postaci diagramu stanów konwersacje między agentami

  1. Poziom projektowania Agentów:

2.1) Odwzorowania akcji w konwersacjach do komponentów agenta

2.2) Definiowanie struktur danych w konwersacjach jako wejście i wyjście



    1. Definiowanie wewnętrznych struktur danych

  1. Poziom projektowania komponentów odpowiedzialnych za planowanie, wyszukiwanie i uczenie

  2. Projektowanie systemu na poziomie fizycznym

Technologie zorientowane agentowoprzykłady konkretnych technologii

Metodologie oparte na technologiach agentowych - właściwości

  • Technologie te nie stosują generycznego modelu analizy, co poprawiłoby poprawność tego procesu

  • Prometheus, HLIM, Cassiopeia – specyfikacja oparta na paradygmacie agentowym

  • Tropos, Gaia, SODA, Styx – analiza oparta na paradygmacie agentowym

  • Identyfikacja agentów oparta na rolach socjalnych agentów: Gaia, SODA, Styx HLIM, Cassiopeia

  • Identyfikacja agentów oparta na rolach aktorów: Tropos, Prometheus

  • Wszystkie wymienione technologie oparte są identyfikacji zstępującej agentów: z ról, aktorów, z komponentów (reprezentujących wiedzę, właściwości), z interakcji między agentami

  • Trzy aspekty tworzenia MAS – projekt wewnętrzny agenta, projekt interakcji, projekt struktury organizacji lub społeczności. Wymagania te spełniają Tropos, Gaia, Prometheus, Styx, HLIM, jednak tylko SODA wspiera społeczną strukturę MAS

  • Tropos, Prometheus, Styx i SODA wspierają identyfikację obiektów środowiska, natomiast SODA dodatkowo wspiera projektowanie interakcji między tymi obiektami,



Metodologie oparte na technologiach obiektowych - właściwości



  • Technologie te nie stosują generycznego modelu analizy, co poprawiłoby poprawność tego procesu

  • Koncepcja agenta jest wypracowana podczas fazy projektowania: wszystkie oprócz ODAC i AOAD, które już podczas analizy identyfikują agentów

  • DESIRE implementuje komponentowo sterowany proces zstępujący identyfikowania agentów, pozostałe implementują komponentowo sterowany proces wstępujący identyfikowania agentów

  • Technologie ODAC, MASB, DESIRE, AAII, AOMEM, AOAD, MASB wspierają budowę wewnętrzną i zewnętrzną agenta, natomiast MASSIVE i AOAD wspierają projektowanie struktury organizacji lub społeczności

  • Technologie ODAC, MASB i MASSIVE identyfikują obiekty środowiska, natomiast MASSIVE wspiera dodatkowo projektowanie interakcji między obiektami środowiska

  • Technologie traktują agentów jako złożone obiekty, co jest niezgodne z abstrakcyjną definicją agenta, z autonomicznymi właściwościami agenta, interakcjami oraz organizacyjną strukturą



Metodologie oparte inżynierii wiedzy - właściwości
Technologie te główny nacisk kładą na identyfikację, akwizycję i modelowanie wiedzy agenta: CommonKADS, MASCommonKADS i CoMoMAS

  • Technologie te nie stosują generycznego modelu analizy, co poprawiłoby poprawność tego procesu

  • MAS-CommonKADS identyfikują agentów podczas analizy, realizując proces wstępującej identyfikacji aktora

  • Technologie CommonKADS i CoMoMAS wspierają budowę wewnętrzną i zewnętrzną agenta, ale nie wspierają projektowania struktury organizacji lub społeczności

  • Technologie te nie wspierają identyfikacji właściwości środowiska,

W zakresie tworzenia technologii MAS dąży się do opracowania technologii, która definiuje generyczny model analizy i projektowania, niezależne od architektury




3. Baza wiedzy wspierająca projektowanie i syntezę systemów wieloagentowych
3.1. Schematy reprezentacji wiedzy
Baza jest produktem inżynierii wiedzy, która jest dyscypliną Sztucznej Inteligencji (AI).

Baza wiedzy jest reprezentowana w postaci:



  • Faktów

  • Reguł

  • Heurystyk

Schematy reprezentacji wiedzy:

  • Logiczny

  • Reguły

  • Sieci semantyczne

  • Ramki

  • Obiekty

Wzorce reprezentacji wiedzy:

  • Logiczny

  • Strukturalny

  • Proceduralny

lub

  • Deklaratywny

  • Proceduralny


3.1.1. Schemat logiczny reprezentacji wiedzy
Jest logiczna reprezentacji wiedzy oparta na języku predykatów 1-ego rzędu: rachunek zdań i kwantyfikatorów oraz teorię schematów wnioskowania
Rachunek zdań:

Zdanie (1) jest zawsze prawdziwe

Kwiat jest owocem” lub nieprawda , że kwiat jest owocem”
Zdanie (1) to formuła zw. prawem wyłączonego środka




p lub nie p

(p   p)
Formuła generująca zawsze zdania prawdziwe po podstawieniu za zmienną zdaniową(nazwową) określonej treści nazywa się prawem logicznym.


  • Jeśli (jest tak, że) jeśli grzmi, to błyska, to jeśli nie błyska, to nie grzmi”

  • jeśli (jeśli p to q) to (jeśli nie q to nie p)

  • (pq)  ( q  p) formuła zw. prawem transpozycji


Rachunek kwantyfikatorów:

W rachunku kwantyfikatorów jest uwidoczniona wewnętrzna struktura zdania prostego.

Wyróżnia się:


  • podmiot np. zmienna nazwowa x

  • oraz orzeczenie czyli predykat jako L.

Zdanie proste „Russell jest logikiem” zapisano w języku rachunku kwantyfikatorów w postaci formuły :

  • L(x) lub Lx ( x jest logikiem)

Ta formuła staje się zdaniem w wyniku:


  • podstawienia jakiejś nazwy za x

  • poprzedzenia danej formuły symbolami, reprezentującymi słówka każdy i niektóry czyli i

(3) Każdy x jest owocemx L(x)

(4) Pewien y jest owocem y L(y)



Metody wnioskowania na poziomie logicznym
1) Metody wyznaczania wartości formuł logicznych= metody dowodzenia

  • Metoda zero-jedynkowa .

  • Metoda skrócona zero-jedynkowa

2) Aksjomaty i reguły wnioskowania - ujęcie Hilberta i Bernaysa

Założenia:

  • Aksjomatami są wszystkie twierdzenia rachunku zdań oraz wszystkie formuły podpadające pod schematy:

  1. x L(x) Q(p)

  2. Q(p)  x L(x)

  • Regułami pierwotnymi wnioskowania są: reguła dołączania kwantyfikatora ogólnego DU i reguła dołączania kwantyfikatora egzystencjalnego DE

(DU) Z QL(x) wolno wnosić QxL(x) (w formule Q x nie może być zmienną wolną)

(DE) Z L(x)Q wolno wnosićx L(x)  Q



Przykłady fałszywych formuł:

  • (x<2)(x<3), wówczas z DU mamy (1<2) x(x<3) - implikacja fałszywa

  • (x<2)(x<3), wówczas x DE mamy x (x<2)(4<3) - implikacja fałszywa

  • Reguły wtórne wnioskowania:

Np. Wyprowadzenia wtórnej reguły

Z L(x) wolno wnosić x L(x)

(1) L(x) - założenie

(2) L(x) ((pp)L(x)) - prawo wyłączonego środka

(3) (pp)L(x) - prawo odrywania z (1) i (2)

(4) (pp) x L(x) - reguła dołączania DU

(5) x L(x) - prawo odrywania z pp i 4
3) Teoria schematów wnioskowania – logika przedmiotów


  • Formuły, które są prawdziwe ze względu na swoją formę logiczną, są spełniane przez wszystkie przedmioty z dowolnej (niepustej) dziedziny rozważań.

  • Są to schematy zdań prawdziwych w dowolnej dziedzinie przedmiotów.

  • Każdemu twierdzeniu logiki przedmiotowej w postaci okresu warunkowego przyporządkowany jest jednocześnie pewien schemat poprawnego wnioskowania, opisany pewną regułą.

schemat rozumowania

poprzednik (założenie)

następnik (teza)

x [P(x)  Q(x)]  x [Q(x)  S(x)]

x[P(x)S(x)]

generuje schemat wnioskowania

x [P(x)  Q(x)]

x [Q(x)  S(x)]



Przesłanka

x[P(x)S(x)]

Wniosek

Twierdzenie o dedukcji

Głosi ono, że dla udowodnienia implikacji wystarczy z jej poprzednika wyprowadzić następnik, stosując logiczne reguły wnioskowania.

Niech X będzie zbiorem jakichś formuł teorii T, zaś A formułą zamkniętą (tj. bez zmiennych wolnych) tejże teorii; jeśli z X i A, przy zastosowaniu reguł właściwych teorii T, da się wydedukować formuła B, to z X da się wydedukować implikacja AB, czyli

jeśli X, A  B, to X  AB

Jeśli X jest zbiorem pustym mamy: jeśli A  B, to  AB

Odwrotne twierdzenie o dedukcji: jeśli X  AB, to X, A B

Pozwala wyprowadzać nowe reguły dedukcyjne na podstawie udowodnionych już formuł logicznych

np. Jeśli mamy udowodnione lub przyjęte aksjomatycznie: A(A)

wówczas można przyjąć regułę: A   (A) :Z A można wydedukować  A
Dedukcja naturalna

Intencją jej jest jak najdalej idące przybliżenie logicznej teorii dowodu do rzeczywistej praktyki dowodowej w matematyce i i innych naukach.






Reguły wprowadzania


Reguły opuszczania

()






AB







AB




AB







AB







A




B




()



A




B







AB AC BC




AB




AB







C




()






A0







AA




A







A







0




A




()






AB

odpowiednik twierdzenia o dedukcji




A AB










AB




B







()






B(a)










xB(x)










xB(x)










B(a)







()





B(a)










xB(x) B(a)A







xB(x)










A



gdzie a – zmienna nie związana ( występuje w roli parametru) ,

x - zmienna związana,

O- formuła fałszywa logicznie

oraz reguła

Dowody przeprowadzane metodą dedukcji naturalnej to dowody założeniowe (kierując się regułami wyprowadza się wnioski z założeń przyjętych na próbę):


0

A






  • dowód wprost

  • dowód nie wprost.

Przykład

Dana jest formuła (pq)(rs)(pr)(qs) .

Należy udowodnić, że formuła ta jest prawem


  1. pq założenie uzyskane z reguły opuszczania ()

  2. rs ””

  3. pr ””

  4. p z reguły opuszczania () z (3)

  5. r z reguły opuszczania () z (3)

  6. q z reguły opuszczania () z (1),(4)

  7. s z reguły opuszczania () z (2),(5)

  8. qs z reguły dołączania () z (6) ,(7)

Stąd mamy: (pq)(rs)(pr)(qs) z reguły dołączania () z (1),(2),(3),(8)
3.1.2. Reguły

System reguł jest logiczną reprezentacją wiedzy, klasyczną w systemach ekspertowych.



Symptom Diagnoza

LeftHand Side(LHS) Right Hand Side(RHS)

Rule 1: If a program is mobile THEN the program is a agent

Rule 2: If an agent has goals THEN the agent is goal-based

Dane są następujące fakty: Program X is mobile and has goals

Reguły systemu dedukcji: Program X is a goal-based agent

Symptom Diagnoza1

Diagnoza1 Diagnoza2 itd

System reguł tworzy łańcuch wnioskowania.

Rozróżnia się łańcuch wnioskowania „do przodu”(LHS) oraz łańcuch wnioskowania „do tyłu”(RHS - sterowany celem).

Mechanizm wnioskowania opiera się na dwóch głównych metodach:



  • sieć wnioskowania

  • dopasowanie wzorca (dla RHS, LHS)

W systemie reguł odrzuca się ograniczenia czysto logicznych wyników.

Problemami mogą być:



  1. nieskończony łańcuch wnioskowania- utworzenie w łańcuchu wnioskowani nieskończonej pętli wnioskowania

  2. sprzeczność wiedzy- nowa reguła jest sprzeczna z poprzednią ścieżką wnioskowania

  3. nieczytelność zachowania się – pewien model reprezentacji wiedzy może prowadzić do nieczytelnego zbioru reguł


3.1.3. Sieci semantyczne

Sieć semantyczna jest strukturalną metodą reprezentacji wiedzy.

Jest to graf skierowany, reprezentujący sieć wnioskowania opartą na zbiorze reguł:


  • wierzchołki grafu stanowią obiekty zamiast faktów

  • krawędzie grafu stanowią relacje między obiektami zamiast reguł

Sieć semantyczna

Zalety sieci semantycznych: rozszerzenie reprezentacji wiedzy do zapytań, brak uzależnienia się od wnioskowania wiążącego z dziedziną problemu

Problemy: poziomy szczegółowości w powiązaniach, nieskończoność rekurencyjna powiązań, brak bezpośredniego powiązania z system wnioskowania opartego na rachunku predykatów i regułach ułatwiającego wnioskowanie.
3.1.4. Ramki

Jest to strukturalna reprezentacja wiedzy.

Generic Agent Frame

Specialization-of: PROGRAM

Generalization-of: (MOBILE-AGENT, INTERIA-AGENT)

Planner:

Range: (FORWARD-CHAINING, BACKWARD-CHAINING)



Knowledge-Store:

Range: (Database, Flat-File)

Default: Database

Security-Level:

Range: (SECRET, UNCLASSIFIED, TOP-SECRET)

If-Changed: (ERROR: No permission to change classification)

Przykład ramki dla dziedziny aplikacji Agenta



Zalety: brak uzależnienia od wnioskowania wiążącego z dziedziną problemu

Wady: brak reprezentacji wiedzy heurystycznej opartej na rachunku predykatów i regułach, ograniczenie w przystosowaniu się do różnych sytuacji lub obiektów

3.1.5. Obiekty

Proceduralna reprezentacja wiedzy oparta na obiektach rozszerza ramkę wykorzystując:

  • połączenie danych i operacji

  • dziedziczenie, polimorfizm

  • hermetyzację.

3.1.6. Hybrydowa reprezentacja wiedzy

Reprezentacja wiedzy wykorzystuje łącznie metody przedstawione w p. 3.1.1-3.1.5



  • połączenie reguł i ramki tworzące „czarną skrzynkę” wnioskującą

  • połączenie logicznej, proceduralnej i strukturalnej reprezentacji-ER

  • CKML, OML, XML

CKML- Conceptual Knowledge Marking Language- język do specyfikacji aplikacji rozszerzny do XML

XML- Xtensible Marking Language- format struktury dokumentów przekazywanych w sieci Web

OML- Ontology-Markup Language rozszerza XML do reprezentowania bazy wiedzy


  • AST – (Abstract Syntax Trees) drzewa syntaktyki abstrakcyjnej oparte na gramatyce formalnej reprezentujące XML

Przykład

Dane są: V={a, comfortable, is, near, shoes, sometimes, table, the, wear, window, women},

V’= {S, A, AN, B, C, CN, D, N},

oraz produkcje w notacji BNF:



::=

::= ||

::=
|

::= | window | women | shoes | table

::= near | sometimes

::= comfortable

::= athe

::= is | wear




©absta.pl 2016
wyślij wiadomość

    Strona główna