Intelligente agenter

Den autonome ferja over fjorden ser verden gjennom radar, kamera og GPS, og påvirker den med propeller, ror og rampe. Den er en agent: noe som oppfatter omgivelsene gjennom sensorer og handler på dem gjennom aktuatorer. Det sensorene leverer på ett tidspunkt, er en persepsjon (percept), og hele historikken av slike persepsjoner er agentens persepsjonssekvens (percept sequence).

Begrepet er bredt med vilje. Et menneske har øyne og ører som sensorer og hender og stemme som aktuatorer. Et program som handler i en nettbutikk, har nettsider og meldinger som persepsjoner og klikk og bestillinger som handlinger. Agentbegrepet er et verktøy for å analysere systemer, ikke en grense mellom det som er KI og det som ikke er det: en dørklokke kan også beskrives som en agent, men det gir lite innsikt.

Atferden kan beskrives utenfra som en agentfunksjon (agent function): en avbildning fra hver mulig persepsjonssekvens til en handling, ƒagentfunksjonen:

Agentfunksjonen er et matematisk objekt. Det som faktisk kjører om bord, er et agentprogram (agent program), koden som implementerer funksjonen på agentens maskinvare. Programmet får bare den nåværende persepsjonen inn; vil det bruke historikken, må det lagre den selv.

Den enkleste implementasjonen er en tabell med én rad per persepsjonssekvens. Med $|\mathcal{P}|$ mulige persepsjoner per tidssteg og levetid $T$ trengs ƒrader i en tabelldrevet agent:

rader. Et kamera med bare 100 piksler i gråtoner har $256^{100}$, over $10^{240}$, mulige bilder, langt flere enn de omtrent $10^{80}$ atomene i det synlige universet, og det er bare for ett tidssteg.

Utfordringen i KI er derfor å skrive små programmer som gir fornuftig atferd uten en slik tabell, slik et navigasjonsprogram finner ruter uten å ha lagret en ferdig rute for hvert par av adresser.

antall_persepsjoner = 4  # @param 2..10
levetid = 6  # @param 1..12

# Én rad per mulig persepsjonssekvens med lengde 1, 2, ..., levetid
rader = sum(antall_persepsjoner ** t for t in range(1, levetid + 1))
nye = antall_persepsjoner ** levetid  # sekvensene med full lengde


def med_mellomrom(n):
    return f"{n:,}".replace(",", " ")


print(f"Rader i agenttabellen: {med_mellomrom(rader)}")
print(f"Rader per ny tidsenhet: {med_mellomrom(nye)}")

Ta en klorautomat i en svømmehall. Den skal holde nok klor i vannet til at bakterier ikke overlever, men ikke så mye at badegjestene får sviende øyne. Hvordan avgjør vi om den gjør jobben godt? Automatens egen logg sier hva den gjorde, og den kan godt melde at alt gikk fint. Det som avgjør, er likevel vannet, altså prøvene vi tar av bassenget gjennom dagen. En slik målestokk kalles et ytelsesmål (performance measure). Designeren velger den, og den gir forløpet i miljøet en score uansett hvilke handlinger agenten brukte for å komme dit.

Med et ytelsesmål på plass kan vi si hva det vil si at en agent er rasjonell:

Definisjonen er en regel for å dømme agenten rettferdig. Vi vurderer hvert valg ut fra det agenten hadde for hånden da den valgte: målingene så langt, det den visste fra før, og handlingene den faktisk kunne velge mellom, alt holdt opp mot ytelsesmålet. Rasjonalitet (rationality) gjelder altså valget, ikke hvordan det gikk. Doserer automaten fornuftig ut fra målingene, og en skoleklasse hopper uti minuttet etter, har den ikke handlet irrasjonelt fordi nivået falt under grensen. Å kreve noe annet er å kreve at agenten er allvitende og kjenner utfallet på forhånd, og det kan ingen agent være.

Rettferdigheten går også den andre veien. Kunne agenten lett ha skaffet seg et bedre grunnlag, regnes det mot den at den lot være. Skal ferja legge fra kai i tett tåke, koster et ekstra radarsveip nesten ingenting og kan avsløre en kajakk i leia. Å kjøre uten å sveipe er irrasjonelt, også de gangene leia er tom. Å hente inn informasjon før man handler, hører derfor med til det å handle rasjonelt.

Det agenten «visste fra før», har den fra designeren, og det kan være feil. Klorautomaten leveres med en innstilling for en rolig formiddag. Om kvelden er hallen full av svømmetrening, kloret forsvinner mye raskere, og en automat som stoler blindt på innstillingen, kommer for sent med dosene hver eneste kveld. En automat som bruker målingene til å lære hvor fort kloret faktisk forsvinner ved ulike besøkstall, blir bedre uke for uke. Hvor mye atferden bygger på det agenten selv oppfatter og lærer, framfor det den fikk med fra fabrikken, kalles autonomi (autonomy).

Før vi designer en agent, beskriver vi oppgavemiljøet (task environment). En PEAS-beskrivelse har fire deler: ytelsesmål, miljø, aktuatorer og sensorer. Miljøet er omgivelsene agenten virker i, med objektene og egenskapene der, ikke selve oppgaven. Aktuatorene er det agenten handler med, og sensorene det den oppfatter med.

Tabellen viser to ting som går igjen i gode PEAS-beskrivelser. Ytelsesmålet har ofte flere deler som trekker hver sin vei: ferja skal være presis, men ikke på bekostning av sikkerheten, og den skal spare energi uten at passasjerene blir sjøsyke. Og beskrivelsen er konkret. «Sensorer: radar og kamera» er nyttig, mens «den ser» ikke er det. Skill også mellom en sensor og en persepsjon: GPS-mottakeren er sensoren, og posisjonen den leverer i et gitt øyeblikk, er persepsjonen.

Et ytelsesmål med flere deler må vekte dem mot hverandre, og vektene er et designvalg, ikke noe agenten finner ut selv. Miljøet trenger heller ikke være fysisk. En agent som svarer på kundehenvendelser i en nettbutikk, har meldinger og ordrehistorikk som miljø, tekstsvar og endringer i bestillingssystemet som handlinger og innkommende meldinger som persepsjoner. Slike programvareagenter kan ha like krevende miljøer som roboter, fordi kundene er mange og uforutsigbare.

Oppgavemiljøer varierer langs sju egenskaper, og hver egenskap sier noe om hvilken agent som trengs.

• •Fullt og delvis observerbart (fully / partially observable): Gir sensorene agenten alt som er relevant for valget? Ferja ser ikke hva som skjuler seg bak en holme, så miljøet dens er delvis observerbart.
• •Én agent og fleragent (single-agent / multiagent): Finnes det andre agenter som optimerer et mål som avhenger av vår agent? Andre båter i leia gjør ferjas miljø til et fleragentmiljø, med både samarbeid og konkurranse om plassen. I konkurranse kan uforutsigbar atferd være rasjonelt, mens samarbeid ofte krever kommunikasjon.
• •Deterministisk, ikke-deterministisk og stokastisk (deterministic / nondeterministic / stochastic): Er neste tilstand bestemt av tilstanden og handlingen? Kjenner vi sannsynlighetene for utfallene, er miljøet stokastisk; kjenner vi bare hvilke utfall som er mulige, er det ikke-deterministisk.
• •Episodisk og sekvensiell (episodic / sequential): Påvirker et valg senere valg? Å sortere én og én flaske er episodisk, mens hvert grep i et sudoku endrer hva som er lurt senere.

• •Statisk, dynamisk og semidynamisk (static / dynamic / semidynamic): Endrer miljøet seg mens agenten tenker? Et sudoku er statisk. Står miljøet stille, men poengsummen avhenger av hvor lang tid agenten bruker, kalles det semidynamisk.
• •Diskret og kontinuerlig (discrete / continuous): Har miljøet endelig mange tilstander og handlinger, eller varierer de kontinuerlig, som fart og kurs?
• •Kjent og ukjent miljø (known / unknown): Vet agenten hva handlingene fører til? Et kjent miljø kan likevel være delvis observerbart, som et kortspill der reglene er kjent, men kortene skjult.

Legg merke til hvor ferja havner: på den krevende siden av seks av de sju egenskapene. Bare fysikken er kjent. Sudokuløseren havner på den enkle siden av alle sju, og det forklarer mye av hvorfor datamaskiner har løst sudoku i flere tiår, mens autonome ferjer fortsatt er et forskningsfelt.

Egenskapene avhenger også av hvordan vi avgrenser oppgaven. Ser vi på hver overfart som en episode, er ferjeruta episodisk mellom overfartene, men sekvensiell innenfor hver av dem. Svar derfor alltid med en begrunnelse som viser hvilken avgrensning du har valgt. Det er begrunnelsen som gir poeng, ikke ordet alene.

De fire programtypene kan leses som fire svar på samme spørsmål: hva må programmet ha tilgang til for å velge godt? Hver type legger til én ting.

Bare det den ser nå. En enkel refleksagent (simple reflex agent) er en samling regler fra persepsjon til handling, som «viser måleren under 4, doser». Den trenger verken minne eller modell og reagerer raskt. Reglene holder så lenge det sensorene viser akkurat nå, er nok til å avgjøre hva som er lurt. For klorautomaten holder de ikke. Måleren sitter et stykke ut i sirkulasjonen og viser vannet slik det var for et par minutter siden. Rett etter en dose viser den fortsatt for lite klor, og refleksagenten doserer igjen.

Det den ser, pluss det den har holdt rede på. En modellbasert refleksagent (model-based reflex agent) fører et internt regnskap over det den ikke kan se direkte. To modeller holder regnskapet oppdatert. Overgangsmodellen sier hva tiden og handlingene gjør med verden: en dose hever nivået, og badegjestene bruker opp litt klor hvert minutt. Sensormodellen sier hvordan verden viser seg i persepsjonene: måleren ligger noen minutter bak. Regnskapet blir et anslag og aldri en sikker sannhet, men det er bedre enn det måleren gir alene. Den modellbaserte automaten under legger dosene måleren ennå ikke har sett, til målingen og trekker fra forventet forbruk.

Et mål å styre mot. Reglene i de to første typene sier hva som skal gjøres i hver situasjon. En målbasert agent (goal-based agent) får i stedet vite hvor den skal, for eksempel «ferja ligger ved kai 2», og finner handlingene selv med søk eller planlegging. Prisen er regnetid, fordi agenten må prøve ut handlingsrekker i hodet før den gjør noe. Gevinsten er at et nytt mål ikke krever nye regler: skal ferja til kai 3 i stedet, er det samme program med et annet mål. Det er denne typen agenter neste kapittel handler om.

En skala i stedet for ja eller nei. Et mål er enten nådd eller ikke, men av alle rutene til kai 2 er noen raskere, tryggere eller billigere enn andre. En nyttebasert agent (utility-based agent) gir hvert utfall et tall med en nyttefunksjon $U$ og velger handlingen med høyest forventet nytte, ƒnyttebasert valg:

Med tall kan agenten bytte litt rutetid mot mindre energi, og den kan regne med at vinden kanskje snur. Hold likevel nyttefunksjonen og ytelsesmålet fra hverandre. Ytelsesmålet eies av designeren og brukes til å bedømme agenten utenfra. Nyttefunksjonen sitter inne i agenten og brukes til å velge. Designeren skriver nyttefunksjonen for å peke mot ytelsesmålet, men ingenting garanterer at de to stemmer. Spriker de, jager agenten feil ting, slik verdijusteringsproblemet viser.

Alle de fire typene kan bli bedre med erfaring. En lærende agent (learning agent) har fire deler. Ytelseselementet er agentprogrammet som velger handlinger. Kritikeren vurderer hvordan det gikk, målt mot en fast ytelsesstandard utenfor agenten. Læringselementet bruker vurderingen til å forbedre ytelseselementet. Problemgeneratoren foreslår av og til handlinger som er nye, for å samle erfaring agenten ellers ikke ville fått, selv om de kan være dårligere på kort sikt.

Ta ferja som eksempel. Ytelseselementet legger til kai med en bestemt innseilingsvinkel. Kritikeren registrerer at ferja traff kaia hardt, målt mot en standard om at anløpet skal være mykt. Læringselementet justerer regelen for innseilingen, og problemgeneratoren foreslår av og til en annen vinkel for å finne ut om den er bedre.

Hvordan agenten beskriver tilstander, avgjør hvilke algoritmer den kan bruke, og vi skiller mellom tre nivåer: atomisk, faktorisert og strukturert representasjon (atomic / factored / structured representation). Med en atomisk representasjon er en tilstand bare et navn uten indre struktur; søkealgoritmene i neste kapittel bruker det. Med en faktorisert representasjon er tilstanden et sett variabler med verdier, slik begrensningsproblemer og planlegging bruker. Med en strukturert representasjon består tilstanden av objekter og relasjoner, slik førsteordens logikk og språk krever.

Mer uttrykksfulle representasjoner kan beskrive mer med mindre tekst, men resonnering og læring blir mer krevende. Prisen gjelder også den andre veien: i en atomisk representasjon er to tilstander enten like eller helt ulike, så agenten kan ikke generalisere fra én tilstand til en som ligner. En representasjon kan også være lokal, der hvert begrep har sin egen plass i minnet, eller distribuert, der et begrep er et mønster over mange enheter, slik nevrale nett lagrer kunnskap. Distribuerte representasjoner tåler støy bedre. Kapitlene videre beveger seg fra atomiske mot strukturerte representasjoner.