These problems are modified from the exercises in the Davis book.

Problem I:

Consider the following microworld. There are light bulbs, sockets, and switches. Each socket is controlled by exactly one switch; each switch controls exactly one socket. The following states are significant: A light bulb may be in or out of a socket; a light bulb may be shining or dark; a light bulb may be working or burned out, a switch may be on or off. The following events are significant: A switch may be turned on or off, a light bulb may be inserted or removed from a socket; a light bulb may burn out.

1. Formalize this problem in the situation calculus, using the Reiter-syle formalism of the Davis blocks-world handout.

You will need to specify

• state coherence axioms or domain constraints (e.g., only one bulb can be in a socket at a time)
• feasibility axioms (e.g., it is possible to insert a bulb into an empty socket)
• causal rules (e.g. inserting a bulb into a socket will result in the bulb being in the socket)
• frame axioms, specifically explanation closure axioms (e.g., the only actions that change the position of a switch are turning the switch on or off)
• unique names assumptions

2. Assume that in the starting situation, there are exactly two sockets and exactly two bulbs. (Thus there are exactly two switches as well.) One socket is empty and one socket contains a burned out bulb. Both switches are turned off. Formalize the starting situation in the situation calculus. (To a large extent, this is just a matter of writing axioms of the form Holds(S0,fluent), for the various fluents that are true in the starting situation. You will also have to add domain closure assumptions: assumptions which state that there are no more than 2 switches, no more than 2 sockets, no more than 2 bulbs. An example of a domain closure assumption can be found here.)

Give a plan (sequence of actions) which will result in a light bulb shining. Prove that the plan will work.

3. Formalize the light-bulb world in STRIPS, as far as possible. (Recall that STRIPS is discussed in Section 5.7 of Davis's book; also look at Figure 5.11.)

One difficulty you will have to deal with is the fact that STRIPS can't deal with conditional actions; actions which have different effects depending on the starting situation. Turning on a switch is an example of a conditional action since whether or not a bulb is shining as a result of this action depends on whether there is a working bulb in the socket controlled by the switch. The way to deal with this in STRIPS is to split each action type into two or more action types; and to specify different sets of preconditions for the different action types.

Now assume the starting situation above, and give a plan in STRIPS analogous to the plan given for the situation calculus. Show that your plan will work. (That is, show the state at each point in the plan.)

Problem II:

Consider a modified light-bulb world where there are multiple agents working synchronously. This means that more than one agent can operate at a time, but with certain restrictions. Specifically, time is divided into a sequence of units, and in any unit of time, an agent can turn on a switch, turn off a switch, insert a bulb, remove a bulb, or wait. (The wait action is needed because when not all agents are acting, the actions of the other agents generally need to be represented as wait actions.) As before, a bulb can also burn out. We don't normally associate an agent with a bulb burning out, but for the sake of uniformity, it is convenient to associate one extra agent (sometimes called Nature) to formalize actions that "just happen."

There are certain restrictions on how agents can interact. In general, interfering actions are not allowed. Two agents cannot be involved with the same switch at the same time, or with the same bulb at the same time. Part of the challenge in formalizing domains which allow simultaneous action is figuring out which actions interfere with one another.

1. Axiomatize this revised world in Reiter-style situation calculus. You will need to change the formal language and to modify the axioms.

Changing the formal language: To deal with combinations of simultaneous actions, you will need to consider both single actions and combined actions (a combined action represents several actions occurring together). You will need to extend the function Result: the function Result(s,combined_ act) now takes a combined action as its second argument. You will need a function action_of(agent,combined_act) which maps an agent and a combined action to the particular action that the agent is performing. It may also be useful to have a function which maps a set of single actions into a compound action. You will also have to do one of the following: add an extra parameter to each action for the agent performing the action, or introduce a new function do(agent,action) which maps an agent and a simple action into a simple action. (In all cases, the particular names used for the new functions are just suggestions and are not mandatory.) Depending on the domain and the formalization of that domain, this sort of change may require adding parameters to one's fluents as well.

Modifying the axioms: Some modifications are relatively trivial, and mostly involve syntax. However, some real changes will need to be made. You may have to modify causal axioms, and you will need to modify feasibility axioms. In particular, you will need to list the combinations of actions that interfere. You will have to do one of the following: either modify feasibility axioms so that a combined action is not possible if it contains interfering actions or modify causal axioms so that a combined action does not have the desired effect if interfering actions are performed. Sometimes a combined strategy is more useful. For this exercise, modifying feasibility axioms is probably the easiest method.

2. (Preventing undesired effects:) In the real world, an agent (mildly) burns its hands if a switch is turned on while the agent is inserting a bulb in a socket. Formalize this in the new axiomatization.

• Specify how you are changing the formal language, and what fluents and axioms need to be changed or added.
• Assuming the starting situation of Problem I, but add the fact that there are exactly two agents and that no agent has burnt hands. Give a plan which results in a bulb shining and an agent burning its hands. Prove that the plan will have these results.
• How can you change the formalization to ensure that the agent's hands are not burnt? What axioms need to be changed or added?
• Prove that the plan given in Problem I will not result in any agent's hands being burnt.

Back to web page for KR course