Introduction

This is the project for the course Multi-Agent systems in the academic year 2016-2017 by Sjaak ten Caat, Denny Diepgrond and Stefan Knegt. We will demonstrate the possibility to model a multi-agent story with epistemic logic.

Problem Outline

For our project, we will be looking at a short story by Isaac Asimov called Little Lost Robot. In this story the main character, Susan Calvin, is tasked with finding a robot among multiple almost identical other robots. The robot she is looking for, is trying to hide actively. This robot, called NS-2, uses all of its knowledge about the other robots to make sure that it reacts in exactly the same way as they do. What is known to everyone is that every normal robot will follow the three laws of robotics, namely:

1. A robot may not injure a human being or, through inaction, allow a human being to come to harm.
2. A robot must obey the orders given it by human beings except where such orders would conflict with the First Law.
3. A robot must protect its own existence as long as such protection does not conflict with the First or Second Laws.

However, NS-2 has been modified in such a way that the First Law only states "A robot may not injure a human being" but will still react in such a way as it thinks other robots will react. Finally, NS-2 is different from other robots due to additional education in that it can distinguish between different types of radiation, for instance between harmless infrared and gamma radiation, which is lethal to robots but safe for humans. It does not realize that the other normal robots do not know the difference. In the end Susan solves the problem as follows: she tells each of the robots separately that gamma radiation will destroy a robot within only a few steps. They are then kept isolated from each other, so that they cannot communicate. Each robot is placed in a large room, with walls between them so that they cannot see each other but they can see the center of the room. This room is filled with infrared radiation. Susan sits in a chair at the center, and once all the robots are in position a large weight is dropped down from above the chair and bumped away from the chair at the last second. Only NS-2 moves from his position, before realizing that none of the other robots moved, and Susan has found her robot. The reason that this worked is that the other robots could not distinguish between different types of radiation. They all thought that they would be unable to rescue Susan before being destroyed by the perceived gamma radiation and so did not act at all. NS-2 however saw that the radiation was safe and thought that the other robots would act in accordance with the First Law, and so was the only robot that did act.

Theory

In the 'Little Lost Robot' story we can identify three separate agents: Susan, the lost robot and the normal robots. The normal robots are all exact duplicates so it is irrelevant how many there are for the purpose of this analysis. Therefore we will only consider one. Let Susan be agent S, the lost robot be agent L, and the normal robot be agent N. Since the story deals with what agents believe, rather than what they know, we used the KD45 system. So we define the model to be used as $M = \langle S, \pi, R^B_S, R^B_L, R^B_N\rangle$. We define the propositional atoms as

• $Gr$ = gamma radiation is present
• $Ir$ = infrared radiation is present
• $Dr$ = dangerous radiation (for robots) is present
• $Hd$ = the situation is dangerous for humans
• $La$ = the lost robot acts
• $Na$ = the normal robot acts

The initial situation is as follows:

• $M\models C (Hd \leftrightarrow Na)$ : It's common knowledge that normal robots will act if and only if a human is in danger.
• $M\models C (B_L(Na) \rightarrow La)$ : It's common knowledge that, whenever the lost robot thinks that the normal robot will act, it will also act.
• $M\models C (B_L(\neg Na) \rightarrow \neg La)$ : It's also common knowledge that when the lost robot believes that the normal robot will not act, it will also not act.

Susan's goal is to find one or more announcements that will result in either the lost robot acting without the normal robot, or the normal robot acting without the lost robot, so that she can identify them. This is not yet possible with the current set of formulas. Then, Susan tells each robot about the effects of radiation, which adds the following formulas:

• $M \models C((Hd \land \neg Dr) \leftrightarrow Na)$ : Normal robots will only act if someone is in danger when there is no dangerous radiation present, since they will not be able to do anything before being destroyed. This rule replaces the very first rule.
• $M \models B_L (Gr \leftrightarrow Dr)$ : The lost robot believes that gamma radiation and only gamma radiation counts as dangerous radiation.
• $M \models B_N ((Gr \lor Ir) \leftrightarrow Dr)$ : The normal robot believes that every type of radiation is dangerous radiation, since they cannot distinguish between different types.
• $M \models B_L (B_N (Gr \leftrightarrow Dr))$ : The lost robot believes that the normal robot also believes that it only needs to be aware of gamma radiation.
• $M \models B_S (B_N ((Gr \lor Ir) \leftrightarrow Dr))$ : Susan believes that normal robots cannot distinguish between infrared and gamma radiation.
• $M \models B_S (B_L (B_N (Gr \leftrightarrow Dr)))$ : Susan also believes that the lost robot believes that the normal robot believes that it is only in danger when there is gamma radiation.

In the resulting models, we can obtain Susan's goal state, $B_S(Na \land \neg La) \lor B_S(\neg Na \land La)$ as follows: $$[Hd \land Ir]B_S(\neg Na \land La)$$

Simulation

The epistemic situation in the above-mentioned story of the Little Lost Robot is simulated below. By using the switches, the user can make propositional atoms that were mentioned in the Theory section either true or false. After changing one or more switches, a new model can be generated by clicking the button on the bottom of the Simulation. In the boxes under a particular agent, the epistemic atoms that are true for the corresponding agent are shown. There also is a box with general knowledge in which the common knowledge in the model is shown. The truth valuations for all agents are based on the initial situation and the formulas given in the Theory section.

We implemented this first simulation to represent the three experiments Susan conducted to find the lost robot in the original story:

Experiment 1 The first experiment she comes up with consists of all the robots seeing a human about to be crushed by a weight. This corresponds with switching the $Hd$ switch to true. The robots are all in a room in which they can communicate so the Communication switch will also be switched to true. The normal robots with a fully implemented First Law have to act to save the person ($M\models C(Hd \leftrightarrow Na)$). Now NS-2 does not have to save the human but does anyway since it beliefs the normal robots will do just that and it does not want to get discovered ($ M\models C(B_L(Na) \rightarrow La)$). This shows that the lost robot is actively trying to hide and Susan needs to come up with something smarter to identify NS-2. In the simulation, the "Settings experiment 1" button can be pressed to give the atoms the values corresponding to the situation in experiment 1. After this, the button on the bottom of the simulation can be pressed to see what the beliefs of the agents are.

Experiment 2 The second experiment Susan comes up with is very similar to the first one, the only difference is that a beam of gamma radiation can now be found between the robots and the human. This corresponds with switching the $Gr$ switch to true. Because the First Law (save humans) is more powerful than the Third (save yourself), the normal robots should leap to save the person, even if it means their death. The lost robot however, lacks the "save humans" command, so it should be ruled by the Third Law and stay seated. Nevertheless, when running the experiment they find out that all robots now do nothing since one of the robots has pointed out that they couldn't save the human and if they stayed seated, they might save a human sometime in the future ($M \models C((Hd \land \neg Dr) \leftrightarrow Na)$). This shows that the communication between the robots is a problem and that the lost robot can make the other robots reinterpret their First Law. In the simulation, the "Settings experiment 2" button can be pressed to give the atoms the values corresponding to the situation in experiment 2. After this, the button on the bottom of the simulation can be pressed to see what the beliefs of the agents are.

Experiment 3 After this, Susan tries to solve the problems of the first two experiments by running the third experiment as explained in the Problem outline. To solve the problem of the first experiment, Susan now puts infrared beams between the robots and the human. This corresponds to switching off the $Gr$ switch and switching on the $Ir$ switch. To solve the problem of the second experiment, Susan places the robots in a large room, with walls between them so that they cannot see each other but they can see the human in the center of the room. This corresponds to switching off the Communication switch. When they run the experiment, all robots stay seated except for NS-2 leading to Susan finding out which robot is the little lost robot. Since NS-2 was the only robot with enough knowledge of physics to see the difference between gamma radiation and infrared radiation ($M \models B_L (Gr \leftrightarrow Dr)$), it is the only one to know that the infrared radiation is not dangerous ( $M \models B_N ((Gr \lor Ir) \leftrightarrow Dr)$). It does also not know that the other robots do not have this knowledge and it does therefore not see a reason not to save the human ($M \models B_L (B_N (Gr \leftrightarrow Dr))$). In the simulation, the "Settings experiment 3" button can be pressed to give the atoms the values corresponding to the situation in experiment 3. After this, the button on the bottom of the simulation can be pressed to see what the beliefs of the agents are.

Feel free to experiment with other settings that do not correspond with Susan's experiments to see how the agents use the epistemic logic in the system. An extended simulation with additional functionalities can be found in the section below.

Settings experiment 1

Settings experiment 2

Settings experiment 3

Communication

False True

Gamma radiation

False True

Infrared

False True

Human in danger

False True

General

Lost Robot

Normal Robot

Susan

Generate new model

Extended Simulation

We have also created a separate simulation with some additions to the original simulation. We will first give a brief summary of each addition, as well as how it changes the simulation.

1. Allow Susan to tell each robot what they should perceive as dangerous. In the original experiment, Susan warned both robots about the dangers of gamma radiation. In this simulation, we give the user control about what Susan should tell each robot what they should watch out for. For instance, to simulate the original experiment, the user would check "gamma radiation" for both the lost robot and the normal robot. The same difference between the lost robot and the normal robot remains, so normal robots are still unable to distinguish between different types of radiation. This means that warning the normal robot about either gamma radiation or infra-red, will result in the robot seeing both as dangerous. On the other hand, selecting only infra-red for the lost robot has the consequence that it will still act if there is gamma radiation present, and the same applies if the lost robot is warned about gamma-radiation and infrared is present. This can be expressed in the formulas $M \models B_N((Gr \rightarrow Dr) \leftrightarrow (Ir \rightarrow Dr))$, which replaces $M \models B_N ((Gr \lor Ir) \leftrightarrow Dr)$ in the original situation, $M \models \neg B_L((Gr \rightarrow Dr) \leftrightarrow (Ir \rightarrow Dr))$, which replaces $M \models B_L (Gr \leftrightarrow Dr)$, and finally $M \models B_L(\neg B_N((Gr \rightarrow Dr) \leftrightarrow (Ir \rightarrow Dr)))$, which replaces $M \models B_L (B_N (Gr \leftrightarrow Dr))$. Susan is still aware of these differences, so we also replace $M \models B_S (B_N ((Gr \lor Ir) \leftrightarrow Dr))$ and $M \models B_S (B_L (B_N (Gr \leftrightarrow Dr)))$ with $M \models B_S (B_N((Gr \rightarrow Dr) \leftrightarrow (Ir \rightarrow Dr)))$ and $M \models B_S(B_L(\neg B_N((Gr \rightarrow Dr) \leftrightarrow (Ir \rightarrow Dr))))$. This changes the goal state, as it is no longer enough for one robot to act differently than the other robot, since this could be explained by the difference in what they were told beforehand, rather than one robot actually being the lost robot. Instead, Susan will now have to reason for both robots if their reactions, given what they are told, is consistent with how the lost robot would act and how a normal robot would act. Then, if a robot's response is not consistent with that of a normal robot, it must be the lost robot. Also, if a robot's response is not consistent with that of the lost robot, then the other robot must be the lost robot. We first change the axiom $Dr$ to $Dr_{(x,i)}$, which now means "The situation is dangerous according to robot i if it were agent x", with x and i being either the lost or the normal robot. Then, we can represent the goal states as the formulas $B_S((Dr_{(La,Na)} \land La) \lor (Dr_{(Na,La)} \land Na))$ as well as $B_S((\neg Dr_{(La,Na)} \land Hd \land \neg La) \lor (\neg Dr_{(Na,La)} \land Hd \land \neg Na))$. In the first case, one of the robots reveals their identities by acting when the other robot wouldn't have, while in the second case it does so by not acting when the other would have.
2. Allow more normal robots to be created Without the first addition, this feature would change nothing since each normal robot would act the same way. However, if Susan were to tell each robot something different, then they will act different as well. This changes when Susan can identify the lost robot. Where before it would have been enough if one normal robot acted in a way that it could not be the lost robot, this is no longer true if there are two or more normal robots, since there would still be two or more robots that could potentially be the lost robot. Instead, every normal robot should act in a way that the lost robot would not, so that the lost robot can be identified by process of elimination. However, it is still enough if the lost robot acts unlike how a normal robot would act.
3. Allow different scenarios We've added two extra scenarios, which both change the difference between what the lost robot believes and what the normal robots believe. The user can select the desired scenario using a drop-down menu. The first option is the original problem, in which the lost robot can distinguish between infra-red and gamma radiation, while the normal robots cannot. When choosing the second option, the lost robot will infer that, should gamma radiation be present, then electricity is present as well, while also assuming that the other robots believe this as well, and Susan is again aware of this difference. So we add the rules $M \models B_L(Gr \rightarrow El)$, $M \models B_L(B_N(Gr \rightarrow El))$, $M \models B_S(B_L(B_N(Gr \rightarrow El)))$ and $M \models B_S(\neg B_N(Gr \rightarrow El))$, where $El$ stands for "electricity is present". These replace the rules $M \models B_N((Gr \rightarrow Dr) \leftrightarrow (Ir \rightarrow Dr))$, $M \models \neg B_L((Gr \rightarrow Dr) \leftrightarrow (Ir \rightarrow Dr))$, $M \models B_L(\neg B_N((Gr \rightarrow Dr) \leftrightarrow (Ir \rightarrow Dr)))$, $M \models B_S (B_N((Gr \rightarrow Dr) \leftrightarrow (Ir \rightarrow Dr)))$ and $M \models B_S(B_L(\neg B_N((Gr \rightarrow Dr) \leftrightarrow (Ir \rightarrow Dr))))$ . In the third scenario, only the lost robot believes it should always act when a human is in danger, regardless of the dangers present. So this scenario replaces the rule $M \models C((Hd \land \neg Dr) \leftrightarrow Na)$ with $M \models B_N((Hd \land \neg Dr) \leftrightarrow Na)$, $M \models B_L(Hd \leftrightarrow Na)$, $M \models B_S(B_N((Hd \land \neg Dr) \leftrightarrow Na))$ and $M \models B_S(B_N(Hd \leftrightarrow Na))$.

Epistemic Analysis

We model theory of mind-properties for the agents with the KD45 system and added beliefs. The idea of bridging cognitive science and logic, by using dynamic epistemic logic to model theory of mind is not new (Verbrugge, 2009). Pol et al. (2016) used dynamic belief updates in a computational-level model of theory of mind. This way they formalize the aspect of theory of mind regarding the attribution of mental states. In the model they focus on epistemic states, in particular on belief. Our model is based on their approach. The most important difference is that in our model, the belief updates will not be based on sequences of actions but on public announcements that change the beliefs of the agents.

Kripke Model

In the figures below, Kripke models can be created that display the epistemic situation corresponding to the state of the system after certain public announcements. To start or reset the creation of Kripke models, press the "Generate new Kripke model" button.

With the epistemic information provided in the Theory section, 11 possible world can be constructed. In the legend, these 11 worlds are shown with the corresponding truth values for the propositional atoms. In the other three frames we show the epistemic relations between the possible worlds for all agent types. By selecting different announcements to be made among the blue buttons, the user can update the Kripke model accordingly. The main challenge when constructing the Kripke model is the large amount of worlds that could be considered. As there are 6 axioms, which could each be true or false, there are $2^6=64$ possible worlds. However, many of these worlds are irrelevant considering the general knowledge of the agents. For instance, in a world where gamma radiation is true, everyone believes that the radiation is dangerous to the robots, and so none of the robots will act.

Conclusion

We have shown that it is possible to model a multi-agent story like "the Little Lost Robot" by Isaac Asimov with epistemic logic based on belief updates. This project was not only intended to demonstrate the possibility of modeling theory of mind-stories using dynamic epistemic logic. By guiding the user through the system using simulations, the functioning of the epistemic logic framework can be made clear for people with basic knowledge of modal logic.

References

Isaac Asimov. Little lost robot. Astounding Science Fiction, 39(1):111–132, 1947.

J-J Ch Meyer and Wiebe Van Der Hoek. Epistemic logic for AI and computer science, volume 41. Cambridge University Press, 2004.

Hans Van Ditmarsch, Wiebe van Der Hoek, and Barteld Kooi. Dynamic epistemic logic, volume 337. Springer Science & Business Media, 2007.

Pol, I., I. J. E. I. van Rooij, and J. Szymanik. "Parameterized complexity results for a model of theory of mind based on dynamic epistemic logic." (2016).

Verbrugge, Rineke. "Logic and social cognition." Journal of Philosophical Logic 38.6 (2009): 649-680.