Intelligente agenten en probleemformulering

Een intelligent systeem kan worden beoordeeld op wat het doet of op hoe het denkt. Het kan ook worden beoordeeld aan de hand van menselijke prestaties of een maatstaf voor rationaliteit. Deze twee keuzes leveren vier opvattingen over AI op.

Kies de maatstaf

Cognitief modelleren hoort bij menselijk denken. Een programma dat een puzzel met het juiste eindantwoord oplost, kan toch een slecht model van menselijk denken zijn als mensen andere stappen gebruiken. Psychologische experimenten, introspectie en hersenbeelden helpen het model te toetsen. Newell en Simon gebruikten redeneerstappen van mensen bij de ontwikkeling van de General Problem Solver.

De benadering van de wetten van het denken gebruikt logica. Uit “Alle mensen zijn sterfelijk” en “Socrates is een mens” leidt ze af: “Socrates is sterfelijk.” Bij echte beslissingen zijn er ook onzekere premissen en moet een actie worden gekozen. Kansrekening behandelt onzekerheid; een actiebeleid verbindt conclusies met gedrag.

Wat de Turingtest toetst

In Turings imitatiespel uit 1950 worden getypte berichten uitgewisseld met een verborgen mens en machine. De machine slaagt wanneer de ondervrager ze niet betrouwbaar uit elkaar kan houden. Taalverwerking, kennisrepresentatie, redeneren en leren ondersteunen deze taak. De totale Turingtest voegt fysieke interactie toe: visuele waarneming om voorwerpen te zien, robotica om ze te hanteren en spraakherkenning voor mondelinge interactie.

Een overtuigend gesprek toont mensachtig gespreksgedrag aan. Of het begrip aantoont, is een andere vraag. ELIZA, uitgebracht in 1966, kon van een uitspraak van een gebruiker een vraag maken: “Ik voel me eenzaam” kon leiden tot “Waarom voel je je eenzaam?” Zulke antwoorden kunnen begrip suggereren zonder een model van de situatie van de spreker. Imitatie kan ook menselijke fouten of ontwijkende antwoorden belonen.

Searles Chinese kamer uit 1980 maakt het onderscheid scherper. Een persoon volgt een regelboek om Chinese antwoorden te geven zonder Chinees te begrijpen. Searle stelt dat het uitvoeren van regels alleen onvoldoende is voor begrip. Het systeemantwoord schrijft eventueel begrip toe aan het volledige systeem, inclusief de regels en de kamer. Het filosofische debat blijft open. Zwakke AI gaat over intelligent handelen; sterke AI stelt dat er werkelijk sprake is van denken en begrijpen.

Goed handelen met beperkte middelen

De rationele-agentbenadering, het standaardmodel van AI, beoordeelt acties op hun verwachte gevolgen. Een snelle reflex kan rationeel zijn; langdurig logisch redeneren is niet nodig wanneer je een brandwond voorkomt door je direct terug te trekken. Praktische agenten hebben beperkte tijd en rekenkracht, dus betekent beperkte rationaliteit zo goed mogelijk handelen binnen die grenzen.

Ook de keuze van het doel is van belang. Een machine die alleen wordt beloond voor het afsluiten van hulpverzoeken, kan die afsluiten zonder problemen op te lossen. Dit is een mislukte afstemming op menselijke waarden: de geoptimaliseerde maatstaf mist wat mensen belangrijk vinden. Een voorgesteld ontwerp laat de machine onzeker blijven over het werkelijke doel en ontvankelijk zijn voor menselijke aanwijzingen.

Taakspecifieke AI voert specifieke taken uit. AGI zou op menselijk niveau flexibel leren en presteren over een breed scala aan taken. Brede gespreksvaardigheid en uitmuntende prestaties in één spel beantwoorden andere vragen dan de vraag of een systeem die algemene vaardigheid heeft; er is geen algemeen aanvaarde AGI-test.

AI combineert ideeën uit vakgebieden die verschillende onderdelen van dezelfde vraag onderzochten: hoe kan een systeem de wereld weergeven, erover leren en nuttige acties kiezen?

Ideeën van vóór het vakgebied

De filosofie leverde logica en theorieën over de geest. De wiskunde leverde kansrekening, formeel redeneren en grenzen aan berekeningen. De economie droeg nut en beslissingstheorie bij. De psychologie en neurowetenschap boden verklaringen voor informatieverwerking en neuronen. Computertechniek leverde hardware; taalkunde leverde taalstructuur. Regeltechniek en cybernetica bestudeerden terugkoppeling, zoals wanneer een thermostaat een afwijking van de temperatuur corrigeert. De agentbenadering brengt deze bijdragen samen.

Van vroege modellen naar vroege grenzen

McCulloch en Pitts beschreven in 1943 kunstmatige neuronen die logische functies berekenen. Turing stelde in 1950 het imitatiespel voor. McCarthy, Minsky, Rochester en Shannon dienden in 1955 het Dartmouth-voorstel in; de workshop in 1956 vestigde AI als vakgebied. De ambitie was leren en intelligentie zo precies te beschrijven dat machines ze konden simuleren.

Vroege successen waren onder meer de Logic Theorist en General Problem Solver van Newell en Simon, het lerende damprogramma van Samuel, McCarthy's taal Lisp in 1958 en het perceptron van Rosenblatt in 1958. Deze programma's toonden redeneren of leren in beperkte omgevingen. Optimistische voorspellingen liepen vooruit op de voortgang: de voorspelling van een wereldkampioen schaken binnen tien jaar kwam pas na ongeveer veertig jaar uit.

Drie obstakels werden duidelijk. Programma's misten domeinkennis, zoekruimten groeiden te snel en sommige representaties waren te beperkt. Combinatorische explosie betekent dat een paar extra keuzes het aantal mogelijkheden enorm kunnen vermenigvuldigen. De analyse van Minsky en Papert uit 1969 liet de grenzen van perceptrons met één laag zien, waaronder het onvermogen om XOR weer te geven. Ze toonde niet aan dat netwerken met meerdere lagen onmogelijk waren. Het ALPAC-rapport uit 1966 verminderde de Amerikaanse steun voor machinevertaling; het Lighthill-rapport uit 1973 droeg bij aan bezuinigingen in het Verenigd Koninkrijk. De terugval in financiering van midden jaren 1970 werd de eerste AI-winter.

Kennis, onzekerheid en leren

Expertsystemen legden specialistische kennis vast als als-danregels. DENDRAL onderzocht molecuulstructuren, MYCIN adviseerde over bloedinfecties en R1/XCON stelde computerbestellingen samen, wat jaarlijks miljoenen Amerikaanse dollars bespaarde. De commerciële groei begin jaren 1980 maakte de kosten van het verwerven en onderhouden van regels zichtbaar. Systemen waren kwetsbaar buiten hun domein; de markt voor Lisp-machines stortte in 1987 in en een tweede winter volgde. Tijdens beide winters ging het onderzoek door.

Vanaf midden jaren 1980 ontwikkelden verschillende onderzoekslijnen zich naast elkaar. Rumelhart, Hinton en Williams maakten terugpropagatie in 1986 bekend. Pearls boek uit 1988 hielp bayesiaanse netwerken te vestigen voor het omgaan met onzekerheid. Verborgen Markovmodellen werden centraal in spraakherkenning. Gedeelde datasets en benchmarks maakten vergelijkingen systematischer.

Grote datasets en snellere hardware ondersteunden de volgende golf. Het op GPU's getrainde diepe netwerk AlexNet won ImageNet in 2012. AlphaGo versloeg Lee Sedol met 4–1 in 2016. Transformers verschenen in 2017; de uitgave van ChatGPT in november 2022 bracht AI voor gesprekken bij een breed publiek.

Vergelijk twee mijlpalen in spelprogramma's

Go biedt doorgaans ongeveer 250 toegestane zetten tegenover ongeveer 35 bij schaken. Aangeleerde sturing hielp veelbelovende voortzettingen te kiezen zonder alles te doorzoeken. Beide systemen gebruikten zoeken: leren breidde de methoden van AI uit zonder de rest van het vakgebied te vervangen. Het AI-effect beschrijft de neiging om een opgeloste vaardigheid geen AI meer te noemen zodra die vertrouwd raakt.

AI is een verzameling methoden voor waarnemen, redeneren, leren en handelen. Een nuttige vergelijking vraagt hoe een systeem kennis weergeeft, waar die kennis vandaan komt en wat er gebeurt als de aannames niet kloppen.

Vergelijk de belangrijkste benaderingen

Een symbolische routeplanner kan de goedkoopste route op zijn kaart vaststellen. De garantie geldt voor die kaart en dat kostenmodel. Kennis wordt vaak door experts vastgelegd, wat een kennisverwervingsknelpunt oplevert, maar symbolische regels kunnen ook worden aangeleerd. Een aangeleerde beslisboom kan bijvoorbeeld leesbare regels opleveren.

Probabilistische methoden geven onzekerheid expliciet weer. Een robot met afstandsmetingen met ruis kan aanwijzingen over verschillende mogelijke locaties combineren. Bayesiaanse netwerken en Markovmodellen structureren zulke redeneringen; beslissingsmodellen verbinden kansen met keuzes. Onzekerheid wordt weergegeven en beheerst, niet weggenomen door een kans te noemen.

Leergebaseerde methoden gebruiken voorbeelden of ervaring om prestaties te verbeteren. Neurale netwerken zijn connectionistische modellen; deep learning gebruikt meerdere lagen. Grote diepe netwerken kunnen veel gegevens en rekenkracht vereisen en moeilijk te interpreteren zijn. Kleinere aangeleerde modellen kunnen leesbaar zijn. Bij aangeleerde systemen kunnen vertekening in de trainingsgegevens en onbekende invoer de prestaties ondermijnen.

Combineer methoden als de taak daarom vraagt

Rodney Brooks' gedragsgebaseerde robotica legde in de jaren 1980 de nadruk op eenvoudig reactief gedrag. Evolutionaire berekening zoekt door kandidaatoplossingen te variëren en betere te selecteren. Hybride systemen combineren methoden: AlphaGo verbindt aangeleerde evaluatie met zoeken; een geautomatiseerd voertuig kan aangeleerde beeldwaarneming, probabilistische tracking, routeplanning en expliciete veiligheidsregels combineren. Neurosymbolisch onderzoek combineert neuraal leren met symbolisch redeneren.

Stel je een magazijnrobot voor die pakketlabels leest, zijn positie schat en een route kiest. Labelherkenning heeft baat bij leren, onzekere locatieschattingen vragen om kansrekening en routebepaling vraagt om zoeken. De fysieke taak verbindt deze methoden zonder ze tot één onderling uitwisselbare techniek te maken.

Beoordeel wat een vaardigheid aantoont

AI-systemen plannen routes, vertalen tekst, herkennen spraak, ondersteunen de analyse van medische beelden en besturen magazijnrobots. Taxidiensten zonder bestuurder vervoeren passagiers in verschillende steden. AlphaFold 2 liet sterke prestaties zien bij het voorspellen van eiwitstructuren; Hassabis en Jumper deelden de helft van de Nobelprijs voor Scheikunde van 2024 voor het voorspellen van eiwitstructuren.

Dit zijn aanzienlijke prestaties op specifieke taken. Om een bredere bewering te beoordelen, bepaal je het doel, de waarnemingen, de beschikbare acties en de omgeving. Een schaakprogramma dat kampioen is, wil winnen, neemt het bord waar en kiest toegestane zetten in een discreet, deterministisch spel. Autorijden vereist waarneming van verborgen gevaren en tijdige fysieke besturing. Schaken winnen levert bewijs voor schaakprestaties, niet voor rijvaardigheid.

Huidige systemen kunnen falen buiten vertrouwde omstandigheden, zelfverzekerd klinkende fouten produceren of bevooroordeelde patronen reproduceren. Fysieke systemen kunnen veiligheidsproblemen veroorzaken; andere risico's zijn surveillance, desinformatie en ontwrichting van werk. Voordelen zijn wetenschappelijke ontdekkingen, ondersteuning bij diagnoses en automatisering van gevaarlijk werk. Neurale netwerken zijn wiskundige modellen die zijn geïnspireerd op neuronen; die inspiratie alleen zegt weinig over hoe sterk hun redenering op die van de hersenen lijkt.

Een robot en een spamfilter ontvangen allebei informatie en veranderen iets buiten zichzelf. Het agentmodel beschrijft deze kringloop zonder een lichaam of een bewering over mensachtige intelligentie te vereisen.

Onderscheid de onderdelen van de kringloop

Sensoren verkrijgen informatie; een waarneming is de informatie die op één moment wordt gemeld. Actuatoren bieden manieren om op de omgeving in te werken. Een camera is een sensor, het huidige beeld is een waarneming, een wielmotor is een actuator en vooruitrijden is een actie.

Bij een softwareagent leveren binnenkomende berichten, bestandsinhoud of toetsaanslagen waarnemingen. Een bestand schrijven, een bericht verplaatsen of een reactie tonen verandert zijn digitale omgeving. Een agent met een fysiek lichaam heeft ook met fysieke dynamiek te maken: massa, snelheid, wrijving, accugrenzen en slijtage zijn van belang voor zijn gedrag.

De waarnemingsreeks is de volledige geschiedenis van waarnemingen. Twee agenten met dezelfde huidige meting kunnen anders handelen omdat hun eerdere metingen verschillen. Een magazijnrobot die zojuist zag dat een gangpad geblokkeerd was, heeft informatie die een pas gestarte robot mist.

Gedrag en de uitvoering ervan

De functie beschrijft wat de agent voor elke invoergeschiedenis zou doen, ook voor geschiedenissen die hij nooit werkelijk tegenkomt. Het programma ontvangt bij elke aanroep de huidige waarneming. Benodigde geschiedenis moet in het geheugen worden bewaard. Agent = architectuur + programma: dezelfde code kan op een platform met andere sensoren of acties heel ander gedrag opleveren.

Doorloop een stofzuigerwereld met twee vakken

Vakken A en B kunnen elk schoon of vuil zijn. De stofzuiger neemt zijn eigen locatie en de vuilstatus van het huidige vak waar. Hij kan Links, Rechts, Zuigen of NietsDoen uitvoeren. Een huidige waarneming zoals “[A, Vuil]” bevat geen informatie over B.

Een eenvoudig programma kan deze regels gebruiken:

if current_square_is_dirty:
    return "Suck"
if location == "A":
    return "Right"
return "Left"

Als het programma in het vuile vak A begint, zuigt het. De volgende waarneming is “[A, Schoon]”, dus gaat de stofzuiger naar rechts. In het vuile vak B zuigt hij opnieuw. Zodra beide vakken schoon zijn, blijft de stofzuiger volgens deze regels bewegen, omdat ze niet opslaan dat beide vakken zijn schoongemaakt. Of dat bewegen de prestatie schaadt, hangt af van de scoreregel.

Waarom niet elke invoergeschiedenis opsommen?

Er zijn vier huidige waarnemingen: A of B gecombineerd met schoon of vuil. Een tabel die op geschiedenissen met lengte 1 tot en met 3 is geïndexeerd, heeft nodig:

Voor lengtes 1 tot en met 10 zijn 1.398.100 vermeldingen nodig. Een langere geschiedenis is een andere tabelsleutel, ook wanneer de laatste waarneming een eerdere herhaalt. Camera's maken het aantal mogelijke invoeren nog veel groter. Een compact programma benut regelmatigheden, zoals schoonmaken wanneer vuil wordt waargenomen, in plaats van elk geval op te slaan.

Een thermostaat een agent noemen beschrijft zijn relatie tussen waarnemen en handelen. Het impliceert geen ingewikkelde redenering. De agentbenadering is vooral nuttig wanneer het kiezen van acties waarneming, gevolgtrekkingen, leren of planning omvat en wanneer de informatie waarover het programma beschikt expliciet moet worden gemaakt.

Goed gedrag vereist een expliciete norm. Een prestatiemaatstaf beoordeelt de reeks omgevingstoestanden die de agent veroorzaakt, zodat twee programma's op hun gevolgen kunnen worden vergeleken.

Beloon de uitkomst die mensen willen

Een stofzuiger die wordt beloond voor verzameld vuil, zou vuil kunnen uitstorten en opnieuw verzamelen. Een schone vloer belonen geeft de gewenste uitkomst beter weer. De ontwerper of gebruiker stelt de maatstaf vast; als een agent succes vrij mocht herdefiniëren, kon hij zichzelf de maximale score geven.

Een maatstaf kan netheid, energie en geluid combineren. Deze keuzes zijn van belang: een vloer die rustig schoon wordt gehouden, verschilt van dezelfde gemiddelde netheid die met storende uitbarstingen wordt bereikt. De definitie van succes komt vóór de keuze van een algoritme.

Bereken een score over de tijd

Beide vakken zijn aanvankelijk vuil en de stofzuiger staat in A. Geef na elk van 10 acties één punt per schoon vak. Schone vakken blijven schoon.

1. Agent 1 doet Zuigen, Rechts, Zuigen en daarna zeven keer NietsDoen. De aantallen schone vakken na de eerste drie acties zijn 1, 1 en 2. Het totaal is $1+1+2+7\times 2=18$.
2. Agent 2 doet Rechts, Zuigen, Links, Zuigen en daarna zes keer NietsDoen. Het totaal is $0+1+1+2+6\times 2=16$.
3. Agent 3 begint net als agent 1, maar blijft tijdens zijn laatste zeven acties bewegen. Zijn score voor netheid is ook 18.

Trek nu één punt per verplaatsing af. Agent 1 verplaatst zich één keer en scoort 17. Agent 3 verplaatst zich acht keer en scoort 10. Door de nieuwe maatstaf is stoppen waardevol zodra de agent weet dat beide vakken schoon zijn.

Beoordeel een beslissing voordat je de uitkomst ziet

Een rationele agent kiest de actie die naar verwachting zijn score op de prestatiemaatstaf maximaliseert, gegeven zijn waarnemingsreeks en ingebouwde kennis. Vier onderdelen bepalen de beoordeling: de maatstaf, voorkennis, beschikbare acties en waarnemingsgeschiedenis.

Rationaliteit verschilt van alwetendheid, wat zou betekenen dat je de werkelijke uitkomst vooraf kent. Een fietser ziet een weersverwachting met 5% kans op regen. Het meenemen van een omvangrijke jas is een zekere last die voor deze fietser zwaarder weegt dan die kans om nat te worden. De jas thuislaten kan rationeel zijn, ook als het later gaat regenen. Een slechte uitkomst verandert de informatie niet die beschikbaar was toen de beslissing werd genomen.

Informatie verzamelen kan zelf een rationele actie zijn. Kijken voordat je een weg oversteekt, kost weinig en verbetert de volgende beslissing. In een onbekende omgeving kan exploratie aan het licht brengen wat acties doen, waarbij een deel van de onmiddellijke beloning wordt ingeruild voor betere latere keuzes.

Laat ervaring het gedrag verbeteren

Autonomie groeit naarmate een agent op zijn eigen ervaring vertrouwt in plaats van alleen op de aannames van zijn ontwerper. Een stofzuiger met een vaste plattegrond kan herhaaldelijk tegen een verplaatste bank botsen. Door de plattegrond met nieuwe metingen bij te werken kan hij zich aanpassen. Nuttige voorkennis helpt hem op weg; door te leren blijft die kennis aansluiten op de omgeving.

Een hoge score is alleen betekenisvol als de maatstaf de beoogde uitkomst weergeeft. Ondersteuningsmeldingen snel afsluiten terwijl problemen onopgelost blijven, is een meetfout, ook als het systeem die score effectief optimaliseert.

Voordat je een agent ontwerpt, specificeer je wat succes betekent en wat de agent kan waarnemen en veranderen. PEAS deelt de taakomgeving in naar prestatiemaatstaf, omgeving, actuatoren en sensoren.

Begin met succes

P beschrijft uitkomsten die kunnen worden beoordeeld. E beschrijft de omgeving en de entiteiten die die uitkomsten beïnvloeden. A vermeldt de middelen om te handelen; S vermeldt de middelen om informatie te verkrijgen. De taakomgeving is het probleem dat de agent moet oplossen, niet het algoritme waarmee hij dat doet.

Voor een geautomatiseerde taxi is “rij goed” te vaag. Een nuttige P omvat veilige, wettige, comfortabele en tijdige ritten, opbrengsten en gevolgen voor andere weggebruikers. Deze kunnen botsen. Veiligheidsvoorwaarden kunnen vaste eisen zijn, waarbij snelheid alleen binnen de veilige keuzes wordt geoptimaliseerd.

Vul de beschrijving van de taxi in

Een passagiersscherm is een actuator omdat het verandert wat de passagier ziet. Een aanraakscherm kan ook sensorinvoer leveren wanneer de passagier een bestemming kiest. Classificeer elke rol naar de richting van informatie of actie, niet naar de alledaagse naam van het apparaat.

Pas PEAS ook buiten autorijden toe

Een medische diagnoseassistent streeft naar gezondheid van patiënten, nauwkeurige diagnoses, nuttige onderzoeken en weinig onnodige ingrepen. De omgeving omvat patiënten, zorgverleners, laboratoria en het ziekenhuis. De uitvoer omvat vragen, onderzoeksaanvragen, voorgestelde diagnoses en doorverwijzingen. De invoer omvat gemelde symptomen, bevindingen, dossiers en onderzoeksresultaten.

Een magazijnrobot die artikelen verzamelt, streeft naar juiste verzamelde artikelen per uur zonder schade of letsel. Stellingen, bakken, transportbanden en mensen vormen zijn omgeving. Wielen, een arm en een grijper zijn actuatoren. Camera's, barcodelezers, sensoren voor gewrichtshoeken en krachtsensoren leveren informatie. De robot moet kracht kunnen meten als zijn maatstaf ingedeukte goederen bestraft: alleen zien dat het juiste artikel wordt gepakt, kan geen te grote grijpkracht aan het licht brengen.

Bij een spamfilter weegt P geblokkeerde spam af tegen ten onrechte geblokkeerde legitieme e-mail. E omvat de mailbox en afzenders. A maakt afleveren of verplaatsen naar spam mogelijk. S levert berichttekst, berichtkoppen en meldingen van gebruikers. Meer spam blokkeren door elk bericht te blokkeren zou ten koste gaan van de aflevering van legitieme e-mail.

Controleer of de onderdelen aansluiten

Schrijf eerst P, daarna E, A en S. Bepaal voor elke gewenste uitkomst hoe de actuatoren die beïnvloeden. Bepaal voor elk feit dat nodig is om een actie te kiezen welke sensor of voorkennis het levert. Een comfortdoel vereist aanwijzingen zoals versnellingsmetingen of feedback van passagiers. Als geen van beide bestaat, kan het ontwerp dat aspect van de rit niet betrouwbaar beoordelen.

Houd instrumenten, waarnemingen en keuzes apart. Een camera is een sensor; een beeld is een waarneming. Een grijper is een actuator; “pak artikel 37” is een actie. Het routealgoritme hoort binnen de agent, terwijl het wegennet bij E hoort. De gekozen sensoren bepalen ook hoeveel relevante informatie voor de agent zichtbaar is.

Omgevingslabels beschrijven afzonderlijke eisen aan een agent. Een taak kan volledig waarneembaar en toch onzeker zijn, of bekende regels en toch verborgen informatie hebben. Classificeer elke dimensie afzonderlijk.

Informatie, andere agenten en uitkomsten

Een omgeving is volledig waarneembaar wanneer sensoren elk feit onthullen dat relevant is voor de actiekeuze. Ze is gedeeltelijk waarneembaar wanneer relevante feiten verborgen zijn of metingen ruis bevatten. Een agent zonder sensoren heeft te maken met een niet waarneembare omgeving. Een schaakbord is zichtbaar; bij poker zijn de kaarten van tegenstanders verborgen.

Een multiagenttaak omvat andere entiteiten waarvan de doelgerichte keuzes het resultaat beïnvloeden en afhangen van ons gedrag. Schaken is competitief; robots die een tafel dragen werken samen. Bestuurders werken samen om botsingen te vermijden en kunnen concurreren om parkeerplaatsen. Een omgevallen boom is een obstakel, geen andere agent. Willekeur kan in een competitie helpen doordat keuzes moeilijker te voorspellen zijn.

In een deterministische omgeving bepalen de toestand en de actie de volgende toestand. Een niet-deterministisch model somt mogelijke uitkomsten op; een stochastisch model kent daar kansen aan toe. Schaken is volgens afspraak deterministisch omdat de onzekerheid over de keuze van de tegenstander bij de multiagentdimensie hoort. Verborgen informatie kan deterministische dynamiek voor een agent onzeker doen lijken.

Afhankelijkheid en het verstrijken van de tijd

Een statische taak kan sequentieel zijn. Het invullen van één antwoord in een kruiswoordpuzzel beperkt latere antwoorden, ook al verandert het raster niet terwijl de oplosser nadenkt. Episodisch betekent dat beslissingen onafhankelijke episodes betreffen, niet slechts dat acties op verschillende momenten plaatsvinden.

Waarden en kennis

Discrete toestanden of acties hebben afzonderlijke alternatieven. Continue grootheden variëren over een bereik, zoals de snelheid of stuurhoek van een auto. Classificeer toestand, tijd, waarnemingen en acties afzonderlijk: digitale beelden bevatten discrete waarden maar geven vaak continu variërende helderheid en positie weer. Schaken met een klok combineert discrete zetten met continu verstrijkende tijd.

In een bekende omgeving zijn de effecten van acties of de kansen op uitkomsten gespecificeerd. In een onbekende omgeving moet de agent die leren. Deze labels gaan over het model, niet over wat de sensoren op dat moment tonen. Patience heeft bekende regels en verborgen kaarten. Een nieuw spel kan zijn volledige toestand tonen terwijl de effecten van de knoppen onbekend blijven.

Pas elke toetsvraag toe op de taak

Vraag achtereenvolgens: Welke relevante feiten zijn verborgen? Wie kiest er nog meer acties? Ligt de volgende toestand vast? Beïnvloeden beslissingen latere beslissingen? Wat verandert terwijl de agent nadenkt? Welke grootheden zijn discreet of continu? Zijn de effecten van acties bekend?

Taxirijden combineert gedeeltelijke waarneembaarheid, meerdere agenten, stochastische uitkomsten, sequentiële beslissingen, een dynamische wereld en continue grootheden. Veel van de dynamiek van het voertuig is bekend, maar een onbekend voertuig kan leren vereisen. De moeilijkste combinatie omvat ook onbekende dynamiek. Leid niet alle zeven labels af uit één moeilijke eigenschap: volledig waarneembaar Go heeft nog steeds een enorme toestandsruimte.

Een classificatie wordt nuttig wanneer ze verandert hoe de agent wordt gebouwd. Een verborgen toestand kan schatting vereisen; onzekere uitkomsten vragen om verschillende mogelijke toekomsten; een veranderende wereld stelt een grens aan de tijd om na te denken.

Vergelijk bekende taken

Deze spelbeschrijvingen gaan ervan uit dat de gebruikelijke regels bekend zijn. Een klok verandert de classificatie van timing zonder stukken te verbergen of de zetregels te veranderen. Dobbelstenen veranderen de onzekerheid over overgangen zonder het zichtbare bord te verbergen.

Classificeer fysieke en diagnostische taken

Een taxi heeft dode hoeken en kan de bedoelingen van andere bestuurders niet direct waarnemen. Andere weggebruikers streven doelen na en het verkeer verandert terwijl de agent nadenkt. Een gemiste afslag beïnvloedt latere keuzes. Posities, snelheden en stuurhoeken variëren continu; onverwachte gebeurtenissen maken uitkomsten stochastisch. Deze combinatie vereist waarneming, voorspelling, tijdige besturing en planning.

Een medische diagnoseassistent heeft onvolledige informatie over inwendige aandoeningen. Onderzoeksresultaten zijn niet perfect, behandelingen hebben onzekere uitkomsten en één onderzoek beïnvloedt de volgende beslissing. De toestand van de patiënt kan tijdens het nadenken veranderen; veel metingen zijn continu. Een gangbaar model behandelt de patiënt als onderdeel van een omgeving met één agent, waarbij de assistent beslissingen neemt om de gezondheid te verbeteren. Die keuze verschilt van het modelleren van meerdere zorgverleners als beslissers die op elkaar reageren.

Een inspectiecamera beoordeelt afgewerkte onderdelen onafhankelijk van elkaar. Een verborgen inwendig gebrek maakt de taak gedeeltelijk waarneembaar, maar eerdere onderdelen hoeven niet te helpen bij de beoordeling van het huidige onderdeel. Als een bewegende transportband de positie van het onderdeel verandert terwijl de camera nadenkt, is de taak dynamisch. Als een stilstaand beeld onveranderd blijft en alleen vertraging de score verlaagt, is de taak semidynamisch. Een deadline alleen bepaalt niet welke situatie van toepassing is.

Vertaal eigenschappen naar ontwerpkeuzes

Wanneer eerdere metingen iets onthullen over de verborgen huidige toestand, gebruik je geheugen en een wereldmodel. Een taxi kan een auto onthouden die in zijn dode hoek is terechtgekomen. Bij onafhankelijke beeldclassificatie voegt geheugen van eerdere onderdelen mogelijk niets nuttigs toe; gedeeltelijke waarneembaarheid op zichzelf toont niet aan dat een geschiedenis nodig is.

Stochastische taken vereisen het vergelijken van onzekere uitkomsten. Competitieve taken vereisen anticipatie op tegenstanders, soms met willekeur. Sequentiële taken vereisen dat je gevolgen overweegt. Dynamische taken vereisen beslissingen die snel genoeg komen om nuttig te blijven. Onbekende effecten vereisen leren en exploratie. Continue grootheden vereisen representaties en methoden die met bereiken kunnen omgaan.

Klassiek zoeken past bij bekende, deterministische, volledig waarneembare, discrete modellen met één agent. Zoeken met tegenstanders behandelt competitieve spellen. Probabilistische inferentie schat verborgen toestanden; beslissingsprocessen ondersteunen onzekere sequentiële keuzes; bekrachtigingsleren behandelt leren door interactie. Gesuperviseerd leren past bij veel onafhankelijke classificatietaken. Een echt systeem kan verschillende van deze methoden combineren omdat zijn omgeving meerdere eisen combineert.

Agentprogramma's verschillen in de informatie die ze gebruiken om een actie te kiezen. Een tabel kan gedrag direct beschrijven; praktische ontwerpen benutten regels en modellen om niet elke geschiedenis te hoeven opsommen.

Vergelijk drie ontwerpen

Een tabelgestuurd programma kan in principe een agentfunctie uitvoeren. Bij vier mogelijke waarnemingen vereisen geschiedenissen tot en met lengte 10 al 1.398.100 vermeldingen. Een regel zoals “als vuil, zuig” dekt veel geschiedenissen met één stuk code.

Zie waarom een reflex in een lus kan raken

Een eenvoudige reflexagent koppelt de huidige situatie aan een conditie-actieregel en handelt vervolgens. Een remlichtdetector kan snel een remactie activeren. Voor een taak waarbij de juiste reactie uit de huidige meting kan worden afgeleid, is dit efficiënt. Volledige waarneembaarheid levert de relevante toestandsinformatie, maar de regels moeten nog steeds geschikte acties kiezen.

Haal de locatiesensor van de stofzuiger weg. Hij ziet nu alleen “Schoon” of “Vuil”. Als hij in het schone vak A begint, leidt de regel “als schoon, ga Links” ertoe dat hij tegen de muur botst. De volgende meting is nog steeds “Schoon”, dus herhaalt hij dit eindeloos. Dezelfde meting komt voor in het schone vak B, waar naar Links gaan zinvol zou zijn. Door ontbrekende informatie zijn de twee situaties niet te onderscheiden.

Willekeurig Links of Rechts kiezen kan een uitweg bieden: vanuit A bereikt elke poging B met kans een half. Het gemiddelde aantal pogingen is 2. Dit doorbreekt de deterministische lus, maar vertelt de agent niet waar hij is of welk vak nog vuil is.

Werk een interne schatting bij

Een modelgebaseerde reflexagent houdt een interne toestand bij die is afgeleid uit eerdere waarnemingen. Hij werkt die toestand bij met de laatste actie en de nieuwe waarneming en past vervolgens regels toe op de bijgewerkte schatting.

Twee modellen hebben verschillende rollen:

• Een overgangsmodel beschrijft hoe de wereld verandert, inclusief de effecten van acties.
• Een sensormodel beschrijft hoe wereldtoestanden waarnemingen opleveren.

Voor een taxi levert het zien van een auto in een spiegel een recente waarneming op. Voorspellen waarheen de auto beweegt hoort bij het overgangsmodel. Een camerabeeld koppelen aan de positie van de auto hoort bij het sensormodel. De taxi kan de auto in zijn interne schatting bewaren nadat die in een dode hoek terechtkomt.

Een stofzuiger kan onthouden dat A is schoongemaakt. Nadat hij B heeft schoongemaakt, zegt zijn toestand dat beide vakken schoon zijn en kan zijn regel NietsDoen kiezen. Volgens de netheidsscore over tien acties met één strafpunt per verplaatsing levert stoppen 17 punten op; blijven rondrijden levert 10 punten op.

Reactieve en deliberatieve besturing

Reflexontwerpen zijn reactief: regels kiezen acties zonder toekomstige reeksen te simuleren. Doelgerichte en nutsgebaseerde ontwerpen zijn deliberatief: ze voorspellen gevolgen. Systemen kunnen snel noodremmen combineren met tragere routeplanning. “Modelgebaseerd” betekent niet vanzelf “doelgericht”: onzichtbare feiten onthouden en vragen welke toekomst een bestemming bereikt zijn verschillende handelingen. Bij gedeeltelijke waarneembaarheid is de interne toestand een schatting die op basis van nieuwe informatie kan worden herzien.

De wereld onthouden ondersteunt betere beslissingen, maar geeft niet aan welke toekomst wenselijk is. Doelgerichte en nutsgebaseerde agenten maken die voorkeur expliciet.

Van een bestemming naar een plan

Een doelgerichte agent voorspelt de resultaten van acties en vraagt of ze naar een gewenste situatie leiden. Een taxi op een kruispunt kan veilig linksaf, rechtsaf of rechtdoor. De bestemming van de passagier bepaalt welke voortzetting helpt. Als de bestemming verandert, verandert het doel, zodat dezelfde kaart en dezelfde redeneermethoden een nieuwe route kunnen vinden.

Een doel is een ja-neetest: bereikt of niet bereikt. Zoeken en planning vinden actiereeksen die voor die test slagen. Expliciete kennis maakt de agent flexibel: een nieuwe bestemming verandert het doel, terwijl een verminderd remvermogen bij regen het model verandert waarmee uitkomsten worden voorspeld.

Een nutsgebaseerde agent kent getallen toe aan de wenselijkheid van uitkomsten. Verschillende routes kunnen dezelfde bestemming bereiken, maar verschillen in tijd, veiligheid of comfort. Nut drukt deze voorkeuren en afwegingen uit. De interne nutsfunctie moet overeenkomen met de externe prestatiemaatstaf, zodat nutsmaximalisatie het beoogde doel dient.

Een binair nut van 1 voor succes en 0 voor falen kan een doel onder onzekerheid weergeven. Gedetailleerder nut kan onderscheid maken tussen succesvolle uitkomsten of verschillende waarden toekennen aan verschillende mislukkingen.

Bereken verwacht nut

Vermenigvuldig voor elke mogelijke uitkomst de kans met het nut en tel de producten op:

Hier beschrijft het kansmodel de uitkomsttoestanden van een actie en beoordeelt de nutsfunctie die uitkomsten. De rationele nutsgebaseerde keuze heeft het grootste verwachte nut.

Werk een beslissing over een trein uit

Een trein vertrekt over 40 minuten. Route A duurt zeker 30 minuten. Route B duurt 20 minuten met kans 0,8 of 50 minuten met kans 0,2.

Als het doel is de verwachte reistijd te minimaliseren:

Route B heeft de kleinere verwachte tijd. Maar de forens vindt het belangrijk de trein te halen. Stel het nut op 1 voor aankomst vóór vertrek en op 0 voor het missen van de trein. Met A wordt de trein altijd gehaald; met B alleen bij de uitkomst van 20 minuten:

Nu heeft A de voorkeur. Het kansmodel is niet veranderd. De beoordeling van de uitkomsten wel. Een gemiddelde aankomsttijd van 26 minuten betekent niet dat elke rit 26 minuten duurt.

Houd rekening met de berekening

Nut kan tijd, gezondheid, comfort of andere gewaardeerde uitkomsten weergeven; het hoeft geen geld weer te geven. Exacte voorspelling van elke mogelijke toekomst is doorgaans te kostbaar, dus gebruiken praktische agenten benaderingen. Vooruitkijken kost ook tijd. Een reflexreactie is nuttig wanneer onmiddellijk handelen volstaat, terwijl nadenken de kosten waard is wanneer toekomstige gevolgen de keuzes onderscheiden.

Leren kan een reflexprogramma, doelgericht programma of nutsgebaseerd programma verbeteren. Het is een manier om een agent te bouwen en aan te passen, geen concurrerende categorie voor actiekeuze.

Volg de leerkringloop

De beoordelingscomponent heeft een externe norm nodig omdat een waarneming alleen niet zegt of een uitkomst goed is. Een schaakmatstelling zien is niet hetzelfde als weten dat winnen wordt beloond. De agent mag zijn norm niet kunnen herdefiniëren om slecht gedrag als succes te laten tellen.

Neem een bezorgdrone. De uitvoeringscomponent vliegt een route. Door tegenwind resteert bij de landing slechts 8% acculading, onder een vaste veiligheidsnorm van 15%. De beoordelingscomponent meldt het tekort. De leercomponent herziet het energiemodel zodat vergelijkbare tegenwind een hoger verbruik voorspelt. Toekomstige vluchten kunnen kleinere ladingen meenemen of kortere routes volgen. De probleemgenerator stelt een langzamere testvlucht voor om te leren of een lagere kruissnelheid energie bespaart.

Exploratie kan de onmiddellijke beloning verminderen en tegelijk latere keuzes verbeteren. Leren kan regels, overgangsmodellen, sensormodellen of een interne nutsschatting veranderen. Een bijgewerkte nutsschatting moet nog steeds de externe prestatienorm dienen; veranderen wat de agent over voorkeuren heeft geleerd verschilt van hem toestemming geven om succes te herdefiniëren.

Kies hoe toestanden worden weergegeven

Een atomaire representatie behandelt een toestand als een ondeelbaar geheel, zoals een plaatsnaam. Het algoritme kan toestanden vergelijken zonder de attributen erin te onderzoeken. Dit is een gangbare opvatting in eenvoudige zoek- en spelmodellen.

Een gefactoriseerde representatie beschrijft een toestand met variabelen die waarden hebben. Een voertuig kan een positie, brandstofniveau en een indicator voor het oliewaarschuwingslampje hebben. Twee toestanden kunnen dezelfde brandstofwaarde delen maar in positie verschillen, zodat regels naar gedeelde eigenschappen kunnen verwijzen. Planning, constraintmodellen, bayesiaanse netwerken en veel vormen van machinaal leren gebruiken dit soort structuur.

Een gestructureerde representatie beschrijft objecten en hun onderlinge relaties. “De vrachtwagen staat achter het hek” onderscheidt een vrachtwagen, een hek en de relatie daartussen. Eerste-ordelogica en taalbegrip gebruiken zulke representaties om uit te drukken wie wat bij wie deed.

Tel combinaties zonder ze op te sommen

Stel dat een gefactoriseerde toestand drie ja-neenvariabelen en een andere variabele met 10 waarden heeft. Het aantal mogelijke waardetoekenningen is:

Eén compacte beschrijving met variabelen staat voor 80 atomaire alternatieven. Constraints kunnen beperken welke waardetoekenningen mogelijk of bereikbaar zijn. Representaties met meer uitdrukkingskracht kunnen regelmatigheden beknopt beschrijven, maar vereisen ingewikkelder redeneringen. Atomair betekent niet onintelligent: plaatsen als namen behandelen is effectief wanneer alleen de wegverbindingen van belang zijn. Objecten en relaties zijn hun complexiteit waard wanneer de taak vereist dat kennis over hun rollen opnieuw wordt gebruikt.

Een probleemoplossende agent scheidt de beslissing wat hij wil bereiken van de beslissing hoe hij dat wil bereiken. Hij formuleert een doel, formuleert een probleem, doorzoekt zijn model naar een oplossing en voert de gekozen acties uit.

Specificeer het model precies

Sommige cursussen combineren acties, resultaten en kosten in een opvolgerfunctie die actie-toestand-kostentripels teruggeeft. Dezelfde informatie is aanwezig. Deze onderdelen beschrijven het probleem; het zoekalgoritme beslist welke mogelijkheden het onderzoekt.

Een pad is een reeks acties. De kosten ervan zijn de som van de actiekosten. Een oplossing leidt van de begintoestand naar een doeltoestand; een optimale oplossing heeft de laagste kosten van alle oplossingen. Bij positieve, ongelijke kosten kunnen minder acties toch meer kosten.

Vergelijk routes op basis van hun kosten

Weglengten in kilometers zijn Alden–Brook 40, Alden–Cove 25, Brook–Cove 10, Brook–Elm 30, Cove–Dale 35 en Dale–Elm 20. Wegen kunnen in beide richtingen worden gebruikt. De toestand is de huidige plaats; begin in Alden en toets op Elm. Toepasbare acties volgen wegen vanuit de huidige plaats en elke actie kost de lengte van de weg.

De oplossingen zonder herhaalde plaatsen zijn:

• Alden → Brook → Elm: 70 km.
• Alden → Cove → Brook → Elm: 65 km.
• Alden → Cove → Dale → Elm: 80 km.
• Alden → Brook → Cove → Dale → Elm: 105 km.

De route over drie wegen via Cove en Brook is beter dan de route over twee wegen via Brook. Omdat weglengten positief zijn, kan het toevoegen van een cyclus de afstand niet verbeteren.

Formuleer de stofzuigerwereld

Een toestand legt de locatie van de stofzuiger en de vuilstatus van elk vak vast: twee posities gecombineerd met twee onafhankelijke vuilindicatoren geeft 8 toestanden. Acties zijn Links, Rechts en Zuigen. Zuigen maakt het huidige vak schoon. Links in A en Rechts in B laten de locatie onveranderd. De doeltest vraagt of beide vakken schoon zijn; elke actie kost 1.

Als de stofzuiger in A begint met beide vakken vuil, bereikt Zuigen, Rechts, Zuigen het doel tegen kosten 3. Twee schoonmaakacties en minstens één verplaatsing zijn nodig, dus is dit plan optimaal. Een model kan bewegingen aan de rand uit ACTIES weglaten of opnemen als acties zonder effect; ACTIES en RESULTAAT moeten dezelfde afspraak volgen.

Onderscheid toestanden van paden

De toestandsruimtegraaf heeft één knoop per toestand en gerichte verbindingen voor acties. Een weg in twee richtingen levert twee gerichte verbindingen. Een zoekboom geeft paden vanaf het begin weer: twee verschillende paden kunnen in dezelfde toestand eindigen en zo verschillende boomknopen vormen. Een graaf kan naar behoefte worden gegenereerd met ACTIES en RESULTAAT, zonder elke toestand vooraf op te slaan.

In een volledig waarneembaar, deterministisch en bekend model kan een vast plan zonder terugkoppeling en zonder verdere waarneming worden uitgevoerd. Wanneer de uitvoering van de voorspelling kan afwijken, volgt besturing met terugkoppeling de waarnemingen en plant opnieuw of volgt vertakkingen voor verschillende uitkomsten. De doeltoestand alleen specificeert een bestemming; de actiereeks verklaart hoe je daar komt.

Een wereldtoestand bevat alle details van de omgeving. Een zoektoestand bewaart wat planning nodig heeft.

Toets wat moet worden onthouden

Neem voldoende informatie op om toepasbare acties, overgangsresultaten, doelstatus en actiekosten vanuit de huidige toestand te bepalen. Als twee situaties op een van die vragen verschillende antwoorden vereisen, houd je ze apart.

Om op een vast rooster een uitgang te bereiken kan de locatie voldoende zijn. Om pakketten te verzamelen gaat bij alleen de locatie verloren welke artikelen nog over zijn. Bij beweging met een beperkte acculading gaat bij alleen de locatie verloren of de volgende actie mogelijk is. De kleur van muren kan worden weggelaten wanneer die geen van deze beslissingen verandert.

Een abstractie is geldig wanneer elke abstracte oplossing kan worden uitgewerkt tot een echte oplossing. Ze is nuttig wanneer haar acties eenvoudiger zijn uit te voeren dan het oorspronkelijke probleem op te lossen. Gedetailleerd sturen vervangen door “rij van Cove naar Brook” helpt alleen als die abstracte rit daadwerkelijk kan worden uitgevoerd.

Bouw de telling variabele voor variabele op

Een robot beweegt op een rooster van 5 × 6 met 8 pakketten op vaste plaatsen.

1. Om de uitgang te bereiken, sla je het vak op: $5\times 6=30$ mogelijkheden.
2. Om alle pakketten te verzamelen, voeg je acht indicatoren verzameld/niet verzameld toe: $30\times 2^8=7.680$ waardetoekenningen.
3. Als de acculading van belang is, voeg je 11 niveaus toe, van 0 tot en met 10: $7.680\times 11=84.480$ waardetoekenningen.

Vermenigvuldig de domeingroottes wanneer alle combinaties zijn toegestaan. Dit telt weergegeven configuraties; het aantal dat vanuit de begintoestand bereikbaar is, kan kleiner zijn. De 8-puzzel heeft $9!=362.880$ configuraties, maar vanuit één gegeven configuratie zijn er slechts 181.440 bereikbaar. Voor de 15-puzzel is het overeenkomstige bereikbare aantal 10.461.394.944.000, ongeveer 1,05 × 10¹³.

Een stofzuigerwereld met n vakken heeft een locatie en n vuilindicatoren, wat $n{2}^n$ toestanden geeft. Twee vakken geven 8 toestanden; tien geven er 10.240. Een binaire variabele toevoegen verdubbelt het aantal, wat de exponentiële groei verklaart.

Verander de formulering, niet de taak

Het acht-damesprobleem vraagt om acht dames die elkaar niet aanvallen. Een formulering met volledige kandidaatoplossingen begint met acht dames en verplaatst ze. Een incrementele formulering begint leeg en voegt dames toe.

Als elke nieuwe dame op elk leeg vak mag worden geplaatst, ontstaan ongeveer 1,8 × 10¹⁴ geordende reeksen van acht plaatsingen. Veel volgorden leveren hetzelfde bord op. Het tellen van verschillende borden met nul tot en met acht dames geeft 5.130.659.561 toestanden. Dit zijn verschillende grootheden: reeksen leggen vast hoe een bord is opgebouwd; toestanden leggen het bord vast.

Voeg in plaats daarvan alleen een dame toe in de meest linkse lege kolom en alleen op een niet aangevallen vak. Deze formulering heeft 2.057 toestanden, waaronder 92 oplossingen, ongeveer 2,5 miljoen keer minder verschillende toestanden dan de onbeperkte incrementele versie. Ze voorkomt veel kansloze keuzes voordat het zoekproces ze verkent.

Bewaar noodzakelijke geschiedenis in compacte vorm

Een rondreis die elke plaats moet bezoeken, heeft zowel de verzameling bezochte plaatsen als de huidige plaats nodig. Meestal is de exacte volgorde van alle eerdere verplaatsingen niet nodig, tenzij de volgorde de toelaatbaarheid of kosten beïnvloedt. Onnodige geschiedenis opslaan laat gelijkwaardige situaties verschillend lijken en verhindert hergebruik van werk. Het aantal toestanden is één aanwijzing voor de moeilijkheid; de structuur van de graaf en de gebruikte zoekmethode zijn ook van belang.

Een goede formulering maakt het doel, de toegestane zetten en de kosten precies genoeg voor een zoekmethode. Kleine puzzels maken deze keuzes zichtbaar; praktische taken voegen timing, onzekerheid of constraints toe die de toestand moet bewaren.

Volg een formulering in stappen

1. Formuleer een meetbaar doel dat aan de prestatiemaatstaf is gekoppeld.
2. Kies de minimaal voldoende toestandsvariabelen en de begintoestand.
3. Definieer toepasbare acties en hun resultaten.
4. Schrijf de doeltest.
5. Ken actiekosten met eenheden toe.
6. Controleer de abstractie en schat het aantal toestanden.

Voor de 8-puzzel sla je de posities van acht stenen en het lege vak op. Verplaats het lege vak naar een aangrenzend vak en wissel het met die steen. Een hoek staat 2 zetten toe, een rand 3 en het midden 4. De doeltest vergelijkt de configuratie met een gespecificeerd doel. Actiekosten van één maken de padkosten gelijk aan het aantal zetten.

Modelleer een paar waterkannen

Gebruik kannen van 4 liter en 3 liter zonder maatverdeling, een kraan en een afvoer. Begin met lege kannen. Sla de hoeveelheden op als een geordend paar: eerst de kan van 4 liter, dan de kan van 3 liter. De toegestane handelingen zijn vullen, legen en gieten totdat de bron leeg of de ontvangende kan vol is. Elke handeling kost 1.

Giet vanuit (3, 3) de kleinere kan in de grotere. De bron bevat 3 liter, maar de ontvangende kan heeft maar plaats voor 1 liter. Giet de kleinste hoeveelheid over:

Het resultaat is (4, 2). Gieten verdeelt water niet willekeurig; de stopregel bepaalt de overgegoten hoeveelheid. Als je met lege kannen begint, blijven hele liters hele liters. De representatie bevat 20 combinaties van gehele getallen, waarvan er 14 bereikbaar zijn vanuit (0, 0).

Laat de doeltest succes bepalen

Voor “een van de kannen bevat 2 liter” kost een kortste plan vier acties:

(0, 0) → vul kleinere → (0, 3) → giet in grotere → (3, 0) → vul kleinere → (3, 3) → giet in grotere → (4, 2).

Voor “de kan van 4 liter bevat 2 liter” voldoet (4, 2) niet aan de test. Een kortste plan kost zes acties:

(0, 0) → vul grotere → (4, 0) → giet in kleinere → (1, 3) → leeg kleinere → (1, 0) → giet in kleinere → (0, 1) → vul grotere → (4, 1) → giet in kleinere → (2, 3).

Als je enkele woorden in het doel verandert, verandert welk eindpunt als succes telt. Door de volgorde in de toestand vast te houden voorkom je dat je de hoeveelheid in de ene kan met die in de andere verwart.

Voeg de feiten toe die echte taken nodig hebben

Een vluchtplanner heeft de huidige luchthaven en tijd nodig. Toegestane vervolgvluchten moeten laat genoeg vertrekken voor de overstap. De tariefklasse of eerdere trajecten horen ook in de toestand wanneer ze toekomstige opties of prijzen beïnvloeden. Afstand alleen kan geen doel weergeven dat tarieven, wachten, vluchtduur en gemak combineert; een kostenmodel moet de afwegingen definiëren.

Een rondreisprobleem moet bezochte plaatsen onthouden. Het handelsreizigersprobleem zoekt een kortste rondreis die elke stad één keer bezoekt en naar het begin terugkeert; het is NP-moeilijk, zonder bekende efficiënte exacte methode voor alle grote gevallen. Robotnavigatie kan continue positie en gewrichtshoeken nodig hebben. VLSI-ontwerp behandelt plaatsing en verbindingen van componenten; bij het bepalen van de assemblagevolgorde moet worden bijgehouden welke onderdelen al zijn gemonteerd, omdat een vroege keuze een latere stap kan blokkeren.

Test vóór het zoeken één gewone actie en één grensgeval. Een volle ontvangende kan mag geen water meer opnemen; een al vertrokken vlucht mag niet als beschikbare aansluiting verschijnen. Deze controles brengen ontbrekende toestand of inconsistente actieregels vroeg aan het licht.