Propositional Logic Agents

In this section, we will put together everything that has been described so far in order to proceed with the creation of agents acting using propositional logic. There will be two types of agents: first, agents that use logical inference algorithms and a knowledge base similar to the universal knowledge-based agent shown in the listing, and, secondly, agents that calculate the values ​​of logical statements directly using logic circuits. This section will also demonstrate the functioning of both types of agents in the vampus world , and also show that they both suffer from serious flaws.

Search pits and vampuses using logical inference

We begin with a description of the agent, who reasoned logically about where the pits, vampuses and safe squares are located. The agent begins his work with a knowledge base, which describes the "laws" of the world of the vampus. He knows that the square [1,1] does not contain a pit or a vampus; This means that ¬P _1.1 and ¬W _1.1 . For each square [x, y], the agent knows a statement with an indication of how a breeze arises:

B _{x, y} <=> (P _{x, y + 1} v P _{x, y-1} v P _{x + 1, y} v P _{x-1, y} )

For each square [x, y], the agent knows a statement with an indication of how an unpleasant smell arises:

S _{x, y} <=> (W _{x, y + 1} v W _{x, y-1} v W _{x-1, y} )

Finally, he knows that there is exactly one vampus in the world of the vampus. The corresponding statement consists of two parts. First of all, you must specify that there is at least one Wampus:

W _1,1 v W _1,2 v ... v W _4,3 v W _4,4

Then you need to specify that there is at most one vampus. One way of formulating this statement is that if there are any two squares, one of them must be free from vampus. In the presence of n squares, we get n (n-1) / 2 such statements that are similar in form to the expression ¬W1,1 v ¬W1,2 Thus, for the world with dimensions 4x4, the description begins with a total of 155 statements containing 64 different character.

The agent's program, shown in the listing, reports to its knowledge base using the Tell operation about each new perception of the breeze and unpleasant smell. (It also updates some of the usual program variables to track where the agent is and where he was; additional information is given below.) The program then selects among the peripheral squares (i.e., the squares that are adjacent to those that are Already visited agent) such a square, which should be checked in the next turn. An agent can prove that the peripheral square [I, j] is safe if a statement (¬Pi, j ^ ¬Wi, j) follows from the knowledge base. In second place in terms of its attractiveness is the square, which is probably safe; such is a square, in relation to which the agent cannot prove that it has a pit or a vampus, that is, a square for which the following statement does not follow from the knowledge base (P _{i , j} v W W _{i , j} ).

An agent for the world of vampus, using propositional logic to define pits, vampuses, and safe squares. The Route-Problem procedure forms a search problem, the solution of which is a sequence of actions leading from [x, y] to [I, j] and passing only through previously visited squares

function PL-Wumpus-Agent {percept) returns action action

   inputs : percept, a list of perceptual results in the form

[Stench, Breeze, Glitter] (["Bad Breath",

"Breeze", "Glitter"])

   static : KB, a knowledge base that initially contains only definitions

The "laws of the functioning" of the vampus world

x, y, orientation, agent position (initially 1.1) and its

orientation (originally Right - looks

right)

visited, an array showing which squares were visited,

originally containing false values

action, last agent action originally

undefined

plan, intended sequence of actions, originally

empty

update x, y, orientation, visited

with action

if stench then Tell (KB, S ^ .y) else Tell (KB, -iS> c, y)

if breeze then Tell (KB, B *, y) else TelKJCB, -TD.y)

if glitter then action <- grab

else if plan is not empty then action <- Pop (plan)

else   if for some peripheral square [i, j]

Ask result (KB, (—iPifj l -iWij)) is true or

for some peripheral square [i, j] the result

Ask (KB, (Pi, jv ^ i, j)) is false then do

plan <- A * -Graph-Search (Route-Problem ([x, y], orientation,

[i, j], visited))

action <- Pop (plan)

else action <- randomly selected step

return action

The calculation of the logical consequence of the Ask procedure can be implemented using any of the methods described earlier in this chapter. Obviously, the TT-Entails algorithm? It is practically not applicable, because it has to perform a search of 264 lines. The DPLL algorithm performs the required logical inference in a few milliseconds, mainly due to the use of heuristics with the propagation of single expressions. The Walks AT algorithm can also be used, given the usual caveats of incompleteness. In the considered instances of the vampus world, failures in finding a model using 10,000 inversions invariably correspond to impracticability; therefore, the probability of errors caused by the incompleteness of this algorithm is very small.

The PL-Wumpus-Agent algorithm works quite well in the small vampus world. Nevertheless, some features of the knowledge base of the agent remain extremely unsatisfactory. The KB knowledge base contains "literal" statements in a general form, for each individual square. The larger the environment, the larger this initial knowledge base should be. It would be much better to have only two statements that say, because of which there are breezes and odors in any squares. But such expressive possibilities go beyond the framework of propositional logic. The next chapter will show a more expressive logical language in which such statements can easily be presented.

Tracking location and orientation

The agent’s program listed in the listing is a bit "cheating" because it keeps track of whereabouts outside the knowledge base, whereas logical reasoning should be used instead. To perform these functions "properly" will require statements regarding the location. One of the first attempts at solving this problem may be to use some symbol like L _1.1 to denote that the agent is in the square [1,1]. In this case, the initial knowledge base could include statements such as the following:

L _1.1 ^ FacingRight ^ Forward => L _2.1

However, it is immediately found that this method is not applicable. If the agent begins to move from the square [1,1], looking to the right, and moves forward, then the knowledge base will follow the statements and L _1.1 (about its original location), and L _1.2 (about its new location). However, these statements cannot be true at the same time! The problem is that these two statements regarding location should refer to two different periods of time. We need to enter a designation like L _1.1 which would mean that the agent was in the square [1,1] at the moment of time 1, L _2.1 - to indicate that the agent was in the square [2,1] at the moment of time 2, etc. Statements regarding orientation and action should also depend on time. Therefore, the correct statements are the following:

L + ^ FacingRight ¹ ^ Forward ¹ => L _2.1

FacingRight ^ TurnLeft ¹ => FacingUp ²

and similar statements. As it turned out, the task of creating a complete and correct knowledge base, which would allow to monitor everything that happens in the world of vampus, is very complex. And in this section, it suffices to emphasize such an idea that the initial knowledge base should contain statements like those given in the two previous examples for each time point t, as well as for each location. This means that for each point in time t and location [x, y], the knowledge base contains a statement like this:

L ^t _{x, y} ^ FacingRight ^t ^ Forward ^t => L ^{t + 1} _{x + 1, y}

But even if we set the upper limit on the number of permissible time intervals (say, 100), in the end the knowledge base will be filled with tens of thousands of statements. The same problem arises if, for each new time interval, the addition of statements is made “as necessary”. Because of such a rapid increase in the number of statements, the knowledge base becomes uncomfortable for people to read, but fast propositional algorithms — problem solvers are still able to easily cope with tasks in the 4x4 world of vampus (they reach the limit of their capabilities in a world that is approximately 100x100 in size ). Agents based on logic circuits, which are described in the next subsection, provide a partial solution to this problem of rapidly increasing the number of statements.