FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:   || 2 | 3 | 4 |

«Narratives in the Situation Calculus Rob Miller Murray Shanahan Department of Computing Department of Computing Imperial College Imperial College 180 ...»

-- [ Page 1 ] --

Narratives in the Situation Calculus

Rob Miller Murray Shanahan

Department of Computing Department of Computing

Imperial College Imperial College

180 Queen's Gate 180 Queen's Gate

London SW7 2BZ, U.K. London SW7 2BZ, U.K.

email: rsm@doc. ic. ac. uk email: mps@doc. ic. ac. uk

WWW: http://laotzu.doc.ic.ac.uk/ WWW: http://laotzu.doc.ic.ac.uk/

UserPages/sta /rsm/rsm.html UserPages/sta /mps/mps.html February 1995

Original paper in:

Journal of Logic & Computation, Volume 4, Number 5, October 1994 (Special Issue on Actions and Processes) With addendum added February 1995 Abstract A narrative is a course of real events about which we might have incomplete information.

Formalisms for reasoning about action may be broadly divided into those which are narrativebased, such as the Event Calculus of Kowalski and Sergot, and those which reason on the level of hypothetical sequences of actions, in particular the Situation Calculus. This paper bridges the gap between these types of formalism by supplying a technique for linking incomplete narrative descriptions to Situation Calculus domain formulae written in the usual style using a Result function. Particular attention is given to actions with duration and overlapping actions. By illuminating the relationship between these two di erent styles of representation, the paper moves us one step closer to a full understanding of the space of all possible formalisms for reasoning about action.

Introduction The Situation Calculus 15] is one of A.I.'s oldest and best understood formalisms for representing change, but it has often been criticised for having limited expressive power. Recently, a number of authors have challenged this view, by showing how the Situation Calculus might be used to represent domains with continuous change and concurrent actions 23], 7], 14]. However, the representation of narrative information within the framework of the Situation Calculus has largely been neglected.

A narrative is an actual course of actions (or events1 ) about which we may have incomplete knowledge. One of the features of the Situation Calculus is that it operates at a more


level than that of actual actions. It allows us, for example, to reason about the hypothetical situation which results from the performance of a sequence of hypothetical actions. In contrast, narrative-based formalisms, such as the Event Calculus of Kowalski and Sergot 11], the work of Allen 1] and that of Sandewall 19], operate at the level of actual events. In the latter kind of formalism, it is easy to represent facts about the actual occurrence of events and the properties that actually hold in the world.

The aim of this paper is to bridge the gap between the Situation Calculus and the narrative-based approach. In order to deal properly with narrative information in the Situation Calculus, some extra default reasoning must be used to account for incomplete information about the occurrence of actions, and a number of extra predicates, functions and axioms are required.

The paper is organised as follows. The rst section motivates the paper and describes an example of the kind of reasoning we wish to capture. We then go on to provide predicates, functions and axioms which will link an incomplete narrative description to any set of Situation Calculus domain formulae presented in the usual style using the Result function. Finally we adapt and extend this approach to deal with more complex narratives, involving actions with duration and overlapping actions.

A few words about notation. Throughout this paper, we use a many-sorted rstorder predicate calculus with equality. Variables begin with lower-case letters and constant and function symbols with upper-case letters. All variables in formulae are universally quanti ed with maximum scope unless otherwise indicated. Where we wish to refer to arbitrary predicate calculus terms or expressions, we sometimes use meta-variables beginning with Greek letters. For example, we might refer to arbitrary action terms 1 and 2. Non-logical axioms are labelled with names beginning with an upper-case letter, e.g. the frame axiom `(F1)', whereas derived sentences or expressions are simply numbered | `(1)', `(2)', etc. We use parallel and prioritised circumscription, with predicates, functions and constants allowed to vary (see for example 12]). The parallel circumscription of predicates and in a theory T with and allowed to vary is written as CIRC T ; ; ; ; ] If predicate is also circumscribed, at a higher priority than and, this is either written as CIRC T ; ; ; ; ] or as CIRC T ; ; ; ; ; ] ^ CIRC T ; ; ; ; ] The equivalence of the second expression to the rst is shown in 12].

We use the terms `action' and `event' interchangeably.

1 Incomplete Narratives | An Example Consider the following scenario. Before breakfast one morning, a lecturer, Mary, checks her briefcase to make sure her lecture notes are inside, which indeed they are.

She eats her breakfast, and a short while later carries her briefcase to college. Mary knows that exactly those belongings which were in her case when she left home are at work with her. So she concludes that, at the end of this sequence of event occurrences, her lecture notes are safely at college. However, shortly after she sits down at her desk, her husband telephones to apologise for accidentally removing her notes from the briefcase before she left for work. With her new knowledge of her husband's actions, Mary concludes that her notes are not at college.2 Two main forms of reasoning feature in this story. To begin with, Mary employed a solution to the frame problem to conclude that her lecture notes were at college.

She assumed that her breakfast, whatever other e ects it may have had, did not a ect the whereabouts of the notes, and that they were still in her briefcase when she set o for work. Second, at each stage in her reasoning, Mary assumed that the events she knew about were the only events that took place. That is to say, she used a form of default reasoning to cope with her potentially incomplete knowledge of the actual narrative of events.

We will not be directly concerned here with the frame problem, but rather with the problem of representing and reasoning about incomplete narrative descriptions, in particular in the context of the Situation Calculus. Let's try to represent the lecture notes example in the Situation Calculus. Following the usual practise, there will be sorts in our language for situations (with variables s, s0, s1, etc.), action types (with variables a, a0, a1, etc.) and uents (with variables f, f0, f1, etc.), and the term Result( ; ) will denote the situation which results from performing an action of type in situation. The formula Holds( ; ) represents that uent holds in situation. The situation constant S0 will be used to denote an initial situation.

To represent the lecture notes example, we use three action types: Eat, Carry and Take, denoting respectively the actions of eating breakfast, carrying the briefcase to work and taking the notes from the briefcase. Two uents are needed: Work and Case, denoting respectively that the notes are at work and in the briefcase. The following formulae represent what Mary knows about the domain.

Holds(Work; Result(Carry; s)) Holds(Case; s) (Ex1) :Holds(Work; Result(Carry; s)) :Holds(Case; s) (Ex2) :Holds(Case; Result(Take; s)) Holds(Case; s) (Ex3) Holds(Case; S0) (Ex4) In order to derive useful conclusions from these formulae, we need to add a frame axiom ((F1) below), and to adopt a solution to the frame problem which minimises Ab properly. We will adopt Baker's solution3 3], and will include `existence-of-situations' This story is similar to the Glasgow{Moscow problem described in 16].

We expect our approachto representingnarratives to work equally well with many other solutions axioms ((B1){(B4) below). We also assume that the necessary uniqueness-of-names axioms for uents and actions, and a domain closure axiom for uents, are present.

To brie y summarise Baker, the frame problem is overcome (avoiding such di culties as the Yale Shooting Problem) by minimising the predicate Absit (which appears in Axiom (B3) below) at a higher priority than the predicate Ab, whilst allowing S0 and the Result function to vary. The functions And and Not are used to form `generalised uents' (a super-sort of uents) representing combinations of uents and their negations. Axioms (B1){(B4) together with the minimisation of Absit guarantee that any such combination of uents allowed by the domain theory holds in at least one situation. This is necessary in order to ensure that the minimisation of Ab behaves correctly. (See 3] for details.) Holds(f; Result(a; s)) $ Holds(f; s)] :Ab(a; f; s) (F1) Holds(And(g1; g2); s) $ Holds(g1; s) ^ Holds(g2; s)] (B1) Holds(Not(f); s) $ :Holds(f; s) (B2) Holds(g; Sit(g)) :Absit(g) (B3) Sit(g1) = Sit(g2) ! g1 = g2 (B4) The traditional way to use the above formulae to model Mary's reasoning in the lecture notes example is to show that the formula Holds(Work; Result(Carry; Result(Eat; S0))) is true. But how do we then assimilate the new fact that a Take action took place some time after S0 and before the Carry action? We can of course also prove the formula :Holds(Work; Result(Carry; Result(Take; Result(Eat; S0)))) But we can show this at any time, either before we assimilate the extra Take event or afterwards. Mary's reasoning, on the other hand, is clearly non-monotonic. At rst, she concludes that her notes are at work, but she retracts this conclusion when she learns of the extra Take event. We want to be able to capture this.

The traditional use of the Situation Calculus does not incorporate the idea of a narrative of actual events. For the lecture notes example, and for countless similar examples, we need some way of asserting the fact that an action of a given type actually takes place at a given time. Conclusions about what uents hold when are then no longer expressed in terms of the Result function, they are expressed in terms of narrative time. The next section presents the basis of an approach to the representation of narratives in the Situation Calculus.

to the frame problem, because of our methodology of strictly separating narrative knowledge from domain knowledge.

2 Narratives and the Result Function To make our approach to narratives work, we need to introduce a new sort for times, with variables t, t0, t1, etc. We will consider only interpretations in which this sort is interpreted by the non-negative reals, and in which the comparative predicates (,,, and ) have their usual meanings for real numbers. A new predicate is also required. The formula Happens( ; ) represents that an action of type occurs at time. (Action occurrences are thus instantaneous. Later, we will adapt our approach in order to represent action occurrences with duration.) Finally, a new function is introduced. The term State( ) denotes the situation at time. Now we have the following axiom which forms the link between narrative descriptions and the Result function.

State(t) = Result(a1; State(t1)) (N1) Happens(a1; t1) ^ t1 t ^ :9a2; t2 Happens(a2; t2)^ a1 6= a2 _ t1 6= t2] ^ t1 t2 ^ t2 t]] Axiom (N1) says that the situation at time t is Result(a1; State(t1)) if action a1 happens at t1 and no other action happens between t1 and t. Note that the righthand-side of (N1) is false if an action takes place concurrently with a1 (we assume actions of the same type do not occur concurrently). We will discuss concurrent and overlapping actions in more detail later on.

We also need an axiom to describe the situation that obtains at all times before the occurrence of the rst action within a narrative.

State(t) = S0 :9a1; t1 Happens(a1; t1) ^ t1 t] (N2) A narrative of events is now represented as a set of Happens formulae. The lecture notes example might be rendered as follows.

Happens(Eat; 8) (Occ1) Happens(Carry; 9) (Occ2) Now, in addition to the minimisation we use to solve the frame problem, we need to minimise Happens, representing the assumption that no events occur other than those which are known to occur. We will minimise Happens in parallel with Ab, allowing Result and State to vary. As mentioned above, we include Baker's existenceof-situations axioms in our domain descriptions, and minimise Baker's predicate Absit at a higher priority. For this example it can easily be seen that minimising Happens will not interfere with the minimisation of Ab. The minimisation of Happens will give us the conclusion Happens(a; t) $ a = Eat ^ t = 8] _ a = Carry ^ t = 9]] (1) From this we can derive Holds(Work,State(10)), as shown in Figure 1. But if we now add (Occ3) below, representing the additional fact that a Take action occurred between 8 and 9, we can no longer draw this conclusion.

By (F1), (Ex1), (Ex2), (Ex3) and (Ex4):

Holds(Work; Result(Carry; Result(Eat; S0))) (i)

By (1), (N2) and (i):

Holds(Work; Result(Carry; Result(Eat; State(8)))) (ii)

By (1):

:9a2; t2 Happens(a2; t2) ^ a2 6= Eat _ t2 6= 8] ^ 8 t2 ^ t2 9] (iii)

By (N1), (Occ1) and (iii):

State(9) = Result(Eat; State(8)) (iv)

By (i) and (iv):

Holds(Work; Result(Carry; State(9))) (v)

By (1):

:9a2; t2 Happens(a2; t2) ^ a2 6= Carry _ t2 6= 9] ^ 9 t2 ^ t2 10] (vi)

By (N1), (Occ2) and (vi):

State(10) = Result(Carry; State(9)) (vii)

By (v) and (vii):

Holds(Work; State(10)) (viii) Figure 1 | Derivation of Holds(Work; State(10)) Happens(Take; 8:5) (Occ3) Instead of (1), minimising Happens now gives Happens(a; t) $ (2) a = Eat ^ t = 8] _ a = Carry ^ t = 9] _ a = Take ^ t = 8:5]] With (2), we can no longer prove Holds(Work; State(10)), which is just the outcome we were seeking. (Indeed, we can now derive :Holds(Work; State(10))).

Pages:   || 2 | 3 | 4 |

Similar works:

«Ministry of Education and Science of the Russian Federation Ural Federal University named after the first President of Russia B. N. Yeltsin The Institute of Public Administration and Entrepreneurship Russian society of sociologists Garold E. Zborovsky RUSSIAN SOCIOLOGY: ON THE WAY TO CIVIL SOCIETY Scientific monograph Ekaterinburg 2014 Министерство образования и науки Российской Федерации Уральский федеральный...»

«Accessoires Der Mode Entwurf Herstellung Accessoires Der Mode: Entwurf, Herstellung, Marketing Marketing 10 out an initial plans than originating a services to articulate at the Middle Defaulter referrals with growth is that country of a task cities or the mortgage. Comfortable genre is apart done to realize times look air help or county volunteers in making people. The Coaching Course Mortgage Accessoires Der Mode: Entwurf, Herstellung, Marketing does a new new offering way. They I having to...»

«This rnanuscript has been reproduœd from the microfilm master. UMI films the from the original or copy submitted. text directly Thus, some thesis and dissertation copies are in typewriter face, m i l e others may be from any type of amputer printer. The quality of this reproduction is dependent upon the quality of the copy submitted. Broken w indistinct print, colored or poor quality illustrations and photographs, print bleedthrough, substandard margins, and improper alignment can adversely...»

«Einkaufsbedingungen von MWV (Fassung 1, 2013) 1 Parteien Die vorliegenden Einkaufsbedingungen („EB“) gelten zwischen der MWV Manufacturing Trier GmbH sowie der MeadWestvaco Managment Holding GmbH & Co. KG („MWV“), die Waren oder Leistungen erwirbt (nachfolgend als „Liefergegenstände“ bezeichnet) und dem Lieferanten („Lieferant“), der diese Liefergegenstände liefert (beide als „Parteien“ bezeichnet). 2 Anfrage Von MWV eingeholte Preisoder Angebotsanfragen oder sonstige...»

«Journal of Hebrew Scriptures Volume 14, Article 7 DOI:10.5508/jhs.2014.v14.a7 The Ashkar-Gilson Manuscript: Remnant of a Proto-Masoretic Model Scroll of the Torah PAUL SANDERS Articles in JHS are being indexed in the ATLA Religion Database, RAMBI, and BiBIL. Their abstracts appear in Religious and Theological Abstracts. The journal is archived by Library and Archives Canada and is accessible for consultation and research at the Electronic Collection site maintained by Library and Archives...»

«Digitalisierung im Bundesarchiv Strategie für den Einsatz neuer Techniken der Digitalisierung zur Verbesserung der Zugänglichkeit des Archivguts und zu seinem Schutz 2011 2016 Stand: Feb. 2011 Inhalt: Zusammenfassung Die Perspektive Schwerpunkte einer Digitalisierungsstrategie Der aktuelle Stand Strategische Ziele 1. Verbesserung der Zugänglichkeit und Schutz des Achivguts 2. Erhöhung des Nutzungskomforts 3. Entwicklung von wirtschaftlichen Verfahren 4. Nachhaltigkeit der Maßnahmen Der...»

«Security of Radioactive Sources Proceedings of an international conference held in Vienna, Austria, 10–13 March 2003, organized by the International Atomic Energy Agency, hosted by the Government of Austria, co-sponsored by the Government of the Russian Federation and the Government of the United States of America, and in co-operation with the European Commission, the European Police Office, the International Criminal Police Organization and the World Customs Organization IAEA SAFETY RELATED...»

«AIPPI Association Internationale pour la Protection de la Propriété Industrielle Comité exécutif Annuaire 1985/Ill Conseil des Présidents de Rio de Janeiro 1985 (13-18 mai1985) Rapports administratifs Compte rendu des séances Résolutions et prises de position Congrès de Londres 1986 (8-13 juin 1986) Programme du Congrès Orientation de travail Rapports des représentants de l'AIPPI © AIPPI Zurich 1985 ISBN No.3 9050 2801 8 Edité au nom de I'AIPPI par J. David MEISSER, Klosters...»

«Ausbildung auf Gesundheit u. Sicherheit für Arbeitnehmer in der Umwelt industriellen Sektor 518718-LLP-1-2011-1-GR-LEONARDO-LMP http://www.adam-europe.eu/adam/project/view.htm?prj=8383 Ausbildung auf Gesundheit u. Sicherheit für Arbeitnehmer in der Umwelt industriellen Sektor (518718-LLP-1-2011-1-GR-LEONARDO-LMP) Projektinformation Titel: Ausbildung auf Gesundheit u. Sicherheit für Arbeitnehmer in der Umwelt industriellen Sektor Projektnummer: 518718-LLP-1-2011-1-GR-LEONARDO-LMP Jahr: 2011...»

«2 Marco Polo – Ein Leben zwischen Orient und Okzident Dieter Lohmann Zusammenfassung Siebzehn Jahre war Marco Polo alt, als er 1271 in Begleitung seines Vaters und seines Onkels zu seiner berühmten Entdeckungsreise aufbrach. Von Venedig aus ging es über die Seidenstraße Richtung Osten nach China bis an den Hof des legendären Mongolenherrschers Kublai Khan. Siebzehn Jahre lang stand Marco Polo dort anschließend im Dienste des Enkels von Dschingis Khan und reiste in dieser Zeit kreuz und...»

«Für Mensch-Computer-Interaktion kann man zwei Vorbilder verwenden (Metaphern): • Die Partner-Metapher: Der Computer als Kommunikationspartner (Mensch-Computer-Kommunikation oder Mensch-Maschine-Kommunikation). Der Computer scheint intelligent zu sein und imitiert einen Menschen in seinem Kommunikationsverhalten. Der Computer und der Mensch teilen sich die Kontrolle über die Kommunikation. Sowohl KI als auch CL tendieren hierzu, jedoch gibt es auch kritische Stimmen. Folgende...»

«Table of Contents Shopping for Your New Home 2 Making the Right Choice 3 Choosing the Right Price 6 Down Payment 6 Monthly Mortgage Payment 7 Other Debts 7 Price Range 8 Amortization Schedule 9 Understanding Gross Debt Service (GDS) Ratio and Total Debt Service (TDS) Ratio 10 Checking It Out 11 Comparison Chart 12 Writing the Offer 16 Other Costs of Purchase 18 Shopping for a Mortgage 19 Available Sources 19 It Pays to Shop Around 20 Alternatives Available 20 The Effect of Weekly Payments 21...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.