Artificiell intelligens del 1 – Intelligenta agenter

14 augusti, 2008 kl 12:59 av Jon i AI | 3 kommentarer

Introduktion

I våras läste jag en kurs i artificiell intelligens. Tentan gick bra men nu känner jag att jag vill repetera lite. Det tänkte jag göra genom att skriva en liten AI-skola. Jag sammanfattar grunderna i AI från boken “Artificial Intelligence – A modern approach” av Stuart Russel och Peter Norvig. Den boken tycker jag är väldigt läsvärd. Tyvärr är den lite väl pratig ibland vilket bidrar till bokens rejäla tjocklek.

I boken pratar man ofta om en intelligent och autonom taxi, men jag har istället valt att relatera till den helikopter som jag och en vän utvecklar. Fel i sammanfattningen kan självklart förekomma, påpeka gärna detta om du upptäcker några. Då kör vi igång!

Intelligenta agenter

Vilka sorters agenter och omgivningar finns det, och vad gör en agent rationell?

Innan jag kan gå in på de lite roligare delarna med exempel på olika slags agenter, måste jag förklara grunderna lite kortfattat. En agent kan vara många olika saker. Gemensamt för alla agenter är att de har sensorer för att uppfatta sin omgivning och pådrivare (actuators) för att kunna agera i sin omgivning.

Det agenten uppfattar vid en viss tid kallas dess percept. En agents perceptsekvens består av allt den uppfattat hittills.

Rationella agenter

Man kan helt enkelt säga att en rationell agent är en agent som alltid gör rätt val utifrån vad den hittils sett och lärt sig av sin omgivning och utifrån dess inbyggda kunskaper. Men vad är då rätt? För att kunna svara på det måste man definiera och ge sin agent ett eller flera prestandamätvärden. Då kan agenten vara rationell genom att sträva mot att maximera dessa mätvärden. En bevakningshelikopter kan t.ex. få i uppgift att hitta så många skadade personer som möjligt i ett katastrofområde.

Sammanfattningsvis, hurvida en agent är rationell vid en viss tidpunkt beror på:

• Prestandamätvärdena som definierar vad som är framgång
• Vad agenten har för perceptsekvens
• Vad agenten kan göra för något
• Vad agenten har för förkunskaper

Uppgiftsomgivning

När man börjar utveckla sin intelligenta agent bör man först specificera en uppgiftsomgivning. I denna ska man ha med prestanda-mätvärden, omgivningen som agenten ska operera i, agentens pådrivare och dess sensorer.

Nu får jag äntligen tillfälle att ta upp helikoptern igen. Vi fortsätter med räddningssenariet, där helikoptern ska se och platsbestämma så många skadade personer som möjligt efter t.ex. en tsunami.

Typ av agent: Helikopter av typen quadrotor.
Prestanda-mätvärden: Hitta så många skadade personer som möjligt per tidsenhet.
Omgivning: Strand med både skadade och inte skadade personer. Starka vindar kan förekomma, träd och byggnadsrester kan stå i vägen. Området bör också avgränsas.
Pådrivare: Kontroll över de fyra motorerna genom styrkommandon såsom upp, ner, höger, vänster, frammåt och bakåt i olika hastigheter. Liten högtalare, dioder och 3G-länk som överför information till personal på marken.
Sensorer: GPS, kompass, lufttryckssensor (höjdsensor), avståndsmätare i flera riktningar, batterispänningsmätare och videokamera.

Omgivningen bör specifieras utifrån ett antal begrepp:

Fullt observerbar vs partiellt observerbar

Detta förklarar nästan sig självt. Om en agents sensorer ger den all tänkbar information om hela dess omgivning hela tiden, då är omgivningen fullt observerbar. Om den är partiellt observerbar kan roboten bara se en del av dess omgivning åt gången.

Deterministisk vs stokastisk

Om omgivningens utseende i nästa situation endast beror av den nuvarnade situationen och agentens handling i denna, säger man att omgivningen är deterministisk. I en stokastisk omgivning däremot så kan lite vad som helst hända, utan att agenten har kontroll på detta genom bara sina egna handlingar.

Episodisk vs sekventiell

I en episodisk omgivning beror inte den nuvarande situiationen av den förra. Ett exempel är t.ex. en besiktningsrobot. Hurvida den nuvarande bilen ska bli godkänd eller inte beror där inte på vad den förra bilen fick för omdöme. Men i en sekventiell omgivning kan robotens agerande i en situiation påverka dess agerande i alla kommande situationer.

Statisk vs dynamisk

I en statisk omgivning ändras inget föräns roboten gör något. Den behöver alltså inte titta på sin omgivning medans den bestämmer sig för något. I en dynamisk omgivning däremot så måste roboten hela tiden ha koll på sin omgivning eftersom saker kan förändras hela tiden.

Sådär, då kan jag göra en liten sammanställning över vår tänkta helikopterns omgivning. Den är partiellt observerbar eftersom roboten knappast kan ha koll på allt samtidigt, den är stokastisk eftersom lite vad som helst kan hända utan att helikoptern har koll på detta, den är sekventiell eftersom tidigare kunskaper och ageranden behöver vägas in i framtida beslut och den är dynamisk eftersom saker ändras kontinuerligt. En rätt klurig omgivning, med andra ord!

En agents struktur

Det finns många sorters agenter. Vi har reflex-agenten, den något bättre modellbaserade reflex-agenten (model-based reflex agent), den målbaserade agenten (goal-based agent) och nytto-agenten (utility-based agent). Alla agenter kan dessutom vara lärande agenter.

Reflex-agenten

Den enklaste sortens agent bestämmer vad den ska göra enbart utifrån dess nuvarande percept. T.ex: om en person ligger ner på marken nedanför, ta en bild och spara de nuvarande gps-koordinaterna. Detta kan vi sammanfatta i en tillstånds-handling regel (condition-action rule):

om person-ligger-ner-på-marken-nedanför då ta-en-bild-och-spara-gps-koordinater

Detta kan enklare kallas endast en regel.

Alltså, givet ett percept bestämmer agenten vad den är i för situation. Denna situation slås upp i en tillstånds-handling regeltabell. Vi får ut en regel. Ur denna regel tar vi ut handlingen och returnerar denna. Inga konstigheter, men snart blir det intressantare.

Fördel: Enkel att konstruera.
Nackdelar: Kan fastna i oändliga loopar. Nuvarande percept räcker inte alltid för att ta bra beslut.

Modellbaserad reflex-agent

Skillanden mot reflex-agenten är att denna agent kontinuerligt uppdaterar ett internt tillstånd. Detta interna tillstånd håller reda på utseendet hos de delar av världen som agenten inte ser för tillfället. Tillståndet beror på agentens percept-sekvens. Genom att hela tiden jämföra nya percept mot detta tillstånd kan agenten också avgöra vad som ändrats sedan förra sensor-avläsningen.

För att uppdatera detta tillstånd behöver agenten två sorters kunskaper. Dels måste den veta hur världen utvecklas (t.ex: om en annan helikopter plötsligt synts till bakom helikoptern i föregående tillstånd så är det troligt att denna kommit närmare i nuvarande tillstånd). Vidare måste den veta hur dess egna handlingar påverkar världen. Om jag kör frammåt mot ett träd, så är jag troligen närmare trädet om några sekunder. Dessa två kunskaper kallas en modell över världen, och är alltså det som gett denna agent dess namn.

Fördel: Håller reda på hur välden utvecklas och kommer ihåg hur utforskade delar ser ut.

Målbaserad agent

En målbaserad agent har helt enkelt ett mål med sin existens. Vilket kan vara trevligt. Helikoptern bör inte bara sticka iväg planlöst åt ett håll ut i obygden utan hålla sig där den hittar skadade personer. Vi behöver alltså en uppsättning delmål, som alla är kombinerade med en handling. Efter att agenten tagit reda på hur världen se ut nu så funderar den ut hur världen kommer se ut om den gör vissa handlingar. Hur kommer det vara om jag kör frammåt en meter, hur kommer det vara om jag åker uppåt en meter? När denna interna simulering är klar kan agenten jämföra alla resultat med sina mål. När den hittar ett mål som motsvarar ett möjligt nästa-utseende hos världen så slår den till och utför den handling som detta mål är bundet till.

Exempel
Delmålsnamn: Hitta en skadad
Handling: Ta en bild och spara positionen

Om agenten i sin simulering når resultatet “hitta en skadad” så gör den mostvarande handling och alla blir nöjda. Detta påminner om hur reflex-agenten bestämmer sig för handlingar (tillstånds-handling reglerna), men är mer målinriktat och innefattar intern simulerings-beräkning av nästa tillstånd.

Fördel: Flexibel

Nytto-agenten

Då var vi framme vid den sista lilla agenten. Vad har vi kvar att förbättra? Jo, det är ju så att även om vår helikopter t.ex. kan åka hem till laddningsstationen på många olika sätt, och därmed uppnå sitt delmål att ladda batterierna, så är en del sätt bättre än andra. Fågelvägen är bättre än en rejäl avstickare in över inlandet, om batteriindikatorn blinkar ilsket rött. Istället för att bara säga “bra” och “dåligt” så inför man fler steg. Man jämför olika världs-situationer och om ett sådant “state” är bättre än ett annat så har det större nytta (utility) för agenten.

Här använder man en nytto-funktion. Denna funktion förbinder en världs-situation (eller en serie av sådana som t.ex. uppnår ett mål) med ett värde. Ju högre värde, desto gladare robot.

Lärande agenter

Lärande agenter är ett stooort område som kräver ett kapitel för sig. Kanske kommer det i en framtida del av AI-skolan.

Källa: Artificial Intelligence – A modern Approach – Second Edition av Stuart J. Russell och Peter Norvig 2003, 1995

Relaterade inlägg:

1. Enorma truckar ska göras intelligenta
2. Svenska robotar del 1: Spring, Dasher, spring!