Samenvatting Hoorcollege 17/10/2002 - Kennis En Redeneren
SAMENVATTING HOORCOLLEGE 17/10/2002
Daniel Kucharski, e-mail
[email protected] Jeroen Schaeken, e-mail
[email protected] Matti Roloux, e-mail
[email protected] Sara De Decker, e-mail
[email protected] Vicky De Neyer, e-mail
[email protected] Wouter Van den Broeck, e-mail mailto:
[email protected]
Een agent is een systeen dat quasi-autonoom in een omgeving (= environment) 'leeft' en een bepaald doel (= goal) nastreeft. De agent interageert met zijn omgeving d.m.v. waarnemingen (= perceptions) enerzijds en handelingen (= actions) anderzijds.
PAGE
(Perception, Actions, Goals, Environment)
Environment Agent Perception
Actions Goals
Opmerking: wij ‘mensen’ zijn volgens deze definitie dus ook ‘agents’, maar uiteraard betreft het hier vooral artefacten zoals robots of stukken ‘slimme’ software die bijvoorbeeld op het internet leven, en de mens bijstaan in allerhande welomschreven taken.
! Waarnemen is het opnemen van ‘input’. Wij - fleshware-agents - gebruiken hiervoor bijvoorbeeld onze zes zintuigen. Robots (hardware-agents) bedienen zich van allerhande sensoren, terwijl software-agents het o.a. doen met het opvragen van informatie uit databanken en dergelijke.
Pagina 1/6
Samenvatting Hoorcollege 17/10/2002 - Kennis En Redeneren
Maar waarnemen is meer dan dat. Wat we bijvoorbeeld zien (met onze ogen) is niet noodzakelijk wat we waarnemen (met ons brein). Bv. blinde vlek; daar waar de zenuwbundel - die het oog met het brein verbind in het oog ‘geplugd’ is ‘zien’ we eigenlijks niets, maar we lijken er wel te ‘zien’ omdat het brein omliggende patronen laat doorlopen in deze ‘blinde’ vlek. De perceptiemogelijkheden waarover hard- of software-agents beschikken zijn echter aanzienlijk beperkter dan waar vele biologische entiteiten over beschikken. En zelfs voor deze laatsten is het niet mogelijk alles wat er om hen heen in de analoge wereld gebeurt continue en gedetaileerd te registreren.
! " Agents zijn over het algemeen niet ‘helderziend’, i.e. ze kunnen de gevolgen/resultaten van acties niet voorzien. Soms gaat dit wel, bijvoorbeeld bij schaakcomputers; omdat deze in een discrete wereld opereren, waarin het aantal mogelijke acties (relatief) sterk gelimiteerd is en toeval niet bestaat. Maar meestal ontbreekt het hun aan ervaring, en/of is inductie niet mogelijk wegens; intrinsiek niet induceerbaar en/of door een gebrekkige kennis/perceptie van de relevante factoren in de omgeving. M.a.w: feilloosheid bestaat niet.
" Zonder doel zou een agent natuurlijk weinig nut hebben, misschien vandaar dat de ‘humagents’ zichzelf al eeuwenlang opgescheept zien met existentiele vragen? Het bereiken van een goal kan echter zeer complex zijn: • • •
Meerdere (sub)goals waaraan tegelijk voldaan moeten worden. Tegenstrijdigheden (conflicting constraints). Onverwachte, al dan niet toevalige problemen die 'onderweg' opduiken.
Om te meten of een agent goed bezig is (dit wil zeggen: of hij dichter bij zijn doel komt) moet er hiervoor een soort maatstaf worden opgesteld: de performance measure (PM). Deze measure is handig bij het evalueren van vorige acties, en kan aldus bepalend zijn bij het maken van de keuzes m.b.t. toekomstige handelingen. Men zegt dat een agent rationeel is als zijn acties een gunstige invloed hebben op de PM.
#! De agent werkt in de omgeving en maakt er ook deel van uit => veranderingen in de omgeving zorgen voor veranderingen aan de agent. Eigenschappen van een omgeving: • • • • •
$
Toegankelijk: Deterministisch: Episodisch: Statisch: Discreet:
%
&'$
heeft de agent een zicht op de hele omgeving? speelt toeval een rol in de wereld? hebben vorige handelingen invloed op de huidige handeling? verandert de wereld tijdens de uitvoering van een handeling? is de wereld in stukjes opgedeeld of continu?
!( ! Mens
A
Alles wat de mens waarneemt met zijn zintuigen Alles wat de mens doet
G
Zie filosofie
P
Robottaxi
Waarnemingen met sensoren, camera's snelheidsmeters, ... Passagier oppikken, linksaf slaan, stoppen voor rood licht, portier openen, entertainen,... Passagier van A naar B brengen. Maar: zo
Pagina 2/6
Samenvatting Hoorcollege 17/10/2002 - Kennis En Redeneren
Mens
Robottaxi
zuinig, winstgevend, veilig, ... mogelijk. Bovendien is de tevredenheid van de klant ook belangrijk voor deze agents. Stad, stratenplan, verkeersregels, ander verkeer, ...
De leefwereld van een persoon
E
) • • •
%
*
"
Agent is meestal niet alwetend. Hij heeft geen volledig zicht op zijn omgeving. Agents is niet helderziend: hij kan meestal niet weten wat er gebeurt na een bepaalde actie. Agent is niet perfect, hij kan ook fouten maken.
$
+$
+ , Perception
Actions
Goals Decision Making
Aan de hand van zijn waarnemingen en doelstellingen moet de agent op een magistructurele manier zien te beslissingen wat de meest geschikte volgende actie zal zijn. De vraag is natuurlijk hoe men deze ‘decision making’ tot stand kan brengen in een artificieel systeem.
-
.
%
Hierbij worden waarnemingen (gecombineerd met interne toestanden) gemapt op acties. Concreet wordt er ‘simpelweg’ een tabel opgesteld met alle mogelijke combinaties en welke acties er respectievelijk op moeten volgen.
% Voor elk mogelijke perceptie dient op voorhand een regel voorzien te zijn in de tabel. • Combinatorisch explosief, i.e. het aantal regels groeit exponentieel in verhouding tot het aantal mogelijk waarnemingen en interne toestanden. • Doordat een omgeving in de meeste gevallen dynamisch is, zouden er voor elke nieuwe situatie regels moeten worden toegevoegd en alle vorige regels worden geüpdate zodat ze bekend zijn met het nieuwe aspect. De tabel met regels zal dus al snel verouderd zijn.
/
""!
Een programma dat dynamisch de ‘regels’ kan opstellen en aanpassen: een Kennisgerichte Agent.
Pagina 3/6
Samenvatting Hoorcollege 17/10/2002 - Kennis En Redeneren
,0
1
/
-
2
De agent beslist ‘zelfstandig’ welk zijn volgende handeling/actie zal zijn door middel van een soort denkproces. Zulk process omvat (minstens) de volgende onderdelen: • Vooreerst dienen de agents voorzien te zijn van een interne presentatie van hun omgeving. Deze interne representatie vormt een handelbaar model waarmee het denkproces kan werken. • Nieuwe waarneming dienen te worden verwerkt in de interne representatie. • Decision making; het analyseren van de huidige toestand van het model aan de hand van de goals en de performance measure, en het daaruit laten voortvloeien van ‘conclusies’. • Aktie, de juiste handeling triggeren die ‘logischerwijze’ volgt op de conclusie.
3
&
"
De kennis waaruit de interne representatie bestaat, i.e. het hart van een kennisgerichte agent, is over het algemeen bevat in een de Knowledge Base (KB). Deze kan bijvoorbeeld concreet bestaan uit een verzameling ‘rules’ en ‘assertions’, cfr. expert-systeem. De in een KB bevatte kennis is meestal heel domein specifiek, i.e. beperkt zich in scope tot het direct relevante met betrekking tot de doelstellingen. Hierdoor zijn zulke knowledge bases dus enkel ‘zinvol’ voor de respectievelijke agents.
4
!
Een inference engine gebruikt een knowledge base om tot ‘conclusies’ te komen, maar is op zichzelf domein onafhankelijk. Hierdoor kan deze worden ingezet in uiteenlopende domeinen, mits er een daarop voorziene knowledge base voorhande is. Deze regels van de knowledge base kunnen worden opgevraagd door het ASK-command en geüpdate door het TELL-command.
!#
."
We onderscheiden in zulke kennisgerichte agents twee fundamentele niveaus: •
Kennisniveau of Epistemologie (=wetenschap over het weten) Op dit niveau behandelt men de functionaliteit op abstracte wijze.
•
Implementatie niveau: De vertaling van de abstracte methodologie naar een concrete implementatie.
.. !( Natuurlijke taal is als basis voor de kennis representatie en behandeling niet werkbaar omdat deze taal dubbelzinnig en ambigue is. Natuurlijke taal is ‘ontworpen’ met het oog op expressie. Als kennis-dragend vehicel voor ‘logische’ activiteiten schiet het echter danig te kort.
Pagina 4/6
Samenvatting Hoorcollege 17/10/2002 - Kennis En Redeneren
Een programmeertaal daarentegen is al veel beter geschikt omdat het toelaat op ondubbelzinnige en volledig duidelijke wijze bepaalde handelingen te beschrijven en kennis op te slaan. Men moet in een programmeertaal echter heel expliciet zijn, waardoor het uiteindelijk ook niet geschikt is.
-
!
Is DE formele taal om kennis in voor te stellen. Logica voorziet in twee belangrijke aspecten: 1) semantiek = betekenis 2) syntax = vorm
• • • • •
! *"
Propositie logica Predikaten logica: is de propositie logica uitgebreid met kwantoren. Temporele logica: propositie + prediacate logica + tijdscomponent Waarschijnlijkheids logica: incorporeert kansrekening. Fuzzy logica: Variant van propositie logica waarbij er niet met slechts twee waarheidstoestanden (waar of vals) wordt gewerkt, maar met graden van waarheid.
/ / !"
-/ "! !
, !
Zoals vorig jaar gezien is propositielogica een formeel systeem om vanuit enkele aannamens een conclusie te trekken. Beide bestaan uit: - propositieletter: oneindig veel letters zoals p, q, r (kleine letters) - logische symbolen: dit zijn connectieven: conjuncties, disjuncties, implicaties, negaties en equivalenties. - hulpsymbolen (en) : worden gebruikt om de taal leesbaarder te maken (voor meer gedetaileerde uitleg zie cursus Grondslagen van de Informatica I )
4
! !
"! !
!
De taak van een inferentie engine gebaseerd op propositie logica, is het (geldig) afleiden van zinnen uit de proposities opgeslagen in de knowledge base.
5 •
!(
3 !(6
Aan de hand van een waarheidstabel Als de zin waar is, is ze afleidbaar. Zulke tabelen groeien echter exponentieel in verhouding tot het aantal bevatte proposities, en is hierdoor niet bruikbaar.
•
Afleidingsregels : staaltje van inferentieregels : α β, α | β α1 ∧ α2 ∧ … ∧ αi | αi …
Inferentie gebruik makende van propositielogica is echter NP-compleet: het probleem is zo complex dat het oplossen van het probleem teveel tijd neemt.
Pagina 5/6
Samenvatting Hoorcollege 17/10/2002 - Kennis En Redeneren
$
% .
."3
& & #!
"! !
!
Knowledge base bestaat uit zinnen geschreven in de propositielogica. Men gebruikt de inferentie regels om bv. te weten waar de wumpus zich bevindt als we op de stank staan.
%
%!(
% .! #
"! !
!
!" Propsotielogica kan de acties niet voorstellen. Ze is hiervoor niet krachtig genoeg. = omslachtig - Te complex want knowledge base moet een enorm aantal percepties bevatten. - Symbool moet een tijdstempel krijgen.
/
""!
Eerste Orde Logica.
Pagina 6/6