Das Yale-Schießproblem ist ein Rätsel oder Szenario in formaler Situationslogik, bei dem frühe logische Lösungen des Rahmenproblems versagen. Der Name dieses Problems stammt von den Erfindern Steve Hanks und Drew McDermott, die an der Yale University arbeiteten, als sie das vorschlugen. In diesem Szenario lebt Fred (später als Truthahn bezeichnet) zunächst am Leben, und eine Waffe wird zunächst entladen. Die Waffe zu laden, einen Moment zu warten und dann auf Fred zu schießen, soll Fred töten. Wenn jedoch Trägheit logisch durch Minimierung der Änderungen in dieser Situation formalisiert wird, kann nicht eindeutig nachgewiesen werden, dass Fred nach dem Laden, Warten und Schießen tot ist. In einer Lösung stirbt Fred tatsächlich; In einer anderen (auch logisch korrekten) Lösung wird die Waffe auf mysteriöse Weise entladen und Fred überlebt.
Technisch wird dieses Szenario durch zwei Flüsse beschrieben (ein Fließvermögen ist eine Bedingung, die den Wahrheitswert im Laufe der Zeit ändern kann): und abhängig von der Zeit. Eine direkte Formalisierung der Behauptung des Yale-Schießproblems in der Logik ist folgende:
Die ersten beiden Formeln repräsentieren den Anfangszustand. Die dritte Formel formalisiert den Effekt des Ladens der Waffe zur Zeit . Die vierte Formel formalisiert den Effekt des Schießens auf Fred zur Zeit . Dies ist eine vereinfachte Formalisierung, bei der Aktionsnamen vernachlässigt werden und die Auswirkungen von Aktionen direkt für den Zeitpunkt angegeben werden, zu dem die Aktionen ausgeführt werden. Für Einzelheiten siehe Situationsrechnung.
Die obigen Formeln sind zwar direkte Formalisierungen der bekannten Tatsachen, reichen jedoch nicht aus, um die Domäne richtig zu charakterisieren. In der Tat stimmt mit all diesen Formeln überein, obwohl es keinen Grund zu der Annahme gibt, dass Fred stirbt, bevor die Waffe abgeschossen wurde. Das Problem ist, dass die obigen Formeln nur die Auswirkungen von Aktionen enthalten, aber nicht angeben, dass alle Fluente, die nicht durch die Aktionen geändert wurden, gleich bleiben. Mit anderen Worten, eine Formel muss hinzugefügt werden, um die implizite Annahme zu formalisieren, dass nur das Laden der Waffe den Wert von und nicht der Wert von . Die Notwendigkeit einer großen Anzahl von Formeln, die die offensichtliche Tatsache angeben, dass sich die Bedingungen nicht ändern, wenn sie nicht durch eine Aktion geändert werden, wird als Rahmenproblem bezeichnet.
Eine frühe Lösung des Rahmenproblems basierte auf der Minimierung der Änderungen. Mit anderen Worten, das Szenario wird durch die obigen Formeln (die nur die Auswirkungen von Aktionen festlegen) und durch die Annahme formalisiert, dass die Änderungen der Fluente im Laufe der Zeit so gering wie möglich sind. Der Grund ist, dass die obigen Formeln alle Auswirkungen von Aktionen erzwingen, während die Minimierung die Änderungen auf genau die Änderungen beschränken sollte, die auf die Aktionen zurückzuführen sind.
Im Yale-Schießszenario ist eine der folgenden möglichen Bewertungen der Fluente, bei denen die Änderungen minimiert werden.
Dies ist die erwartete Lösung. Es enthält zwei fließende Änderungen: wird zum Zeitpunkt 3 falsch .
Bei dieser Bewertung gibt es nur noch zwei Änderungen: wird zum Zeitpunkt 1 wahr und falsch zum Zeitpunkt 2. Als Ergebnis wird diese Bewertung als gültige Beschreibung der Entwicklung des Zustands angesehen, obwohl es keinen triftigen Grund gibt, was zum Zeitpunkt 2 falsch ist. Die Tatsache, dass die Minimierung von Änderungen zu einer falschen Lösung führt, ist die Motivation für das Einführung des Yale-Schießproblems.
Während das Problem der Schießerei in Yale als ein ernstes Hindernis für die Verwendung von Logik zur Formalisierung dynamischer Szenarien angesehen wurde, sind seit den späten achtziger Jahren Lösungen dafür bekannt. Eine Lösung beinhaltet die Verwendung von Prädikaten-Vervollständigung bei der Spezifikation von Aktionen: Gemäß dieser Lösung wird die Tatsache, dass das Schießen Fred zum Tode bringt, durch die Voraussetzungen formalisiert: lebend und geladen und Der Effekt ist, dass lebend den Wert ändert (da noch lebte, bevor es wahr war, dies entspricht lebend das falsch wird). Durch die Umwandlung dieser Implikationen in eine -Offikation von werden die Auswirkungen des Schießens korrekt formalisiert. (Prädikate-Vervollständigung ist komplizierter, wenn mehrere Implikationen involviert sind.)
Eine von Erik Sandewall vorgeschlagene Lösung bestand darin, eine neue Okklusionsbedingung einzufügen, die die "Erlaubnis zum Ändern" für einen fließenden Prozess formalisiert. Die Wirkung einer Aktion, die einen Fluss ändern kann, hat daher zur Folge, dass der Fluss den neuen Wert hat und die Okklusion (vorübergehend) wahr gemacht wird. Was minimiert wird, ist nicht die Menge der Änderungen, sondern die Menge der Okklusionen, die wahr sind. Eine weitere Einschränkung, die angibt, dass keine fließenden Änderungen vorgenommen werden, wenn die Okklusion nicht erfüllt ist, vervollständigt diese Lösung.
Das Yale-Schießszenario wird auch durch die Reiter-Version des Situationskalküls, den Fließkalkül und die Aktionsbeschreibungssprachen korrekt formalisiert.
Im Jahr 2005 erhielt das 1985 veröffentlichte Papier, in dem das Yale-Szenario zum ersten Mal beschrieben wurde, die Auszeichnung AAAI Classic Paper. Obwohl es sich um ein gelöstes Problem handelt, wird dieses Beispiel in neueren Forschungsarbeiten immer noch erwähnt, wo es als illustratives Beispiel verwendet wird (z. B. zur Erklärung der Syntax einer neuen Logik, um Handlungen zu begründen) und nicht als ein Problem.
Siehe auch [ edit ]
Referenzen [ edit
- M. Gelfond und V. Lifschitz (1993). Darstellung von Aktion und Veränderung durch Logikprogramme. Journal of Logic Programming 17: 301–322.
- S. Hanks und D. McDermott (1987). Nichtmonotone Logik und zeitliche Projektion. Künstliche Intelligenz 33 (3): 379–412.
- J. McCarthy (1986). Anwendungen der Umschreibung zur Formalisierung des gesunden Menschenverstandes. Künstliche Intelligenz 28: 89–116.
- T. Mitchell und H. Levesque (2006). Die AAAI Classic Paper Awards 2005. "AI Magazine", 26 (4): 98–99.
- R. Reiter (1991). Das Rahmenproblem im Situationskalkül: Eine einfache Lösung (manchmal) und ein Vollständigkeitsergebnis für die Zielregression. In Vladimir Lifschitz, Herausgeber, Künstliche Intelligenz und mathematische Theorie der Berechnung: Papiere zu Ehren von John McCarthy Seiten 359–380. Academic Press, New York.
- E. Sandewall (1994). Merkmale und Flüsse . Oxford University Press.
No comments:
Post a Comment