Logical Agents and Entailment in Knowledge Bases | AI Tutorial

[00:00:00]So in this video I'm going to talk about logical agents. Okay. So the basic actions of a logical agent uh are tell and ask.

[00:00:11]A logical agent is a is an agent that trusts a knowledge base to keep track of things. Okay. And you can tell facts or ask for other inference. Right? So for example, you can tell the agent that father the father of John is Bob. You can tell the agent that Jane is John's sister and you can tell the agent that Jon's father is the same as John's sister's father. So then you can ask who is Jane's father. And the idea is that this logical agent will infer based on these facts that it has been told.

[00:00:46]It will infer who's Jane's father. It knows the relation knows the father of John is Bob and knows that Jane is John's sister. So so far it seems like the father of Jane might be Bob. It also knows that John's father is the same as John's sister's father. Right? So we ask who's John's sister's John's sister um and that is Jane. So then the father of John is the same as John's sister's father. So you ask and that is Bob. And that is an inference. What I just did here is an inference. So the idea of intelligent agent again is an agent where you can tell a lot of facts and via logic you can ask for a question and via inference it can provide the answer to that question. Now the main components of a knowledge based agent uh are a knowledge based an knowledge base so all these facts a knowledge representation language we might not be able to to tell naturally hey Jane is John's sister or is the same as John's sister's father we need some kind of language that abstracts those concepts we need an engine that performs inference of some of some sort um and we have to have a background knowledge about the world that we put in the knowledge base at every step. The idea is that our intelligent agent will construct a sentence or or one of these facts with assertions about the the percepts, right? So, it senses something and it will tell a fact to uh its knowledge base. Then it'll construct a sentence asking what action is next. It will basically it will tell the new perception. I will ask what do I do next given these facts? What do I do next?

[00:02:37]And then uh say the uh and say the response the response will be an assertion something that it inferred. Okay. When we talk about constructing a sentence is that we construct a sentence in the language of our abstraction for the knowledge base.

[00:02:55]We're going to look at an example of this with the uh Was World. The Was World is a it was an old uh almost textbased game u and it'll and it'll serve to illustrate uh this logic although it's far uh more simple than many of the games uh many of today's games it's a good example.

[00:03:20]So the Was world is first a grid. Okay, it's a grid. All the adjacent rooms are connected horizontally or ver vertically. Now, in the cave, there is a wimpus, this monster, and the players can smell the wimpus because it emits a stench. The players feel a breeze if a pit is nearby. Oh, what do pits have to do with this? Well, some room contain uh some rooms contain pits that will trap a player. So, it's good that you feel a breeze before it because everything is dark. Then a player can shoot one arrow and kill the wimpus or he can shoot it and not kill the wampus, but that's the only arrow you have. And one of the rooms contains a pot of gold, which is the prize. Otherwise, you're just off for a very uh gloomy game with no winning at all. So, the grid might look like this. You might have, for example, randomly put pits and the gold here and then the wimpus is lurking over here. So then these adjacent squares feel a stench. If there's a pit here, the adjacent squares feel a breeze and a breeze, right? There's a pit here, adjacent breeze, and breeze, and so on and so forth. And you start at square one, one, the player.

[00:04:36]Now, let's look at the formulation of performance, environment, actuators, and sensors. The performance measure, let's say that we're going to give them 1,000 points for walking out with the gold. So if you get the gold and walk out, that's good. uh negative 1,000 if you die.

[00:04:53]That's basically you lose everything.

[00:04:55]Negative one for each action and negative -10 for an arrow thrown because if you throw the arrow and you kill the wimpas, you have a higher chance of getting the goal. But if you throw the arrow and do not kill the wimpas, there's a significant penalty. Now, there's negative one for each action.

[00:05:10]Basically, what this says is every time we move, there's a little penalty. So, we want to find the goal as quickly as possible, right? In the least amount of moves. The environment is going to be a 4x4 grid. We'll start at 1 one and the golden pit will be randomly distributed.

[00:05:26]And the actuators is basically the agent can move forward, left or right or backwards. And the sensors the the agent can sense smell, breeze, glitter, uh um a bump or a scream.

[00:05:40]If the if if the player screams, then you know it it was killed, right? And if it bumps, then it hits a wall.

[00:05:53]All right, let's look at what the player will be feeling at each step here. The player starts at 1 one. A is the agent or the player in this case starts at 1 one doesn't feel anything. The sensors are none. None. None for for smell. None for uh breeze.

[00:06:12]None for um sorry glitter. Oh, gold. Okay. So, and then we have a little notation here. So, we know that these squares are okay because there's no adjacent anything and we're fine.

[00:06:30]Next time we move to 21. The agent moves to 21 over here. So, it went from here to here. This we mark okay. This we mark with a V for visited. And then we go here and it's okay. But there's a breeze and our sensors are non breeze. None none none.

[00:06:49]So the question is is there a pit here or a pit can be here or here? Right? Those are dangerous places. So then we start marking this and maybe we go up and then back to one two. We might end up in a in a board like this. We went up and then back here for example, we found that this was okay. Because this was okay and there was no breeze. We know the pit was here, right?

[00:07:18]This is how we're inferring the next the next move, okay? Or the next the next assertion. So as we move here, there's no breeze. Then we tell the knowledge base there is no pit here.

[00:07:29]As we move here, we we uh we have a stench, right? We feel a stench. Here's the sensor. Stench is turned on. We have a stench, right? So, we know and then and then we hear a stench. So, we know that there's a stench in this square.

[00:07:44]Now, the question is what to do next, right? We know we tell the knowledge base of the Olympus is here because there's no other place where it can be.

[00:07:52]Okay? And that's how we tell our knowledge base and ask for the next action at each step.

[00:08:00]Right? So then the agent comes back here and then back here and it happens to have the gold there. There's a breeze so it doesn't know whether there's a pit here or a pit here, right? To get out and there's a stench. So the sensors are stench, breeze, glitter, none none, right? I haven't fallen. I haven't um I haven't uh been caught by the wimpus. So this is how my knowledge base now is this grid. It's forming as I tell it facts about my world as I explore it.

[00:08:31]So that is the concept of a logical game and knowledgebased agent. Another uh two more slight uh important I mean two more things that I think are important are the following. First a logic has a syntax. For example uh x + 4= 6. This is this is good math syntax. Right now if I do 4x= 6 plus this is not a valid math syntax. The in the same way the logic of our knowledge base will have a syntax. We'll talk about that in a different video. The semantics of my logic will define the truth of a sentence of an assertion.

[00:09:10]Okay? The way the semantics are the meaning whether this the assertion is true or not. And here's what I want to talk about last. The models describe possible worlds. So for example, I have a model here.

[00:09:26]Here's a model of what I think the grid looks like. Right?

[00:09:30]So the model describe possible worlds.

[00:09:32]This is this is one model, right?

[00:09:34]Another model probably has doesn't have a pit here, doesn't have a breeze here.

[00:09:38]Who knows, right? Or another model might have a pit here, which is irrelevant to my game, but it might be another model.

[00:09:45]So model describe possible worlds.

[00:09:48]Uh model of alpha is the set of all models of alpha. Okay, alpha being um a sentence. For example, ex um uh say say my model my model is uh um uh 4x equals uh 8 for example that's a model well alpha can be just the number two here now if I have another model for example x y = zero.

[00:10:26]Okay. Now, m of alpha is the set of all the models of alpha, right? So, x can be one, y can be three. This model doesn't not true, right? But other things can be x is zero, y is 7, x is zero, y is y is 1,325.

[00:10:45]Whatever models, right?

[00:10:48]Whatever models I put here are alpha.

[00:10:52]Okay? Each model is alpha and m of alpha is the set of all models okay that for this for this sentence for example right m of alpha is the set for all models of this sentence some will be true some will be false now if a sentence in alpha is true for model m alpha satisfies m for example let's look at this model okay if a sentence is true for this a sentence will be say for example x = 0 and y = 12. I just came up with those numbers, right? But this model satisfy is true.

[00:11:32]This this model alpha is true. I'm sorry. This this sentence is true for this model. Okay. Then we can say that alpha satisfies this model. Okay. I can make it more logically dependent. And I can say x= 0 and y = 12 satisfies this model. Okay, x = 1 and y = 12 does not satisfy the model.

[00:12:01]Now we're going to talk a little bit about entailment. This is the last concept we'll cover in this video.

[00:12:06]Entailment is when a sentence follows from another. We say alpha entails beta.

[00:12:11]Alpha entails beta. If in every model where alpha is true, beta is also true.

[00:12:17]This is the most important thing. So we know that basically the model the all the models of alpha are more specific than the models of beta are beta and then some more specific circumstance.

[00:12:29]Right? So for example x equals 0 entails xy equals z because in everywhere everywhere where x is true in this case zero this model beta is also true.

[00:12:43]Basically x=0 is a special situation of beta right of the models of beta.

[00:12:50]Therefore, it entails it.

[00:12:55]Uh if I say P equals true and then there's another model sub beta for P or Q. Well, wherever alpha is true, beta will also be true. Right? So if P is true, beta will also be true. If P is true, right?

[00:13:11]So every model where alpha is true, beta will also be true. Beta contains more things. It's more general, right? But alpha is more specific. And wherever alpha is true, beta is also true. Now, here's a trickier one that I'm going to attempt to explain, but you can you can uh continue um trying to understand.

[00:13:33]This is one of the tricky situations where false and trail and tails true.

[00:13:37]Imagine beta is true always, always, always, always. Now imagine alpha is false sometimes, but true sometimes.

[00:13:48]If alpha is false sometimes but true sometimes those instances in which it is true well beta will also be true because beta is true for everything. Now let's say alpha is false that means that there's no way in which alpha is true but beta will always be true right so if you ever were to find any true circumstance here alpha will always be true alpha I mean beta will always be true beta is everything and alpha is nothing actually entails everything that's what we're trying to say Now P and Q entails P or Q. What this is saying is that P and Q is more specific than P or Q. But P or but the case in which this is true, this will also be true. So the case in which alpha is true, which is P true and Q true. Well, beta is also true. If you put true here, true here, right? This will be true. So they don't produce the same output. But where this is true, this guy here will al always be true.

[00:14:59]Um if I say uh P if and if if and only if Q or R that entails Q implies P.

[00:15:09]Okay, you can use logic tables to find that out. In the same way you can you can say uh Q implies P entails uh in the same way I want you to find out actually if Q implies P entails P if and if and only if Q or R okay that's something for you to prove you can use truth tables for this okay another one for example if X we have XY such that X and Y are part of the Brady Bunch a TV series an American TV series with six uh siblings. Okay, if X and Y are part of the Brady bunch and they're not the same person. Okay, that entails X and Y such that X is a relative of Y. Okay, X and Y this is such that X is a relative of Y. So the people in the Brady bunch are a subset of all people that are relatives among themselves.

[00:16:06]That's what this is saying. And this entails uh the other Now let's look at the Wus world that we had uh earlier. Right? So this Wus world here actually in particular this situation. Let's look at this situation in Wus World. I'm here and I want to know where's the pit. So I'm going to try and model all possible pits in here. Right? So my model will contain things like there's a pit here and a pit here. There's a pit here and not here but yes here. all all possible combinations of pits here. We're going to try and find where are the pits using this technique. So I'm going to try and draw all the places where two pits can be uh where there can be pits in these all combinations of pits in this uh area. So here they are right. I have one pit here. Another one has a pit over here. Another one has pits on the corners. Another one has all three with pits. Another one has all three without pits and so on and so forth. These are all possible combinations.

[00:17:10]Okay. Now what I want to answer is is it true that there are no pits in one two is this this space over here. Okay. Is it true? So I I'm going to take all the models that do not have a pit in one two basically this model right this model this model this model. and those are going to be in my knowledge base, right?

[00:17:31]But this model also doesn't have any pits in one two, right? But it's not part of my knowledge base because I feel a breeze and I know the rules of the game. Therefore, I know that there there are going to be, you know, there's going to be a pit somewhere, right? Or at least at least one pit somewhere. So what we can say is is if alpha one alpha one are uh are all the models that do not have a pit in one two. I know that my knowledge base entails alpha 1.

[00:18:03]My knowledge base is a specific case of alpha one. Okay. So we're good. We're we're good to go. Okay. So I can say yep you know if there are no pits in in there are no pits in one two. This seems to be true because what I know about the world, what I've told with facts in my knowledge base uh uh complies with it entails alpha 1.

[00:18:27]Now on the other hand, if you were to say, well, is there are there no pits in 22? So, I'm going to explore 2 two, right? So, these are all the models with pits in the area that I'm exploring.

[00:18:38]Now, no pits in 22 have these. This does not have pits in 22. This one and this one, right? But my knowledge base because of the rules of the game, I know that the pit is here or here, right? So my knowledge base also includes this case, right? That I know that this might be a fact. I know that this other one might also happen, right? So my knowledge base in this case does not entail alpha 2, which is basically no pits in 22, right? So now my knowledge base does not entail alpha 2. My knowledge base is not a specific case of alpha 2. So if I ask my knowledge base are there no pits in 22 it will create all the models. It will look at what it knows and it will and it will say that you know what what I know does not entail what you're asking. So therefore no it's false. Okay it is false that there are no pits in 22. On the other case, the question was are there no pits in one two? Well, I model all the cases in which there are no pits in one two. I look at my the cases in my knowledge base and they entail the no pits in one two.

[00:19:53]Therefore, I can say true. Okay. And that is uh entailment in logical agents.