Intelligente Agenten und Problemformulierung

Ein intelligentes System kann danach beurteilt werden, was es tut oder wie es denkt. Es kann außerdem an menschlicher Leistung oder an einem Maßstab der Rationalität gemessen werden. Aus diesen beiden Unterscheidungen ergeben sich vier Sichtweisen auf KI.

Den Maßstab wählen

Kognitive Modellierung gehört zum menschlichen Denken. Ein Programm, das ein Rätsel mit dem richtigen Endergebnis löst, kann dennoch ein schlechtes Modell menschlichen Denkens sein, wenn Menschen andere Schritte verwenden. Psychologische Experimente, Selbstbeobachtung und bildgebende Verfahren zur Untersuchung des Gehirns helfen, das Modell zu prüfen. Newell und Simon nutzten bei der Entwicklung des General Problem Solver Aufzeichnungen menschlicher Schlussfolgerungsschritte.

Der Ansatz der Denkgesetze nutzt Logik. Aus „Alle Menschen sind sterblich“ und „Sokrates ist ein Mensch“ leitet er „Sokrates ist sterblich“ ab. Reale Entscheidungen umfassen auch unsichere Prämissen und die Wahl einer Aktion. Wahrscheinlichkeiten behandeln die Unsicherheit; eine Handlungsstrategie verbindet Schlussfolgerungen mit Verhalten.

Was der Turing-Test prüft

Turings Imitationsspiel von 1950 beruht auf einem schriftlichen Austausch mit einem verborgenen Menschen und einer verborgenen Maschine. Die Maschine ist erfolgreich, wenn die fragende Person beide nicht zuverlässig unterscheiden kann. Sprachverarbeitung, Wissensrepräsentation, Schlussfolgern und Lernen unterstützen diese Aufgabe. Der vollständige Turing-Test ergänzt physische Interaktion: maschinelles Sehen, um Objekte zu erkennen, Robotik, um mit ihnen umzugehen, und Spracherkennung für gesprochene Interaktion.

Eine überzeugende Konversation belegt menschenähnliches Konversationsverhalten. Ob sie Verständnis belegt, ist eine andere Frage. ELIZA, 1966 veröffentlicht, konnte die Aussage einer nutzenden Person in eine Frage umwandeln: Auf „Ich fühle mich einsam“ konnte „Warum fühlst du dich einsam?“ folgen. Solche Antworten können Verständnis nahelegen, ohne dass ein Modell der Situation der sprechenden Person vorliegt. Nachahmung kann außerdem menschliche Fehler oder ausweichende Antworten belohnen.

Searles Chinesisches Zimmer von 1980 verdeutlicht den Unterschied. Eine Person befolgt ein Regelbuch, um chinesische Antworten auszugeben, ohne Chinesisch zu verstehen. Searle argumentiert, dass das bloße Ausführen von Regeln für Verständnis nicht ausreicht. Die Systemantwort verortet ein mögliches Verständnis im Gesamtsystem einschließlich der Regeln und des Raums. Der philosophische Streit bleibt offen. Schwache KI betrifft intelligentes Handeln; starke KI behauptet tatsächliches Denken und Verstehen.

Mit begrenzten Mitteln gut handeln

Die Sicht des rationalen Agenten, das Standardmodell der KI, beurteilt Aktionen nach ihren erwarteten Folgen. Ein schneller Reflex kann rational sein; langes logisches Nachdenken ist unnötig, wenn ein sofortiges Zurückziehen eine Verbrennung verhindert. Praktischen Agenten stehen nur begrenzte Zeit und Rechenleistung zur Verfügung. Beschränkte Rationalität bedeutet daher, mit diesen Mitteln so gut wie möglich zu handeln.

Auch die Wahl des Ziels ist wichtig. Eine Maschine, die nur für das Schließen von Supportanfragen belohnt wird, könnte sie schließen, ohne Probleme zu lösen. Das ist ein Versagen der Werteausrichtung: Das optimierte Maß erfasst nicht, was Menschen wichtig ist. Ein vorgeschlagener Entwurf lässt die Maschine über das wahre Ziel unsicher bleiben und auf menschliche Anleitung reagieren.

Spezialisierte KI bearbeitet bestimmte Aufgaben. AGI würde flexibel lernen und Aufgaben aus einem breiten Spektrum auf menschlichem Niveau ausführen. Sprachliche Gewandtheit in vielen Gesprächen und hervorragende Leistung in einem Spiel beantworten andere Fragen als die, ob ein System diese allgemeine Fähigkeit besitzt; es gibt keinen allgemein anerkannten AGI-Test.

KI verbindet Ideen aus Fachgebieten, die unterschiedliche Teile derselben Frage untersuchten: Wie kann ein System die Welt repräsentieren, etwas über sie lernen und nützliche Aktionen wählen?

Ideen vor der Entstehung des Fachgebiets

Die Philosophie lieferte Logik und Theorien des Geistes. Die Mathematik lieferte Wahrscheinlichkeitsrechnung, formales Schließen und Grenzen der Berechenbarkeit. Die Wirtschaftswissenschaften steuerten Nutzen und Entscheidungstheorie bei. Psychologie und Neurowissenschaften lieferten Erklärungen zur Informationsverarbeitung und zu Neuronen. Die Computertechnik lieferte Hardware; die Linguistik lieferte die Struktur der Sprache. Regelungstechnik und Kybernetik untersuchten Rückkopplung, etwa wenn ein Thermostat eine Temperaturabweichung ausgleicht. Die Agentensicht führt diese Beiträge zusammen.

Von frühen Modellen zu frühen Grenzen

McCulloch und Pitts beschrieben 1943 künstliche Neuronen, die logische Funktionen berechnen. Turing schlug 1950 das Imitationsspiel vor. McCarthy, Minsky, Rochester und Shannon reichten 1955 den Dartmouth-Antrag ein; der Workshop von 1956 begründete KI als Fachgebiet. Sein Anspruch war, Lernen und Intelligenz so genau zu beschreiben, dass Maschinen sie simulieren können.

Zu den frühen Erfolgen gehörten der Logic Theorist und der General Problem Solver von Newell und Simon, Samuels lernendes Dameprogramm, McCarthys Sprache Lisp von 1958 und Rosenblatts Perzeptron von 1958. Diese Programme zeigten Schlussfolgern oder Lernen in begrenzten Situationen. Optimistische Vorhersagen eilten dem Fortschritt voraus: Die Prognose eines Schachweltmeisters innerhalb von zehn Jahren erfüllte sich erst nach etwa vierzig Jahren.

Drei Hindernisse wurden deutlich. Den Programmen fehlte Fachwissen, Suchräume wuchsen zu schnell und manche Repräsentationen waren zu begrenzt. Kombinatorische Explosion bedeutet, dass einige zusätzliche Wahlmöglichkeiten die Anzahl der Möglichkeiten enorm vervielfachen können. Die Analyse von Minsky und Papert aus dem Jahr 1969 zeigte Grenzen einschichtiger Perzeptronen, darunter, dass sie XOR nicht darstellen können. Sie zeigte nicht, dass mehrschichtige Netze unmöglich sind. Der ALPAC-Bericht von 1966 verringerte die US-Förderung für maschinelle Übersetzung; der Lighthill-Bericht von 1973 trug zu Förderkürzungen im Vereinigten Königreich bei. Der Förderrückgang Mitte der 1970er-Jahre wurde zum ersten KI-Winter.

Wissen, Unsicherheit und Lernen

Expertensysteme codierten Fachwissen als Wenn-dann-Regeln. DENDRAL untersuchte Molekülstrukturen, MYCIN beriet bei Blutinfektionen und R1/XCON konfigurierte Computerbestellungen und sparte jährlich Millionen US-Dollar. Das kommerzielle Wachstum Anfang der 1980er-Jahre machte die Kosten für den Erwerb und die Pflege von Regeln deutlich. Außerhalb ihrer Fachgebiete waren die Systeme wenig robust; 1987 brach der Markt für Lisp-Maschinen zusammen und ein zweiter Winter folgte. Während beider Winter wurde weiter geforscht.

Ab Mitte der 1980er-Jahre kamen mehrere Entwicklungen gemeinsam voran. Rumelhart, Hinton und Williams machten 1986 Backpropagation bekannt. Pearls Buch von 1988 trug dazu bei, bayessche Netze für den Umgang mit Unsicherheit zu etablieren. Versteckte Markov-Modelle wurden zentral für die Spracherkennung. Gemeinsame Datensätze und Benchmarks machten Vergleiche systematischer.

Große Datensätze und schnellere Hardware unterstützten die nächste Welle. Das auf Grafikprozessoren trainierte tiefe Netz AlexNet gewann 2012 ImageNet. AlphaGo besiegte Lee Sedol 2016 mit 4–1. Transformer erschienen 2017; die Veröffentlichung von ChatGPT im November 2022 brachte dialogfähige KI zu einem breiten Publikum.

Zwei Meilensteine bei spielenden Systemen vergleichen

Go bietet typischerweise ungefähr 250 zulässige Züge gegenüber ungefähr 35 beim Schach. Die gelernte Steuerung half, vielversprechende Fortsetzungen auszuwählen, ohne alles zu durchsuchen. Beide Systeme nutzten Suche: Lernen erweiterte die Methoden der KI, ohne den Rest des Fachgebiets zu ersetzen. Der KI-Effekt beschreibt die Tendenz, eine gelöste Fähigkeit nicht mehr als KI zu bezeichnen, sobald sie vertraut geworden ist.

KI umfasst Methoden für Wahrnehmung, Schlussfolgern, Lernen und Handeln. Ein hilfreicher Vergleich fragt, wie ein System Wissen repräsentiert, woher dieses Wissen stammt und was geschieht, wenn seine Annahmen nicht zutreffen.

Die Hauptansätze vergleichen

Ein symbolischer Routenplaner kann die kostengünstigste Route auf seiner Karte nachweisen. Seine Garantie betrifft diese Karte und das Kostenmodell. Wissen wird oft von Fachleuten formuliert, wodurch ein Wissensakquisitionsengpass entsteht. Symbolische Regeln können aber auch gelernt werden. Ein gelernter Entscheidungsbaum kann beispielsweise lesbare Regeln liefern.

Probabilistische Methoden stellen Unsicherheit explizit dar. Ein Roboter mit verrauschten Entfernungsmessungen kann Evidenz zu mehreren möglichen Standorten kombinieren. Bayessche Netze und Markov-Modelle strukturieren solche Schlussfolgerungen; Entscheidungsmodelle verbinden Wahrscheinlichkeiten mit Entscheidungen. Unsicherheit wird dargestellt und gehandhabt, nicht durch die Angabe einer Wahrscheinlichkeit beseitigt.

Lernbasierte Methoden nutzen Beispiele oder Erfahrung, um die Leistung zu verbessern. Neuronale Netze sind konnektionistische Modelle; Deep Learning nutzt mehrere Schichten. Große tiefe Netze können viele Daten und viel Rechenleistung benötigen und schwer zu interpretieren sein. Kleinere gelernte Modelle können lesbar sein. Bei gelernten Systemen können Verzerrungen in den Trainingsdaten und ungewohnte Eingaben die Leistung beeinträchtigen.

Methoden kombinieren, wenn die Aufgabe es verlangt

Rodney Brooks' verhaltensbasierte Robotik der 1980er-Jahre betonte einfache reaktive Verhaltensweisen. Evolutionäre Verfahren suchen, indem sie Kandidaten verändern und bessere auswählen. Hybride Systeme kombinieren Methoden: AlphaGo verbindet gelernte Bewertung mit Suche; ein automatisiertes Fahrzeug kann gelerntes Sehen, probabilistische Verfolgung, Routenplanung und explizite Sicherheitsregeln kombinieren. Neurosymbolische Forschung verbindet neuronales Lernen mit symbolischem Schließen.

Stell dir einen Lagerroboter vor, der Paketetiketten liest, seine Position schätzt und eine Route wählt. Die Etikettenerkennung profitiert vom Lernen, unsichere Positionsschätzungen verlangen Wahrscheinlichkeiten und die Routenplanung verlangt Suche. Die physische Aufgabe verbindet diese Methoden, ohne sie zu einem einzigen austauschbaren Verfahren zu machen.

Beurteilen, was eine Fähigkeit belegt

KI-Systeme planen Routen, übersetzen Texte, erkennen Sprache, unterstützen die Analyse medizinischer Bilder und steuern Lagerroboter. Fahrerlose Taxidienste befördern in mehreren Städten Fahrgäste. AlphaFold 2 zeigte starke Leistungen bei der Vorhersage von Proteinstrukturen; Hassabis und Jumper erhielten für die Vorhersage von Proteinstrukturen gemeinsam die Hälfte des Chemienobelpreises 2024.

Das sind beachtliche Leistungen bei einzelnen Aufgaben. Um eine weitergehende Aussage zu bewerten, bestimme Ziel, Wahrnehmungen, verfügbare Aktionen und Umgebung. Ein Schachprogramm auf Meisterniveau will gewinnen, nimmt das Brett wahr und wählt zulässige Züge in einem diskreten, deterministischen Spiel. Autofahren verlangt die Wahrnehmung verborgener Gefahren und rechtzeitige physische Steuerung. Schach zu gewinnen liefert einen Beleg für Schachleistung, nicht für Fahrkönnen.

Heutige Systeme können außerhalb vertrauter Bedingungen versagen, selbstsicher wirkende Fehler erzeugen oder verzerrte Muster reproduzieren. Physische Systeme können Sicherheitsmängel verursachen; weitere Risiken sind Überwachung, Desinformation und Umbrüche in der Arbeitswelt. Zum Nutzen gehören wissenschaftliche Entdeckungen, Unterstützung bei Diagnosen und die Automatisierung gefährlicher Arbeit. Neuronale Netze sind von Neuronen inspirierte mathematische Modelle; diese Inspiration allein sagt wenig darüber aus, wie ähnlich ihre Schlussfolgerungen denen eines Gehirns sind.

Ein Roboter und ein Spamfilter erhalten beide Informationen und verändern etwas außerhalb ihrer selbst. Das Agentenmodell beschreibt diesen Kreislauf, ohne einen Körper oder menschenähnliche Intelligenz vorauszusetzen.

Die Teile des Kreislaufs unterscheiden

Sensoren gewinnen Informationen; eine Wahrnehmung ist die Information, die zu einem Zeitpunkt gemeldet wird. Aktuatoren bieten Möglichkeiten, auf die Umgebung einzuwirken. Eine Kamera ist ein Sensor, ihr aktuelles Bild eine Wahrnehmung, ein Radmotor ein Aktuator und das Vorwärtsfahren eine Aktion.

Bei einem Softwareagenten liefern eingehende Nachrichten, Dateiinhalte oder Tastatureingaben Wahrnehmungen. Das Schreiben einer Datei, Verschieben einer Nachricht oder Anzeigen einer Antwort verändert seine digitale Umgebung. Ein verkörperter Agent ist außerdem physikalischer Dynamik ausgesetzt: Masse, Geschwindigkeit, Reibung, Akkugrenzen und Verschleiß sind für sein Verhalten relevant.

Die Wahrnehmungsfolge ist die vollständige Abfolge der Wahrnehmungen. Zwei Agenten, die denselben aktuellen Messwert erhalten, können unterschiedlich handeln, weil sich ihre früheren Messwerte unterscheiden. Ein Lagerroboter, der vor einem Moment einen blockierten Gang gesehen hat, besitzt Informationen, die einem gerade gestarteten Roboter fehlen.

Verhalten und seine Implementierung

Die Funktion beschreibt, was der Agent bei jeder Eingabefolge tun würde, auch bei Folgen, die tatsächlich nie auftreten. Das Programm erhält bei jedem Aufruf die aktuelle Wahrnehmung. Eine benötigte Vorgeschichte muss im Speicher erhalten bleiben. Agent = Architektur + Programm: Derselbe Code kann sich auf einer Plattform mit anderen Sensoren oder Aktionen ganz anders verhalten.

Einen Staubsauger mit zwei Feldern durchgehen

Die Felder A und B können jeweils sauber oder schmutzig sein. Der Staubsauger nimmt seinen eigenen Standort und den Schmutzzustand seines aktuellen Felds wahr. Er kann Links, Rechts, Saugen oder Keine Aktion ausführen. Eine aktuelle Wahrnehmung wie „[A, Schmutzig]“ enthält keine Angabe über B.

Ein einfaches Programm kann diese Regeln nutzen:

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

Startet es auf dem schmutzigen Feld A, saugt es. Seine nächste Wahrnehmung ist „[A, Sauber]“, also fährt es nach rechts. Auf dem schmutzigen Feld B saugt es erneut. Sobald beide Felder sauber sind, bewegt es sich nach diesen Regeln weiter, weil sie nicht speichern, dass beide gereinigt wurden. Ob diese Bewegung die Leistung beeinträchtigt, hängt von der Bewertungsregel ab.

Warum nicht jede Eingabefolge auflisten?

Es gibt vier aktuelle Wahrnehmungen: A oder B kombiniert mit sauber oder schmutzig. Eine Tabelle, die nach Folgen der Länge 1 bis 3 indiziert ist, benötigt:

Für die Längen 1 bis 10 benötigt sie 1.398.100 Einträge. Eine längere Folge ist ein anderer Tabellenschlüssel, auch wenn ihre letzte Wahrnehmung eine frühere wiederholt. Kameras vergrößern die Anzahl möglicher Eingaben noch erheblich. Ein kompaktes Programm nutzt Regelmäßigkeiten, etwa immer zu reinigen, wenn Schmutz wahrgenommen wird, statt jeden Fall zu speichern.

Einen Thermostat als Agenten zu bezeichnen, beschreibt seine Beziehung zwischen Sensor und Aktion. Das bedeutet nicht, dass er anspruchsvoll schlussfolgert. Die Agentensicht wird besonders nützlich, wenn die Aktionswahl Wahrnehmung, Schlussfolgern, Lernen oder Planung umfasst und wenn ausdrücklich festgehalten werden muss, welche Informationen dem Programm zur Verfügung stehen.

Gutes Verhalten braucht einen expliziten Maßstab. Ein Leistungsmaß bewertet die Folge von Umgebungszuständen, die der Agent erzeugt, sodass zwei Programme anhand ihrer Folgen verglichen werden können.

Das gewünschte Ergebnis belohnen

Ein Staubsauger, der für gesammelten Schmutz belohnt wird, könnte Schmutz abladen und erneut aufsaugen. Einen sauberen Boden zu belohnen erfasst das gewünschte Ergebnis besser. Die entwickelnde oder nutzende Person legt das Maß fest; dürfte ein Agent den Erfolg frei neu definieren, könnte er sich selbst die volle Punktzahl geben.

Ein Leistungsmaß kann Sauberkeit, Energie und Lärm verbinden. Diese Entscheidungen sind wichtig: Ein leise sauber gehaltener Boden unterscheidet sich von derselben durchschnittlichen Sauberkeit, die durch störende Arbeitsphasen erreicht wird. Die Definition des Erfolgs geht der Wahl eines Algorithmus voraus.

Eine Punktzahl über die Zeit berechnen

Beide Felder sind anfangs schmutzig, der Staubsauger steht in A. Vergib nach jeder von 10 Aktionen einen Punkt pro sauberem Feld. Saubere Felder bleiben sauber.

1. Agent 1 führt Saugen, Rechts, Saugen und dann siebenmal Keine Aktion aus. Die Anzahlen sauberer Felder nach den ersten drei Aktionen sind 1, 1 und 2. Seine Gesamtpunktzahl ist $1+1+2+7\times 2=18$.
2. Agent 2 führt Rechts, Saugen, Links, Saugen und dann sechsmal Keine Aktion aus. Seine Gesamtpunktzahl ist $0+1+1+2+6\times 2=16$.
3. Agent 3 beginnt wie Agent 1, bewegt sich aber bei seinen letzten sieben Aktionen weiter. Seine Sauberkeitspunktzahl beträgt ebenfalls 18.

Ziehe nun pro Bewegung einen Punkt ab. Agent 1 bewegt sich einmal und erzielt 17 Punkte. Agent 3 bewegt sich achtmal und erzielt 10 Punkte. Das neue Maß belohnt das Anhalten, sobald der Agent weiß, dass beide Felder sauber sind.

Eine Entscheidung vor ihrem Ergebnis beurteilen

Ein rationaler Agent wählt angesichts seiner Wahrnehmungsfolge und seines eingebauten Wissens die Aktion, die sein Leistungsmaß erwartungsgemäß maximiert. Vier Bestandteile bestimmen die Beurteilung: das Leistungsmaß, Vorwissen, verfügbare Aktionen und die Wahrnehmungsfolge.

Rationalität unterscheidet sich von Allwissenheit, die bedeuten würde, das tatsächliche Ergebnis im Voraus zu kennen. Eine radfahrende Person sieht eine Regenwahrscheinlichkeit von 5 % in der Vorhersage. Eine sperrige Jacke mitzunehmen ist eine sichere Last, die für diese Person die Möglichkeit überwiegt, nass zu werden. Sie zu Hause zu lassen kann rational sein, auch wenn es später regnet. Ein schlechtes Ergebnis ändert nichts an der Evidenz, die bei der Entscheidung verfügbar war.

Informationsbeschaffung kann selbst eine rationale Aktion sein. Vor dem Überqueren einer Straße zu schauen kostet wenig und verbessert die nächste Entscheidung. In einer unbekannten Situation kann Exploration zeigen, was Aktionen bewirken. Dabei wird ein Teil der unmittelbaren Belohnung gegen bessere spätere Entscheidungen abgewogen.

Verhalten durch Erfahrung verbessern

Autonomie wächst, wenn sich ein Agent auf eigene Erfahrungen statt nur auf die Annahmen seiner Entwickler stützt. Ein Staubsauger mit einer festen Karte kann wiederholt gegen ein verschobenes Sofa stoßen. Aktualisiert er die Karte anhand neuer Messwerte, kann er sich anpassen. Nützliches Vorwissen hilft ihm beim Start; Lernen hält dieses Wissen an die Umgebung angepasst.

Eine hohe Punktzahl ist nur aussagekräftig, wenn das Maß das beabsichtigte Ergebnis erfasst. Supporttickets schnell zu schließen und Probleme ungelöst zu lassen ist ein Messfehler, selbst wenn das System diese Punktzahl wirksam optimiert.

Lege vor dem Entwurf eines Agenten fest, was Erfolg bedeutet und was der Agent wahrnehmen und verändern kann. PEAS gliedert die Aufgabenumgebung in Leistungsmaß, Umgebung, Aktuatoren und Sensoren.

Mit dem Erfolg beginnen

P beschreibt Ergebnisse, die bewertet werden können. E beschreibt die Umgebung und die Entitäten, die diese Ergebnisse beeinflussen. A führt die Handlungsmöglichkeiten auf; S die Möglichkeiten zur Informationsgewinnung. Die Aufgabenumgebung ist das Problem, das der Agent lösen soll, nicht der Algorithmus zu seiner Lösung.

Für ein automatisiertes Taxi ist „gut fahren“ zu vage. Ein nützliches P umfasst sichere, regelkonforme, komfortable und zeitgerechte Fahrten, Einnahmen und Auswirkungen auf andere Verkehrsteilnehmer. Diese können in Konflikt stehen. Sicherheitsvorgaben können feste Anforderungen sein, wobei die Geschwindigkeit nur unter den sicheren Möglichkeiten optimiert wird.

Die Beschreibung des Taxis ausfüllen

Eine Fahrgastanzeige ist ein Aktuator, weil sie verändert, was der Fahrgast sieht. Ein Touchscreen kann auch Sensoreingaben liefern, wenn der Fahrgast ein Ziel auswählt. Ordne jede Rolle nach der Richtung der Information oder Aktion ein, nicht nach dem Alltagsnamen des Geräts.

PEAS außerhalb des Straßenverkehrs anwenden

Ein medizinischer Diagnoseassistent zielt auf die Gesundheit der Patienten, genaue Diagnosen, nützliche Untersuchungen und wenige unnötige Eingriffe. Seine Umgebung umfasst Patienten, medizinisches Fachpersonal, Labore und das Krankenhaus. Zu seinen Ausgaben gehören Fragen, Untersuchungsanforderungen, Diagnosevorschläge und Überweisungen. Seine Eingaben umfassen gemeldete Symptome, Befunde, Akten und Untersuchungsergebnisse.

Ein Kommissionierroboter im Lager soll pro Stunde die richtigen Artikel entnehmen, ohne Schäden oder Verletzungen zu verursachen. Regale, Behälter, Förderbänder und Menschen bilden seine Umgebung. Räder, ein Arm und ein Greifer sind Aktuatoren. Kameras, Barcodeleser, Gelenkwinkelsensoren und Kraftsensoren liefern Informationen. Der Roboter muss Kraft erfassen, wenn sein Leistungsmaß zerdrückte Ware bestraft: Allein der Anblick des richtigen Artikels kann keine übermäßige Greifkraft offenbaren.

Bei einem Spamfilter wägt P blockierten Spam gegen fälschlich blockierte legitime E-Mails ab. E umfasst das Postfach und Absender. A ermöglicht die Zustellung oder das Verschieben in den Spamordner. S liefert Nachrichtentext, Kopfzeilen und Meldungen der Nutzer. Mehr Spam zu blockieren, indem jede Nachricht blockiert wird, ginge zulasten der Zustellung legitimer Nachrichten.

Prüfen, ob die Teile zusammenpassen

Schreibe zuerst P, dann E, A und S. Bestimme für jedes gewünschte Ergebnis, wie die Aktuatoren es beeinflussen. Bestimme für jede zur Aktionswahl benötigte Information einen Sensor oder Vorwissen, das sie liefert. Ein Komfortziel braucht Evidenz wie Beschleunigungsmessungen oder Rückmeldungen der Fahrgäste. Gibt es beides nicht, kann der Entwurf diesen Aspekt der Fahrt nicht zuverlässig beurteilen.

Halte Instrumente, Beobachtungen und Entscheidungen auseinander. Eine Kamera ist ein Sensor; ein Bild ist eine Wahrnehmung. Ein Greifer ist ein Aktuator; „Artikel 37 aufnehmen“ ist eine Aktion. Der Routenplanungsalgorithmus gehört in den Agenten, das Straßennetz dagegen zu E. Die gewählten Sensoren bestimmen außerdem, wie viele relevante Informationen für den Agenten sichtbar sind.

Umgebungsmerkmale beschreiben unterschiedliche Anforderungen an einen Agenten. Eine Aufgabe kann vollständig beobachtbar und zugleich unsicher sein oder bekannte Regeln und zugleich verborgene Informationen haben. Klassifiziere jedes Merkmal unabhängig.

Informationen, andere Agenten und Ergebnisse

Eine Umgebung ist vollständig beobachtbar, wenn Sensoren jede für die Aktionswahl relevante Information offenlegen. Sie ist partiell beobachtbar, wenn relevante Informationen verborgen oder Messwerte verrauscht sind. Ein Agent ohne Sensoren steht vor einer unbeobachtbaren Umgebung. Ein Schachbrett ist sichtbar; Poker verbirgt die Karten der Gegner.

Eine Mehragentenaufgabe umfasst andere Entitäten, deren zielgerichtete Entscheidungen das Ergebnis beeinflussen und von unserem Verhalten abhängen. Schach ist kompetitiv; Roboter, die einen Tisch tragen, kooperieren. Fahrer kooperieren, um Zusammenstöße zu vermeiden, und können um Parkplätze konkurrieren. Ein umgestürzter Baum ist ein Hindernis, kein weiterer Agent. Zufällige Entscheidungen können im Wettbewerb helfen, weil sie schwerer vorherzusehen sind.

In einer deterministischen Umgebung legen Zustand und Aktion den nächsten Zustand fest. Ein nichtdeterministisches Modell listet mögliche Ergebnisse auf; ein stochastisches Modell ordnet ihnen Wahrscheinlichkeiten zu. Schach gilt konventionell als deterministisch, weil die Unsicherheit über die Wahl des Gegners zum Merkmal Mehragentenumgebung gehört. Verborgene Informationen können deterministische Dynamik für einen Agenten unsicher erscheinen lassen.

Abhängigkeit und Zeitverlauf

Eine statische Aufgabe kann sequenziell sein. Das Eintragen einer Antwort in ein Kreuzworträtsel schränkt spätere Antworten ein, obwohl sich das Gitter nicht verändert, während die lösende Person nachdenkt. Episodisch bedeutet, dass Entscheidungen unabhängige Episoden betreffen, nicht lediglich, dass Aktionen zu verschiedenen Zeiten stattfinden.

Werte und Wissen

Diskrete Zustände oder Aktionen haben unterscheidbare Alternativen. Kontinuierliche Größen verändern sich über einen Wertebereich, etwa die Geschwindigkeit oder der Lenkwinkel eines Autos. Klassifiziere Zustand, Zeit, Wahrnehmungen und Aktionen getrennt: Digitale Bilder enthalten diskrete Werte, stellen aber oft kontinuierlich veränderliche Helligkeit und Positionen dar. Schach mit Uhr verbindet diskrete Züge mit kontinuierlich verstreichender Zeit.

In einer bekannten Umgebung sind Aktionswirkungen oder Ergebniswahrscheinlichkeiten festgelegt. In einer unbekannten Umgebung muss der Agent sie lernen. Diese Bezeichnungen betreffen das Modell, nicht das, was die Sensoren gerade zeigen. Patience hat bekannte Regeln und verborgene Karten. Ein neues Spiel kann seinen vollständigen Zustand zeigen und zugleich die Wirkungen seiner Tasten unbekannt lassen.

Jede Prüffrage auf die Aufgabe anwenden

Frage der Reihe nach: Welche relevanten Informationen sind verborgen? Wer sonst wählt Aktionen? Ist der nächste Zustand festgelegt? Beeinflussen Entscheidungen spätere Entscheidungen? Was verändert sich, während der Agent nachdenkt? Welche Größen sind diskret oder kontinuierlich? Sind die Aktionswirkungen bekannt?

Taxifahren verbindet partielle Beobachtbarkeit, mehrere Agenten, stochastische Ergebnisse, sequenzielle Entscheidungen, eine dynamische Welt und kontinuierliche Größen. Ein großer Teil der Fahrzeugdynamik ist bekannt, aber bei einem ungewohnten Fahrzeug kann Lernen nötig sein. Die schwierigste Kombination umfasst auch unbekannte Dynamik. Leite nicht alle sieben Einordnungen aus einer einzigen schwierigen Eigenschaft ab: Das vollständig beobachtbare Go hat dennoch einen enormen Zustandsraum.

Eine Klassifikation wird nützlich, wenn sie beeinflusst, wie der Agent aufgebaut wird. Ein verborgener Zustand kann eine Schätzung verlangen; unsichere Ergebnisse erfordern mehrere mögliche Zukünfte; eine veränderliche Welt begrenzt die Zeit zum Überlegen.

Vertraute Aufgaben vergleichen

Diese Spielbeschreibungen setzen voraus, dass ihre üblichen Regeln bekannt sind. Eine Uhr verändert die zeitliche Klassifikation, ohne Figuren zu verbergen oder Zugregeln zu ändern. Würfel verändern die Unsicherheit des Übergangs, ohne das sichtbare Brett zu verbergen.

Physische und diagnostische Aufgaben klassifizieren

Ein Taxi hat tote Winkel und kann die Absichten anderer Fahrer nicht direkt beobachten. Andere Verkehrsteilnehmer verfolgen Ziele, und der Verkehr verändert sich, während der Agent nachdenkt. Eine verpasste Ausfahrt beeinflusst spätere Entscheidungen. Positionen, Geschwindigkeiten und Lenkwinkel verändern sich kontinuierlich; unerwartete Ereignisse machen Ergebnisse stochastisch. Diese Kombination verlangt Wahrnehmung, Vorhersage, rechtzeitige Steuerung und Planung.

Ein medizinischer Diagnoseassistent verfügt über unvollständige Evidenz zu inneren Zuständen. Testergebnisse sind unvollkommen, Behandlungen haben unsichere Ergebnisse, und ein Test beeinflusst die nächste Entscheidung. Der Zustand des Patienten kann sich während des Überlegens ändern; viele Messwerte sind kontinuierlich. Ein verbreitetes Modell behandelt den Patienten als Teil einer Einzelagentenumgebung, wobei der Assistent Entscheidungen zur Verbesserung der Gesundheit trifft. Diese Wahl unterscheidet sich davon, mehrere medizinische Fachkräfte als miteinander interagierende Entscheidende zu modellieren.

Eine Prüfkamera beurteilt fertige Teile unabhängig voneinander. Ein verborgener innerer Fehler macht die Aufgabe partiell beobachtbar, doch frühere Teile müssen bei der Beurteilung des aktuellen Teils nicht helfen. Verändert ein laufendes Förderband die Position des Teils, während die Kamera überlegt, ist die Aufgabe dynamisch. Bleibt ein eingefrorenes Bild unverändert und verringert nur die Verzögerung die Punktzahl, ist sie semidynamisch. Eine Frist allein legt nicht fest, welche Situation vorliegt.

Eigenschaften in Entwurfsentscheidungen übersetzen

Wenn frühere Messwerte etwas über den verborgenen aktuellen Zustand verraten, nutze ein Gedächtnis und ein Weltmodell. Ein Taxi kann sich an ein Auto erinnern, das in seinen toten Winkel gefahren ist. Bei unabhängiger Bildklassifikation muss die Erinnerung an frühere Objekte nichts Nützliches beitragen; partielle Beobachtbarkeit allein begründet keinen Bedarf an einer Vorgeschichte.

Stochastische Aufgaben verlangen den Vergleich unsicherer Ergebnisse. Kompetitive Aufgaben verlangen, Gegner zu berücksichtigen, manchmal mithilfe von Zufall. Sequenzielle Aufgaben verlangen, Folgen zu bedenken. Dynamische Aufgaben verlangen Entscheidungen, die rechtzeitig genug erfolgen, um nützlich zu bleiben. Unbekannte Wirkungen verlangen Lernen und Exploration. Kontinuierliche Größen verlangen Repräsentationen und Methoden für Wertebereiche.

Klassische Suche passt zu bekannten, deterministischen, vollständig beobachtbaren, diskreten Einzelagentenmodellen. Adversarielle Suche behandelt kompetitive Spiele. Probabilistische Inferenz schätzt verborgene Zustände; Entscheidungsprozesse unterstützen unsichere sequenzielle Entscheidungen; bestärkendes Lernen behandelt das Lernen durch Interaktion. Überwachtes Lernen passt zu vielen unabhängigen Klassifikationsaufgaben. Ein reales System kann mehrere dieser Methoden kombinieren, weil seine Umgebung mehrere Anforderungen verbindet.

Agentenprogramme unterscheiden sich darin, welche Informationen sie zur Aktionswahl nutzen. Eine Tabelle kann Verhalten direkt beschreiben; praktische Entwürfe nutzen Regeln und Modelle, um nicht jede Folge aufzuzählen.

Drei Entwürfe vergleichen

Ein tabellengesteuertes Programm kann prinzipiell eine Agentenfunktion implementieren. Bei vier möglichen Wahrnehmungen erfordern Folgen bis zur Länge 10 bereits 1.398.100 Einträge. Eine Regel wie „Wenn schmutzig, saugen“ deckt viele Folgen mit einem Stück Code ab.

Erkennen, warum ein Reflex in einer Schleife enden kann

Ein einfacher Reflexagent gleicht die aktuelle Situation mit einer Bedingungs-Aktions-Regel ab und handelt dann. Ein Bremslichterkennungssystem kann schnell das Bremsen auslösen. Bei einer Aufgabe, deren richtige Reaktion aus dem aktuellen Messwert hervorgeht, ist das effizient. Vollständige Beobachtbarkeit liefert die relevanten Zustandsinformationen, aber die Regeln müssen weiterhin geeignete Aktionen wählen.

Entferne den Standortsensor des Staubsaugers. Er sieht nun nur „Sauber“ oder „Schmutzig“. Startet er im sauberen Feld A, lässt ihn die Regel „Wenn sauber, nach links fahren“ gegen die Wand stoßen. Der nächste Messwert lautet weiterhin „Sauber“, also wiederholt er dies endlos. Derselbe Messwert tritt im sauberen Feld B auf, wo eine Bewegung nach links sinnvoll wäre. Fehlende Informationen machen die beiden Situationen ununterscheidbar.

Eine zufällige Wahl zwischen Links und Rechts kann einen Ausweg bieten: Von A aus erreicht jeder Versuch B mit Wahrscheinlichkeit ein halb. Die durchschnittliche Anzahl der Versuche beträgt 2. Das beseitigt die deterministische Schleife, sagt dem Agenten aber nicht, wo er ist oder welches Feld noch schmutzig ist.

Eine interne Schätzung aktualisieren

Ein modellbasierter Reflexagent führt einen internen Zustand, der aus früheren Wahrnehmungen abgeleitet wird. Er aktualisiert diesen Zustand anhand der letzten Aktion und der neuen Wahrnehmung und wendet dann Regeln auf die aktualisierte Schätzung an.

Zwei Modelle erfüllen unterschiedliche Aufgaben:

• Ein Übergangsmodell beschreibt, wie sich die Welt verändert, einschließlich der Aktionswirkungen.
• Ein Sensormodell beschreibt, wie Weltzustände Beobachtungen erzeugen.

Für ein Taxi ist der Blick auf ein Auto im Spiegel eine kürzlich gemachte Beobachtung. Die Vorhersage, wohin sich das Auto bewegt, gehört zum Übergangsmodell. Die Zuordnung eines Kamerabilds zur Position des Autos gehört zum Sensormodell. Das Taxi kann das Auto in seiner internen Schätzung behalten, nachdem es in einen toten Winkel gefahren ist.

Ein Staubsauger kann sich merken, dass A gereinigt wurde. Nachdem er B gereinigt hat, besagt sein Zustand, dass beide Felder sauber sind, und seine Regel kann Keine Aktion wählen. Bei der Sauberkeitsbewertung über zehn Aktionen mit einem Punkt Abzug pro Bewegung erzielt das Anhalten 17 Punkte; weiteres Umherfahren erzielt 10.

Reaktive und deliberative Steuerung

Reflexentwürfe sind reaktiv: Regeln wählen Aktionen, ohne künftige Folgen zu simulieren. Zielbasierte und nutzenbasierte Entwürfe sind deliberativ: Sie sagen Folgen voraus. Systeme können schnelle Notbremsungen und langsamere Routenplanung in Schichten kombinieren. „Modellbasiert“ bedeutet nicht von selbst „zielbasiert“: Sich unsichtbare Sachverhalte zu merken und zu fragen, welche Zukunft ein Ziel erreicht, sind unterschiedliche Vorgänge. Bei partieller Beobachtbarkeit ist der interne Zustand eine Schätzung, die durch neue Evidenz überarbeitet werden kann.

Sich Informationen über die Welt zu merken unterstützt bessere Entscheidungen, sagt aber nicht, welche Zukunft wünschenswert ist. Zielbasierte und nutzenbasierte Agenten machen diese Präferenz explizit.

Vom Zielort zum Plan

Ein zielbasierter Agent sagt Aktionsergebnisse voraus und fragt, ob sie zu einer gewünschten Situation führen. Ein Taxi an einer Kreuzung kann sicher links, rechts oder geradeaus fahren. Der Zielort des Fahrgasts bestimmt, welche Fortsetzung hilfreich ist. Ändert sich der Zielort, ändert sich das Ziel, sodass mit derselben Karte und denselben Schlussfolgerungsverfahren eine neue Route gefunden werden kann.

Ein Ziel ist ein Ja-Nein-Test: erreicht oder nicht erreicht. Suche und Planung finden Aktionsfolgen, die ihn bestehen. Explizites Wissen macht den Agenten flexibel: Ein neuer Zielort verändert das Ziel, während eine verringerte Bremsleistung bei Regen das Modell zur Vorhersage der Ergebnisse verändert.

Ein nutzenbasierter Agent drückt durch Zahlen aus, wie wünschenswert Ergebnisse sind. Mehrere Routen können denselben Zielort erreichen, sich aber in Zeit, Sicherheit oder Komfort unterscheiden. Nutzen drückt diese Präferenzen und Zielkonflikte aus. Die interne Nutzenfunktion muss mit dem externen Leistungsmaß übereinstimmen, damit die Nutzenmaximierung dem beabsichtigten Ziel dient.

Ein binärer Nutzen von 1 für Erfolg und 0 für Misserfolg kann ein Ziel unter Unsicherheit darstellen. Ein differenzierterer Nutzen kann zwischen erfolgreichen Ergebnissen unterscheiden oder unterschiedlichen Misserfolgen verschiedene Werte zuordnen.

Den erwarteten Nutzen berechnen

Multipliziere für jedes mögliche Ergebnis seine Wahrscheinlichkeit mit seinem Nutzen und addiere dann die Produkte:

Das Wahrscheinlichkeitsmodell beschreibt hier die Ergebniszustände einer Aktion, und die Nutzenfunktion bewertet diese Ergebnisse. Die rationale nutzenbasierte Wahl hat den größten erwarteten Nutzen.

Eine Entscheidung für den Zug durchrechnen

Ein Zug fährt in 40 Minuten ab. Route A dauert mit Sicherheit 30 Minuten. Route B dauert mit Wahrscheinlichkeit 0,8 20 Minuten oder mit Wahrscheinlichkeit 0,2 50 Minuten.

Wenn das Ziel ist, die erwartete Fahrzeit zu minimieren:

Route B hat die geringere erwartete Zeit. Der pendelnden Person ist es aber wichtig, den Zug zu erreichen. Setze den Nutzen für die Ankunft vor der Abfahrt auf 1 und für das Verpassen auf 0. Auf A wird der Zug immer erreicht; auf B nur beim Ergebnis mit 20 Minuten:

Nun wird A bevorzugt. Das Wahrscheinlichkeitsmodell hat sich nicht verändert, wohl aber die Bewertung der Ergebnisse. Eine durchschnittliche Ankunftszeit von 26 Minuten bedeutet nicht, dass jede Fahrt 26 Minuten dauert.

Den Rechenaufwand berücksichtigen

Nutzen kann Zeit, Gesundheit, Komfort oder andere geschätzte Ergebnisse darstellen; er muss kein Geld darstellen. Eine exakte Vorhersage jeder möglichen Zukunft ist im Allgemeinen zu aufwendig, daher verwenden praktische Agenten Näherungen. Auch Vorausschau kostet Zeit. Eine Reflexreaktion ist nützlich, wenn sofortiges Handeln ausreicht, während sich die Kosten des Überlegens lohnen, wenn künftige Folgen die Wahlmöglichkeiten unterscheiden.

Lernen kann ein Reflexprogramm, ein zielbasiertes oder ein nutzenbasiertes Programm verbessern. Es ist eine Möglichkeit, einen Agenten aufzubauen und anzupassen, keine konkurrierende Kategorie der Aktionswahl.

Den Lernkreislauf verfolgen

Der Kritiker braucht einen externen Standard, weil eine Wahrnehmung allein nicht sagt, ob ein Ergebnis gut ist. Eine Schachmattstellung zu sehen ist etwas anderes, als zu wissen, dass Gewinnen belohnt wird. Der Agent darf seinen Standard nicht so umdefinieren können, dass schlechtes Verhalten als Erfolg zählt.

Betrachte eine Lieferdrohne. Das Leistungselement fliegt eine Route. Durch Gegenwind bleiben bei der Landung nur 8 % Akkuladung, weniger als der feste Sicherheitsstandard von 15 %. Der Kritiker meldet die Unterschreitung. Das Lernelement überarbeitet das Energiemodell, sodass es bei ähnlichem Gegenwind einen höheren Verbrauch vorhersagt. Künftige Flüge können kleinere Lasten tragen oder kürzere Routen nehmen. Der Problemgenerator schlägt einen langsameren Testflug vor, um zu lernen, ob eine geringere Reisegeschwindigkeit Energie spart.

Exploration kann die unmittelbare Belohnung verringern und zugleich spätere Entscheidungen verbessern. Lernen kann Regeln, Übergangsmodelle, Sensormodelle oder eine interne Nutzenschätzung verändern. Eine aktualisierte Nutzenschätzung muss weiterhin dem externen Leistungsstandard dienen; das Gelernte über Präferenzen zu ändern ist etwas anderes, als dem Agenten zu erlauben, Erfolg neu zu definieren.

Wählen, wie Zustände repräsentiert werden

Eine atomare Repräsentation behandelt einen Zustand als unteilbare Einheit, etwa einen Stadtnamen. Der Algorithmus kann Zustände vergleichen, ohne ihre inneren Attribute zu untersuchen. Dies ist eine verbreitete Sicht in grundlegenden Such- und Spielmodellen.

Eine faktorisierte Repräsentation beschreibt einen Zustand durch Variablen mit Werten. Ein Fahrzeug könnte Position, Tankfüllstand und eine Anzeige für die Ölwarnleuchte haben. Zwei Zustände können denselben Tankfüllstand haben und sich in der Position unterscheiden, sodass Regeln auf gemeinsame Eigenschaften Bezug nehmen können. Planung, Constraint-Modelle, bayessche Netze und ein großer Teil des maschinellen Lernens nutzen diese Art von Struktur.

Eine strukturierte Repräsentation beschreibt Objekte und ihre Beziehungen. „Der Lastwagen steht hinter dem Tor“ unterscheidet einen Lastwagen, ein Tor und die Beziehung zwischen ihnen. Prädikatenlogik erster Stufe und Sprachverstehen nutzen solche Repräsentationen, um auszudrücken, wer wem was getan hat.

Kombinationen zählen, ohne sie aufzulisten

Angenommen, ein faktorisierter Zustand hat drei Ja-Nein-Variablen und eine weitere Variable mit 10 Werten. Die Anzahl möglicher Belegungen ist:

Eine kompakte Beschreibung durch Variablen steht für 80 atomare Alternativen. Constraints können einschränken, welche Belegungen möglich oder erreichbar sind. Ausdrucksstärkere Repräsentationen können Regelmäßigkeiten knapp beschreiben, verlangen aber aufwendigeres Schlussfolgern. Atomar bedeutet nicht unintelligent: Städte als Namen zu behandeln ist wirksam, wenn nur die Straßenverbindungen wichtig sind. Objekte und Beziehungen rechtfertigen ihre Komplexität, wenn die Aufgabe verlangt, Wissen über ihre Rollen wiederzuverwenden.

Ein problemlösender Agent trennt die Entscheidung, was erreicht werden soll, von der Entscheidung, wie es erreicht werden soll. Er formuliert ein Ziel und ein Problem, sucht in seinem Modell nach einer Lösung und führt die gewählten Aktionen aus.

Das Modell präzise festlegen

Manche Kurse fassen Aktionen, Ergebnisse und Kosten in einer Nachfolgerfunktion zusammen, die Aktion-Zustand-Kosten-Tripel zurückgibt. Dieselben Informationen sind enthalten. Diese Bestandteile beschreiben das Problem; der Suchalgorithmus entscheidet, welche Möglichkeiten er untersucht.

Ein Pfad ist eine Folge von Aktionen. Seine Kosten sind die Summe der Aktionskosten. Eine Lösung führt vom Anfangszustand zu einem Zielzustand; eine optimale Lösung hat die niedrigsten Kosten unter den Lösungen. Bei positiven, ungleichen Kosten können weniger Aktionen dennoch mehr kosten.

Routen anhand ihrer Kosten vergleichen

Die Straßenlängen in Kilometern sind Alden–Brook 40, Alden–Cove 25, Brook–Cove 10, Brook–Elm 30, Cove–Dale 35 und Dale–Elm 20. Die Straßen sind in beide Richtungen befahrbar. Der Zustand ist die aktuelle Stadt; starte in Alden und prüfe auf Elm. Anwendbare Aktionen folgen Straßen von der aktuellen Stadt aus, und jede Aktion kostet die Länge der Straße.

Die einfachen Lösungspfade sind:

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

Die Route über drei Straßen durch Cove und Brook ist günstiger als die Route über zwei Straßen durch Brook. Da die Straßenlängen positiv sind, kann ein zusätzlicher Zyklus die Entfernung nicht verringern.

Die Staubsaugerwelt formulieren

Ein Zustand erfasst den Standort des Staubsaugers und den Schmutzzustand jedes Felds: Zwei Positionen kombiniert mit zwei unabhängigen Schmutzangaben ergeben 8 Zustände. Aktionen sind Links, Rechts und Saugen. Saugen reinigt das aktuelle Feld. Links in A und Rechts in B lassen den Standort unverändert. Der Zieltest fragt, ob beide Felder sauber sind; jede Aktion kostet 1.

Startet der Agent in A und sind beide Felder schmutzig, erreicht Saugen, Rechts, Saugen das Ziel mit Kosten von 3. Zwei Reinigungsaktionen und mindestens eine Bewegung sind nötig, daher ist dieser Plan optimal. Ein Modell kann Bewegungen am Rand aus AKTIONEN weglassen oder als Aktionen ohne Wirkung aufnehmen; AKTIONEN und ERGEBNIS müssen dieselbe Konvention umsetzen.

Zustände von Pfaden unterscheiden

Der Zustandsraumgraph hat einen Knoten pro Zustand und gerichtete Kanten für Aktionen. Eine in beide Richtungen befahrbare Straße liefert zwei gerichtete Kanten. Ein Suchbaum stellt Pfade vom Anfang dar: Zwei verschiedene Pfade können im selben Zustand enden und dabei unterschiedliche Baumknoten erzeugen. Ein Graph kann mit AKTIONEN und ERGEBNIS bei Bedarf erzeugt werden, ohne jeden Zustand im Voraus zu speichern.

In einem vollständig beobachtbaren, deterministischen und bekannten Modell kann ein fester Plan ohne Rückkopplung und ohne weitere Wahrnehmung ausgeführt werden. Kann die Ausführung von der Vorhersage abweichen, überwacht eine Steuerung mit Rückkopplung die Wahrnehmungen und plant neu oder folgt Verzweigungen für verschiedene Ergebnisse. Der Zielzustand allein legt einen Zielort fest; die Aktionsfolge erklärt, wie man dorthin gelangt.

Ein Weltzustand enthält alle Einzelheiten der Umgebung. Ein Suchzustand behält, was die Planung benötigt.

Prüfen, was gespeichert werden muss

Nimm genügend Informationen auf, um anwendbare Aktionen, Übergangsergebnisse, Zielerfüllung und Aktionskosten aus dem aktuellen Zustand zu bestimmen. Wenn zwei Situationen auf eine dieser Fragen unterschiedliche Antworten benötigen, halte sie getrennt.

Um in einem festen Gitter einen Ausgang zu erreichen, kann der Standort genügen. Beim Einsammeln von Paketen geht allein aus dem Standort nicht hervor, welche Artikel noch vorhanden sind. Bei Bewegung mit begrenzter Akkuladung geht allein aus dem Standort nicht hervor, ob die nächste Aktion möglich ist. Die Wandfarbe kann entfallen, wenn sie keine dieser Entscheidungen verändert.

Eine Abstraktion ist gültig, wenn sich jede abstrakte Lösung zu einer realen Lösung ausarbeiten lässt. Sie ist nützlich, wenn sich ihre Aktionen leichter ausführen lassen als das ursprüngliche Problem zu lösen ist. Detaillierte Lenkbewegungen durch „Fahre von Cove nach Brook“ zu ersetzen hilft nur, wenn sich diese abstrakte Fahrt tatsächlich ausführen lässt.

Die Anzahl Variable für Variable bestimmen

Ein Roboter bewegt sich auf einem 5 × 6-Gitter mit 8 fest platzierten Paketen.

1. Um den Ausgang zu erreichen, speichere die Zelle: $5\times 6=30$ Möglichkeiten.
2. Um alle Pakete einzusammeln, ergänze acht Angaben eingesammelt/nicht eingesammelt: $30\times 2^8=7.680$ Belegungen.
3. Ist die Akkuladung wichtig, ergänze 11 Stufen von 0 bis 10: $7.680\times 11=84.480$ Belegungen.

Multipliziere die Größen der Wertebereiche, wenn alle Kombinationen erlaubt sind. Das zählt die repräsentierten Konfigurationen; die Anzahl der vom Anfangszustand aus erreichbaren kann kleiner sein. Das 8-Puzzle hat $9!=362.880$ Anordnungen, aber nur 181.440 sind von einer beliebigen Anordnung aus erreichbar. Beim 15-Puzzle beträgt die entsprechende Anzahl erreichbarer Zustände 10.461.394.944.000, also etwa 1,05 × 10¹³.

Ein Staubsauger mit n Feldern hat einen Standort und n Schmutzangaben, was $n{2}^n$ Zustände ergibt. Zwei Felder ergeben 8 Zustände; zehn ergeben 10.240. Eine zusätzliche binäre Variable verdoppelt die Anzahl, was das exponentielle Wachstum erklärt.

Die Formulierung ändern, nicht die Aufgabe

Das Acht-Damen-Problem verlangt acht Damen, die einander nicht angreifen. Eine vollständige Zustandsformulierung beginnt mit acht Damen und bewegt sie. Eine inkrementelle Formulierung beginnt leer und fügt Damen hinzu.

Darf jede neue Dame auf ein beliebiges leeres Feld gesetzt werden, entstehen etwa 1,8 × 10¹⁴ geordnete Folgen von acht Platzierungen. Viele Reihenfolgen erzeugen dasselbe Brett. Zählt man verschiedene Bretter mit null bis acht Damen, erhält man 5.130.659.561 Zustände. Das sind unterschiedliche Größen: Folgen halten fest, wie ein Brett aufgebaut wurde; Zustände halten das Brett fest.

Setze stattdessen eine Dame nur in die am weitesten links liegende leere Spalte und nur auf ein nicht angegriffenes Feld. Diese Formulierung hat 2.057 Zustände, darunter 92 Lösungen, also etwa 2,5 Millionen Mal weniger verschiedene Zustände als die uneingeschränkte inkrementelle Variante. Sie verhindert viele aussichtslose Entscheidungen, bevor die Suche sie erkundet.

Nötige Vorgeschichte kompakt speichern

Eine Rundreise, die jede Stadt besuchen muss, benötigt neben der aktuellen Stadt die Menge der besuchten Städte. Die genaue Reihenfolge aller früheren Züge ist gewöhnlich nicht nötig, sofern sie nicht die Zulässigkeit oder Kosten beeinflusst. Unnötige Vorgeschichte zu speichern lässt gleichwertige Situationen unterschiedlich aussehen und verhindert die Wiederverwendung geleisteter Arbeit. Die Zustandsanzahl ist ein Hinweis auf die Schwierigkeit; die Struktur des Graphen und das Verfahren zu seiner Erkundung sind ebenfalls wichtig.

Eine gute Formulierung legt Ziel, zulässige Züge und Kosten so genau fest, dass ein Suchverfahren sie nutzen kann. Kleine Rätsel machen diese Entscheidungen sichtbar; praktische Aufgaben ergänzen Zeitbedingungen, Unsicherheit oder Constraints, die der Zustand bewahren muss.

Einer Reihenfolge zur Formulierung folgen

1. Formuliere ein messbares Ziel, das mit dem Leistungsmaß verbunden ist.
2. Wähle die minimal ausreichenden Zustandsvariablen und den Anfangszustand.
3. Definiere anwendbare Aktionen und ihre Ergebnisse.
4. Schreibe den Zieltest auf.
5. Weise Aktionskosten mit Einheiten zu.
6. Prüfe die Abstraktion und schätze die Zustandsanzahl.

Speichere für das 8-Puzzle die Positionen von acht Kacheln und dem Leerfeld. Bewege das Leerfeld in eine benachbarte Zelle und tausche es mit dieser Kachel. Eine Ecke erlaubt 2 Züge, ein Randfeld 3 und die Mitte 4. Der Zieltest vergleicht die Anordnung mit einer vorgegebenen Zielanordnung. Kostet jede Aktion eine Einheit, entsprechen die Pfadkosten der Anzahl der Züge.

Ein Paar Wasserkrüge modellieren

Verwende unmarkierte Krüge mit 4 und 3 Litern, einen Wasserhahn und einen Abfluss. Beginne mit leeren Krügen. Speichere die Mengen als geordnetes Paar: zuerst den 4-Liter-Krug, dann den 3-Liter-Krug. Erlaubt sind Füllen, Leeren und Umfüllen, bis der Ausgangskrug leer oder der Zielkrug voll ist. Jede Aktion kostet 1.

Gieße von (3, 3) aus den kleineren Krug in den größeren. Der Ausgangskrug enthält 3 Liter, aber der Zielkrug bietet nur noch Platz für 1 Liter. Fülle die kleinere Menge um:

Das Ergebnis ist (4, 2). Beim Umfüllen wird Wasser nicht beliebig aufgeteilt; die Stoppregel bestimmt die umgefüllte Menge. Beginnt man mit leeren Krügen, bleiben ganzzahlige Litermengen ganzzahlig. Die Repräsentation enthält 20 ganzzahlige Kombinationen, von denen 14 von (0, 0) aus erreichbar sind.

Den Zieltest über den Erfolg entscheiden lassen

Für „Einer der Krüge enthält 2 Liter“ benötigt ein kürzester Plan vier Aktionen:

(0, 0) → kleineren füllen → (0, 3) → in größeren gießen → (3, 0) → kleineren füllen → (3, 3) → in größeren gießen → (4, 2).

Für „Der 4-Liter-Krug enthält 2 Liter“ besteht (4, 2) den Test nicht. Ein kürzester Plan benötigt sechs Aktionen:

(0, 0) → größeren füllen → (4, 0) → in kleineren gießen → (1, 3) → kleineren leeren → (1, 0) → in kleineren gießen → (0, 1) → größeren füllen → (4, 1) → in kleineren gießen → (2, 3).

Ändert man einige Wörter im Ziel, ändert sich, welcher Endzustand als Erfolg zählt. Bleibt die Reihenfolge im Zustand fest, werden die Mengen in den beiden Krügen nicht verwechselt.

Angaben ergänzen, die reale Aufgaben brauchen

Ein Flugplaner benötigt den aktuellen Flughafen und die aktuelle Zeit. Zulässige Anschlussflüge müssen spät genug für das Umsteigen abfliegen. Tarifklasse oder frühere Teilstrecken gehören ebenfalls in den Zustand, wenn sie künftige Optionen oder Preise beeinflussen. Die Entfernung allein kann ein Ziel nicht darstellen, das Flugpreise, Wartezeit, Flugdauer und Bequemlichkeit verbindet; ein Kostenmodell muss die Zielkonflikte festlegen.

Ein Rundreiseproblem muss sich besuchte Orte merken. Das Problem des Handlungsreisenden sucht eine kürzeste Rundreise, die jede Stadt einmal besucht und zum Ausgangspunkt zurückkehrt; es ist NP-schwer, und für alle großen Fälle ist kein effizientes exaktes Verfahren bekannt. Die Roboternavigation kann kontinuierliche Positionen und Gelenkwinkel benötigen. Der VLSI-Entwurf behandelt die Platzierung und Verbindung von Bauteilen; die Montagereihenfolgeplanung muss festhalten, welche Teile bereits eingebaut sind, weil eine frühe Entscheidung einen späteren Schritt blockieren kann.

Prüfe vor der Suche eine gewöhnliche Aktion und einen Randfall. Ein voller Zielkrug sollte kein weiteres Wasser aufnehmen; ein bereits abgeflogener Flug sollte nicht als verfügbare Verbindung erscheinen. Diese Prüfungen decken fehlende Zustandsinformationen oder widersprüchliche Aktionsregeln früh auf.