Open access peer-reviewed chapter

Predicate Calculus as a Tool for AI Problems Solution: Algorithms and Their Complexity

By Tatiana Kosovskaya

Submitted: July 16th 2017Reviewed: November 28th 2017Published: August 29th 2018

DOI: 10.5772/intechopen.72765

Downloaded: 310

Abstract

The chapter is devoted to the use of predicate calculus for artificial intelligence (AI) problem solving. Here, an investigated object is represented as a set of its elements and is characterized by a fixed number of predicates. Its description is a set of all constant literals (with the chosen predicates), which are valid on the object. The NP-complete problem, “whether an object satisfies a goal formula,” is under consideration. The upper bound of number of its solution steps is exponential. The notion of common up to the names of arguments subformula of two predicate formulas and one of their isomorphisms allows to construct a level description of the set of goal formulas and essentially to decrease the upper bounds of the problem solving. The level description permits to define a self-training predicate network, which may change its configuration during the process of training. The extraction of common up to the names of arguments subformulas permits to construct a multiagent description of an object when every agent does not know the true number of the object elements and uses her own notifications for the names of elements. A model example illustrating all algorithms is presented.

Keywords

  • predicate calculus
  • NP-completeness
  • level description
  • predicate network
  • multi-agent description

1. Introduction

The choice of initial attributes for description of an object in an artificial intelligence (AI) problem is the first stage of any simulation of an informational process (representation of information for its further use).

At the 60–70th of the twentieth century, many authors (see, for example, [1]) offered to use predicate calculus for AI problem solving. The resolution method seemed to be a very easy and clear tool to solve problems dealing with compound objects, which can be described by properties of its elements and relations between these elements.

Until the notion of NP-complete problem (in particular, described in [2, 3]) was not widely adopted, such an approach seemed to be very convenient, but many such-a-way formalized problems occurred to be NP-complete or even algorithmic unsolvable.

While developing the effective algorithms deciding discrete problems, determination of estimations for number of steps of their run becomes one of the important problems. The absence of the proved estimations for number of an algorithm run steps is considered as an insufficient research of this algorithm. It is especially relevant for problems with big input. It concerns, in particular, to the algorithms deciding various AI problems. At practical use of an algorithm, it is important that it has polynomial upper bound of number of its run steps. The NP-completeness or NP-hardness of a problem means now that the polynomial algorithm of its decision is not known.

In 2007, the author proved NP-completeness of a series of AI problems formalized with the help of predicate calculus formulas [4], proved upper bounds for number of steps of algorithms solving these problems [5], and offered a level description of goal formulas for decreasing the number of proof steps [6]. Such a level description is based on the extraction of a common up to the names of its arguments sub-formula of the set of elementary conjunctions of atomic predicate formulas. These sub-formulas define generalized characteristics of an object.

Extraction of such sub-formulas allows to construct logic-predicate networks [7], which may change its configuration (the number of layers and the number of cells in the layer) during the process of training.

Extraction of these sub-formulas may serve as an instrument for constructing a multi-agent description of an object, when every agent can describe only a part of the object (these parts are intersected), but every agent gives its own names to the elements of the whole object [8].

Here, some AI problems formalized in such a way are under consideration. For these problems, the solving algorithms and upper bounds of their run are obtained. These upper bounds permit to point out the parameters of the problem, which mostly influence on the complexity of the algorithm, and to offer approaches permitting to decrease the complexity.

A model example illustrating the described approach and algorithms is given.

2. Logic-predicate approach to some AI problems and number of steps of these problems solution

Let an investigated object be presented as a set of its elements ω = {ω1,, ωt}. The set of predicates p1,, pn (every of which is defined on the elements of ω) characterizes properties of these elements or relations between them. Logical description S(ω) of an object ω is a collection of all true formulas in the form piτ¯or ¬piτ¯(where τ¯is an ordered subset of ω) describing the properties of ω elements or relations between them.

Let the set Ω of all investigated objects be a union of classes Ωk, (k = 1,, K), i.e., Ω = k=1KΩk. Logical description of the class Ωk is such a formula Akx¯that if the formula Akω¯is true then ωΩk. The class description may be represented as a disjunction of elementary conjunctions of atomic formulas.

Here and below, the notation x¯is used for an ordered list of the set x. To denote that there exists such a list x¯that all values for variables from the list x¯are distinct the notation x¯Akx¯is used.

The introduced descriptions allow to solve many artificial intelligence problems [9]. Main of these problems may be formulated as follows.

Identification problem: to pick out all parts of the object ω that belongs to the class Ωk.

Classification problem: to find all such class numbers k that ωΩk.

Analysis problem: to find and classify all parts τ of the object ω.

The solution of these problems may be reduced to the proof of logic sequents

Sωx¯Akx¯,E1
Sωk=1KAkx¯,E2
Sωk=1Kx¯Akx¯,E3

respectively, and determination of the values for x¯and k. The number of Akx¯variables in the sequent (2) must be equal to the number of constants in ω.

Note that the proof of any of the sequent (1), (2), or (3) answers only the question “whether it is true?” Strictly speaking, in the sequents (1)–(3), instead of the symbols x¯and k=1Kthere must be words “what are the distinct values of x¯” denoted as ?x¯and “what are the values of k?” denoted as ?k=1K, respectively. In such a case, the sequents (1)–(3) would take the form

Sω(?x¯)Akx¯,E4
Sω?k=1KAkx¯,E5
Sω?k=1K(?x¯)Akx¯.E6

If one uses an exhaustive or a logical algorithm (derivation in a sequent calculus or proof by resolution method), the algorithm gives the values for x¯and k.

The proof of sequents (1) and (3) is based on the proof of the sequent

Sωx¯Ax¯,E7

where Ax¯is an elementary conjunction. It follows from the fact that Akx¯is a disjunction of the form C1∨…∨Cr of elementary conjunctions of atomic formulas C1,,Cr, and x¯(C1∨…∨Cr) ⇔ (x¯C1∨…∨ x¯Cr). That is why we can consecutively check the sequents of the form Sωx¯Cj. Here, the maximal value for j is r for the sequent (1), and the sum of the number of elementary conjunctions in all class descriptions for the sequent (3).

An exhaustive algorithm is widespread to prove (4). The total estimate for the number of steps (i.e., the number of comparisons) for the exhaustive algorithm solving (4) is

tt1tm+1i=1naisiE8

or, more roughly,

Otmas.E9

While using a logical algorithm (derivation in a predicate sequent calculus or proof by resolution method for predicate calculus), one must find unifier of the formula Ax¯and some subset of S(ω).

The number of steps (i.e., the number of comparisons) required for the solution of the system and, hence, for the logical algorithm solving (4) is

Os1a1snan,E10

ai and si be the numbers of literals with the predicate pi in Ax¯and in S(ω), respectively. More roughly

Osa,E11

where s′ = max{s1,, sn}.

The above-received estimations are exponential over the length of Ax¯. The ones for an exhaustive algorithm are exponential over the number of variables, and for a logical algorithm they are exponential over the maximal number of literals with the same predicate. It allows to choose the algorithm depending on characteristics of the concrete problem under consideration. Note that the reverse Maslov’s method [10, 11] has the same estimations for the solution of the sequent (4), but makes essentially smaller number of steps on the average.

The received estimations cannot be essentially decreased up to polynomial ones if P ≠ NP (classes P and NP are the classes of predicates checked in polynomial time by a deterministic or nondeterministic Turing machine respectively). More precisely, the problem (4) is NP-complete and, hence, the problems (1) and (3) are NP-complete, and the problems (4) and (5) are NP-hard [4, 5].

Problem (2) is strictly connected with the so-called “open” problem ISOMORPHISM OF GRAPHS [3], for which it is not proved neither its polynomiality nor its NP-completeness.

2.1. Model example of description and the estimations for the number of an algorithm steps

These standard images allow to form a description (up to mirror image) of almost all boxes. Such a description is a disjunction of four elementary conjunctions containing, respectively, 10, 8, 10, 8 variables and 30 + 2, 23 + 1, 28 + 4, 33 + 4 atomic formulas with predicates V and L, respectively. The elementary conjunctions corresponding to the images are

Aax1x2x3x4x5x6x7x8x9x10=Vx1x3x2&Vx2x1x5&Vx2x5x8&Vx3x4x1&Vx3x5x1&Vx3x9x4&Vx3x9x5&Vx3x9x1&Vx4x3x6&Vx4x6x5&Vx5x2x3&Vx5x2x4&Vx5x3x7&Vx5x3x10&Vx5x4x7&Vx5x4x10&Vx5x7x2&Vx5x10x2&Vx6x4x9&Vx6x7x4&Vx6x9x7&Vx7x5x6&Vx7x6x10&Vx8x2x10&Vx9x6x3&Vx9x10x6&Vx9x10x3&Vx10x7x9&Vx10x8x7&Vx10x8x9&Lx4x3x5&Lx7x5x10,
Abx1x2x3x4x5x6x7x8=Vx1x4x2&Vx2x1x6&Vx2x6x3&Vx2x1x3&Vx3x2x8&Vx4x5x1&Vx4x6x1&Vx4x7x5&Vx4x7x6&Vx4x7x1&Vx5x4x7&Vx5x7x6&Vx6x2x5&Vx6x2x4&Vx6x5x8&Vx6x4x8&Vx6x8x2&Vx7x5x4&Vx7x8x5&V(x7,x8,x4&Vx8x3x6&Vx8x6x7&Vx8x3x7&Lx5x4x6,
Acx1x2x3x4x5x6x7x8=Vx1x3x2&Vx2x1x6&Vx3x4x1&Vx3x5x1&Vx3x6x1&Vx3x7x4&Vx3x7x5&Vx3x7x6&Vx3x7x1&Vx4x3x7&Vx4x7x5&Vx4x7x6&Vx5x3x8&Vx5x4x8&Vx5x8x6&Vx6x2x5&Vx6x2x4&Vx6x2x3&Vx6x5x8&Vx6x4x8&Vx6x3x8&Vx6x2x8&Vx7x8x4&Vx7x8x3&Vx7x4x3&Vx8x6x5&Vx8x5x7&Vx8x6x7&Lx4x3x5&Lx4x3x6&Lx5x4x6&Lx5x3x6,
Adx1x2x3x4x5x6x7x8x9x10=Vx1x3x2&Vx2x1x6&Vx3x4x1&Vx3x5x1&Vx3x6x1&Vx3x9x4&Vx3x9x5&Vx3x9x6&Vx3x9x1&Vx4x3x7&Vx4x7x5&&Vx4x7x6&Vx5x4x8&Vx5x3x8&Vx5x8x6&Vx6x2x5&Vx6x2x4&Vx6x2x3&Vx6x5x10&Vx6x4x10&Vx6x3x10&Vx7x4x9&Vx7x8x4&Vx7x9x8&Vx8x5x7&Vx8x7x10&Vx8x10x5&&Vx9x7x3&Vx9x10x3&Vx9x10x7&Vx10x6x8&Vx10x8x9&Vx10x6x9&Lx4x3x5&Lx4x3x6&Lx5x4x6&Lx5x3x6.

Given a “box” inside a complex contour image containing t nodes and s be the maximal number of occurrences of the predicate V in the description S(ω), it would be recognized (according to the estimations (5′) and (6′)) in O(t10) steps by an exhaustive algorithm and in O(s37) steps by a logical algorithm.

Can seem that many atomic formulas such as V(x5,x2,x4), V(x5,x3,x7), V(x5,x4,x7), and V(x5,x7,x2) in V(x5,x2,x3) & V(x5,x2,x4) & V(x5,x3,x7) & V(x5,x3,x10) & V(x5,x4,x7) & V(x5,x4,x10) & V(x5,x7,x2) & V(x5,x10,x2) are unnecessary. But if we delete such “unnecessary” formulas, it would be needed to add to a premise of a sequent, a condition that every point that belongs to a segment (y,z) may be substituted instead of y or z (be the second or the third argument) in every atomic formula with the predicate V. It would be another setting of a problem. Moreover, such “unnecessary” formulas can help to decrease the number of algorithm run steps if we use branch and bound algorithm inside the exhaustive algorithm or the reverse Maslov’s method for a logical one [11].

3. Level description of classes

Below, the designation Akx¯kwill be used for elementary conjunctions, which are disjunctive terms of a class description.

The notion of level description of classes was introduced in [6]. Such a description essentially allows to decrease the number of steps for an algorithm solving every of the above-formulated problems. This notion is based on the extraction of “frequently” appeared “sub-formulas” Pi1y¯i1(i = 1,, n1) of A1x¯1,, AKx¯Kwith “small complexity” and changing them in these formulas by atomic formulas pi1yi1defined by an equivalence of the form pi1yi1Pi1y¯i1. New predicates pi1having new first-level arguments yi1for lists y¯i1of initial variables are called first-level predicates. The formula Ak1x¯k1is received from Akx¯kby means of a substitution of pi1yi1instead of Pi1y¯i1

Repeat the above-described procedure with all formulas Ak1x¯k1. After L repetitions, an L-level description in the following form is received:

AkLx¯Lp11y11P11y¯11pn11yn11Pn11y¯n11pilyilPily¯ilpnLLynLLPnLLy¯nLLE12

The solution of the problem of the form (4) with the use of the level description of classes is decomposed on the sequential (l = 1, , L) implementation of the actions 1–4:

  1. For every i (i = 1,, nl) check Sl−1(ω)y¯i1Pi1y¯i1and find all lists τ¯i1of previous levels constants for the values of the variable list yi1such that Sl−1(ω)Pi1τ¯i1.

  2. Introduce new l-level atomic formulas pi1yi1defined by the equalities pi1yi1Pi1y¯i1with new l-level variables.

  3. Substitute pi1yi1instead of Pi1y¯i1into Akl1y¯kl1and obtain Akly¯kl.

  4. Add all constant atomic l-level formulas in the form pi1τil(τi1were received at the first step) to Sl−1(ω) and obtain Sl(ω) . Here τilτil are new l-level constants for the lists of (l − 1)-level constants

  5. At last check SL(ω)y¯kLAkLy¯kL.

The decreasing of the number of steps for an algorithm solving every of the above formulated problems (1)–(3) with the use of a level description follows from the fact that in items 1, 2, and 5, we solve the same problem as it was formulated in Section 1 and has the number (4). The estimations of number of steps exponentially depend on the parameters of the formula, i.e., on the right part of implication. That is why the term “small complexity” for Pily¯ilmust be interpreted as “small number of variables in Pily¯il for an exhaustive algorithm, and “small number of literals in Pily¯il for a logical algorithm

Why did we use quotation marks for the term “sub-formulas?” Such formulas (elementary conjunctions) Pjly¯jlare not obliged to be precisely sub-formulas of A1x¯1, , AKx¯Kbut may differ from these sub-formulas in names of variables and order of conjunctive terms

Definition 1. Elementary conjunctions P and Q are called isomorphic if there is an elementary conjunction R and substitutions λR,P and λR,Q of the arguments of P and Q, respectively, instead of the variables in R such that the results of these substitutions coincide up to the order of literals

The substitutions λR,P and λR,Q are called unifiers of R with P and Q, respectively.

Definition 2. Elementary conjunction C is called a common up to the names of arguments sub-formula of two elementary conjunctions A and B if it is isomorphic to some sub-formulas A′ and B′ of A and B, respectively

For example, let A(x,y,z) = p1(x) & p1(y) & p1(z) & p2(x, y) & p3(x, z), B(x,y,z) = p1(x) & p1(y) & p1(z) & p2(x, z) & p3(x, z)

Is the formula P(u,v) = p1(u) & p1(v) & p2(u, v) their common sub-formula?

The formula P(u,v) is their common up to the names of variables sub-formula with the unifiers λP,A—substitution of x and y instead of u and v, respectively, and λP,B—substitution of x and z instead of u and v, respectively. It is so because P(x,y) = p1(x) & p1(y) & p2(x,y) is a sub-formula of A(x,y,z) and P(x,z) = p1(x) & p1(z) & p2(x,z) is a sub-formula of B(x,y,z).

An algorithm of extraction of a maximal (having a maximal number of literals) common up to the names of arguments sub-formula C of two elementary conjunctions A and B and determining the unifiers λc,A and λc,B is described in [12]. The number of steps of this algorithm is O(aa bb), where a and b are the numbers of literals in A and B, respectively. The minimal number of steps of this algorithm is O((ab)2), the middle estimate is O((ab)1/2 log(ab)).

This algorithm allows to construct a level description for a set of goal elementary conjunctions. Essential difference between maximal common up to the names of arguments sub-formulas and sub-formulas in the level description consists in the fact that in the level description it is needed to extract sub-formulas with “small complexity” but not a maximal one. An algorithm of level description construction is in [6]. It consists in sequential pairwise extraction of common up to the names of variables sub-formulas of Aix¯iand Ajx¯jwith finding their unifiers and then the analogous procedure with the obtained sub-formulas.

Let N be the maximal number of literals Akx¯kin (k = 1,, K). The upper bound of this algorithm number of steps is O(K2N2N).

3.1. Example of sub-formula extraction and a level description construction

Return to the example in the previous section. There, we have seen a description of a class of “boxes” represented in Figure 1. According to these descriptions, we have received that given a “box” inside a complex contour image containing t nodes it would be recognized in O(t10) steps by an exhaustive algorithm and in O(s37) steps by a logical algorithm (here, s is the maximal number of occurrences of the same predicate in the object description S(ω)).

Figure 1.

Standard different contour images of a “box”.

Pairwise extraction of common up to the names of variables of elementary conjunctions, corresponding to these images, allows to extract common up to the names of variables sub-formulas corresponding to the images represented in Figure 2

Figure 2.

Images corresponding to extraction of common sub-formulas.

These sub-formulas contain, respectively, 8, 8, 7, 7, 7, 8 variables and 18, 15, 11, 11, 15, 16 atomic formulas.

The following extraction by means of pairwise partial deduction between common sub-formulas corresponding to images ab, ac, ad, bc, bd, cd gives a sub-formula corresponding to the image represented in Figure 3.

Figure 3.

Image corresponding to the second extraction of common sub-formulas.

Elementary conjunction P1(x1,x2,x3,x4,x5,x9,x10) = V(x1,x3,x2) & V(x2,x1,x5) & V(x3,x4,x1) & V(x3,x5,x1) & V(x3,x9,x4) & V(x3,x9,x5) & V(x3,x9,x1) & V(x5,x2,x4) & V(x5,x2,x3) & V(x9,x10,x3) & T(x4,x3,x5), corresponding to this image, defines a first-level predicate p1(x1). The first-level variable x1 is a variable for a list of seven initial variables x1 = (x1,x2,x3,x4,x5,x9,x10). The unifier of P1(x1,x2,x3,x4,x5,x9,x10) with the description of ab, ac, ad, ac, and bd is an identical substitution, but its unifier with the description of cd is a substitution of x6 instead of x5.

Elementary conjunctions P12(x1,x1,x2,x3,x4,x5,x8,x9,x10), P22(x1,x4,x5,x6,x9,x10), P32(x1,x3,x4,x5,x10), P42(x1,x2,x5,x6,x10), corresponding to the images ab, ac, bd, cd and written with the use of the predicate p1(x1), define second-level predicates p12(x12), p22(x22), p32(x32), p42(x42) with the second-level variables x12 = (x1,x1,x2,x3,x4,x5,x8,x9,x10), x22 = (x1,x4,x5,x6,x9,x10), x32 = (x1,x3,x4,x5,x10), x42 = (x1,x2,x5,x6,x10).

For example, a sub-formula corresponding to the image ab is P12(x1,x1,x2,x3,x4,x5,x8,x9,x10) = p1(x1) & V(x2,x5,x8) & V(x2,x1,x8) & V(x5,x4,x10) & V(x5,x3,x10) & V(x8,x2,x10) & V(x10,x8,x5) & V(x10,x5,x9) & V(x10,x8,x9). The unifier of P12(x1,x1,x2,x3,x4,x5,x8,x9,x10) with the description of a is an identical substitution, and with the description of b, it is a substitution of x4,x5,x6,x7,x8 instead of x2,x4,x5,x9,x10. Descriptions of images c and d are not unified with it.

The three-level description of the image b takes the form Ab2(x12,x4,x5,x6,x7) = p12(x12) & V(x5,x4,x7) & V(x5,x7,x6) or Ab2(x32,x4,x5,x6,x7) = p32(x32) & V(x3,x2,x8) & V(x5,x4,x7) & V(x5,x7,x6).

Given a “box” inside a complex contour image containing t nodes, the proof the sequence from S(ω) of elementary conjunction P1(x1,x2,x3,x4,x5,x9,x10) defining the first-level predicate p1(x1) and the denotation of variables x1,x2,x3,x4,x5,x9,x10 would be done in O(t7) steps by an exhaustive algorithm and in O(s11) steps by a logical algorithm.

Elementary conjunctions P12(x11), P22(x11), P32(x11), P42(x11) contain respectively only 1, 1, 0, 1 “new” variables (not containing in the first-level variables) and 7, 4, 4, 5 “new” atomic formulas. The proof of the sequence from S1(ω ) of these elementary conjunctions defining the second-level predicates p12(x12), p22(x22), p32(x32), p42(x42), and the denotation of the “new” variables would be done in O(t) steps by an exhaustive algorithm and in O(s7) steps by a logical algorithm.

Elementary conjunctions obtained from the class description by means of second-level predicates instead of the corresponding sub-formulas contain respectively 2, 0, 2, 2 “new” variables and 7, 4, 11, 16 “new” atomic formulas. The proof of the sequence from S2(ω ) of these elementary conjunctions and the denotation of the “new” variables would be done in O(t2) steps by an exhaustive algorithm and in O(s16) steps by a logical algorithm.

As O(t7) + O(t) + O(t2) = O(t7) < O(t10) and O(s11) + O(s7) + O(s16) = O(s16) < O(s37) then both an exhaustive algorithm and a logical algorithm using the built level description of the class of “boxes” make the less number of steps then the same ones using the initial description. At the same time, the decreasing of number of steps of a logical algorithm is more noticeably.

4. Logic-predicate network

Traditional neuron network deals with binary or many-valued characteristics of an object and is an adder of weighted inputs followed by a function mapping the result into the segment [0, 1]. The neuron network configuration is fixed and only the weights may be changed.

A logic-predicate network is described later. The inputs for this network are atomic formulas setting properties of the elements composing an investigated object and relations between them [7]. The proposed model of logic-predicate network has two blocks: a training block and a recognition block. The input of every block is an elementary conjunction of atomic predicate formulas or their negations. Configuration of the recognition block is formed after an implementation of the training block and may be changed with its help.

The training block is a “slowly running” block. At the same time, the recognition block is a “quickly running” one. The base of the proposed predicate network is a logic-objective approach to AI problems and level description of classes.

The scheme of the logic-predicate network is presented in Figure 4

Figure 4.

Scheme of the logic-predicate network.

At a training stage of logic-predicate network construction, we have a training set of objects. Let a training set of objects ω1,…, ωK be given to form an initial variant of the network training block. Replace every constant ωkjin S(ωk) by a variable xkj(k = 1,, K, j = 1,, tk) and substitute the sign & between the atomic formulas. Initial goal formulas A1x¯1,,AKx¯Kare obtained.

Construct a level description for these goal formulas with the use of algorithm of level description. The first approximation to the recognition block is formed. Formulas Pily¯il(i = 1,, nl, l = 1,, L) obtained in the training block (together with the unifiers) are the contents of the cells forming the recognition block. This block runs as it was described in the section level description of classes.

The recognition block tries to identify a new object according to the level description of classes, obtained in the training block.

If after the “recognition block” run an object is not recognized or has wrong classification, then it is possible to train anew the network. The description of the “wrong” object must be added to the input set of the training block. The training block extracts common sub-formulas of this description and previously received formulas forming the recognition block. Some sub-formulas in the level description would be changed. Then, the recognition block is reconstructed.

4.1. Model example of a logic-predicate network construction

Given a training set for the class of contour images of “boxes” presented in Figure 1 (Section 2). Pairwise extraction of common up to the names of variables of elementary conjunctions, corresponding to these images, allows to extract common sub-formulas corresponding to the images presented in Figures 2 and 3 (Section 3). Fragments of the images corresponding to a three-level network are presented in Figure 5.

Figure 5.

Fragments of the images corresponding to a three-level network.

Given, a new image represented in Figure 6 for recognition, the network would not recognize it because the first-level predicate is not valid.

Figure 6.

Control image.

Add the description of this control image to the input data of the training block. The extraction of common sub-formulas for this description and the formula defining the first-level predicate gives a formula corresponding to the image represented in Figure 7.

Figure 7.

Image corresponding to the new first-level predicate.

New second-level predicates correspond to three images represented in Figure 8.

Figure 8.

Images corresponding to three new second-level predicates.

The set of the third-level predicates coincides with the set of previous second-level predicates. So, the recognition block is constructed anew and represents four-level description of the class. Fragments of the images corresponding to a four-level network are presented in Figure 9.

Figure 9.

Fragments of the images corresponding to a four-level network.

5. Multi-agent description of an object

A problem of multi-agent description of a complex object is under consideration in this section. It is supposed that every agent knows only a part of an investigated object description. Moreover, she does not know the true names of elements and gives them names arbitrary. It is similar to the parable about tree blind men who feel an elephant. To overcome such a paradox, it is supposed that every two agents have information concerning some common part of an object. The main difficulty in this problem is to find and identify these parts [8].

5.1. Setting of the problem

Let an investigated object is represented as a set of its elements ω=ω1ωtand is characterized by the set of predicates p1,…, pn, every of which is defined on the elements of ω and gives properties of these elements or relations between them.

Information (description) of an object is an elementary conjunction of atomic formulas with predicates p1,, pn and some constants as arguments.

There are m agents a1,, am which can measure some values for some predicates of some elements of ω. The agent aj does not know the true number of the ω elements and suppose that she deals with the object ωj=ω1jωtjj. That is, the agent aj has the information Ijω1jωtjjin the form of elementary conjunction of atomic formulas. It is required to reconstruct the full description Iω1ωtof ω (if it is possible).

As every agent uses her own notifications for the names of the object elements, it is needed to find all common up to the names of arguments sub-formulas Cij of the information Iiω1iωtiiand Ijω1jωtjj(i ≠ j) and their unifiers, i.e., such substitutions for the argument names that the extracted pairs of sub-formulas are identical.

5.2. Algorithm of multi-agent description

Below, the arguments of information will be omitted. Let every agent aj has information Ij about the described object ω (j = 1,…, m). To construct a description of ω the following algorithm is offered.

  1. Change all constants in I1,, Im by variables in such a way that different constants are changed by different variables and the names of variables in Ii and Ij (i ≠ j) does not coincide. Obtain I′1,, I′m.

  2. For every pair of elementary conjunctions I′i and I′j (i = 1,, m − 1, j = i + 1, , m) find their maximal common up to the names of arguments sub-formula Cij and unifiers λi,ij and λj,ij. Every argument of Cij has a unique name.

  3. For every pair i and j (i > j) check if I′i and I′j contain a contradictory pair of atomic formulas or two sub-formulas which cannot be satisfied simultaneously (for example, “x is green” and “x is red”). If such a contradiction is established, then delete from Cij atomic formulas containing the variables, which are in the contradictory sub-formulas. Change the unifiers by means of elimination of these variables.

  4. For every i, identify the variables in Cij (i ≠ j) which are substituted in I′i and I′j instead of the same variable. The names of the identified variables are changed in unifiers by the same name.

  5. With the use of the unifiers obtained in items 2–4 change the names of variables in I′1,, I′m. Obtain I″1, , I″m.

  6. Write down the conjunction I″1 & & I″m and delete the repeated atomic formulas.

5.3. Upper bound of the number of steps

To estimate the number of the algorithm run steps, we estimate every item of the algorithm.

  1. Item 1 requires not more than j=lmIj“steps.”

  2. Item 2 requires Otitj2Ij“steps” for an exhaustive algorithm and OsiIjIi3

    “steps” for an algorithm based on the derivation in the predicate calculus.

    It is needed to summarize the above estimates for i = 1,, m − 1, j = i, , m. So, we have Ott2sm2“steps” for an exhaustive algorithm and Oss+3m2“steps” for an algorithm based on the derivation in the predicate calculus. Here, t and Iare the maximal numbers of variables and atomic formulas in Ij (j = 1,, m), respectively.

  3. Consistency checking of the formulas Ii and Ij requires IiIj“steps.” This item of the algorithm requires not more than i=1mmiIi“steps” that is O(m2s) “steps.”

  4. For every i, identification of the variables in Cij (i > j) consists in the comparison of the replaced part of the unifiers λi,ij and λj,ij. It requires not more than (m − i)ti2 “steps.” Summarizing it for i = 1,, m we have not more than i=1mmiti2=Om2t2“steps”.

  5. The number of “steps” required for the changing of the names of variables in I1, , Im is linear under i=1mIi=OmI“steps.”

  6. The number of “steps” required for the deleting of the repeated conjunctive terms is not more than i=1m1j=i+1mIiIj“steps.”

The whole number of the algorithm run steps is O(tt 2s m2) for an exhaustive algorithm and O(ss + 3 m2) for an algorithm based on the derivation in the predicate calculus.

The analysis of the received estimation shows that the main contribution is made by the summarized number of partial deduction checking (item 2).

5.4. Example of a multi-agent description

Let the initial predicates be V and L described in Section 2. Each of the three agents has a description of one of the fragment presented in Figure 10.

Figure 10.

Fragments of the image received by three agents.

According to the item 1 of the algorithm, all constants in the fragment descriptions are replaced by variables in such a way that different constants are changed by different variables and the names of variables in Ii and Ij (i ≠ j) does not coincide. The fragment descriptions take the form:

I′1(x1,…,x6) = V(x1,x2,x4) & V(x1,x5,x4) & V(x1,x3,x2) & V(x1,x3,x5) & V(x1,x3,x4) & V(x2,x1,x3) & V(x2,x3,x5) & V(x3,x2,x1) &V(x3,x6,x2) & V(x3,x6,x1) & L(x2,x1,x5),

I′2(y1,…,y6) = V(y3,y1,y4) & V(y1,y2,y3) & V(y1,y5,y3) & V(y1,y6,y2) & V(y1,y6,y5) & V(y1,y6,y3) & L(y2,y1,y5),

I′3(z1,…,z8) = V(z1,z5,z3) & V(z1,z3,z2) & V(z1,z5,z2) & V(z3,z1,z7) & V(z3,z1,z6) & V(z3,z7,z4) & V(z3,z6,z4) & V(z3,z4,z1) & V(z4,z2,z3) & V(z4,z3,z8) & V(z4,z2,z8) & L(z7,z6,z3).

According to the item 2 of the algorithm, find maximal common up to the names of arguments sub-formula of formulas I′1(x1,…,x6) and I′2(y1,…,y6). It is C12(u0,…,u4) of the form C12(u0,…,u4) = V(u0,u1,u2) & V(u0,u3,u2) & V(u0,u4,u1) & V(u0,u4,u3) & V(u0,u4,u2) & L(u1,u0,u3).

It has unifiers λI1,C12—substitution of u0, u1, u4, u2, u3 instead of x1, x2, x3, x4, x5, respectively, and λI2,C12—substitution of u0, u1, u2, u3, u4 instead of y1, y2, y3, y5, y6, respectively. Besides,

I′1(u0,u1,u2,u3,u4,x6) = V(u1,u0,u4) & V(u1,u4,u3) & V(u4,u1,u0) & V(u4,x6,u1) & V(u4,x6,u0) & C12(u0, …, u4),

I′2(u0,u1,u2,y4,u3,u4) = V(u2,u0,y4) & C12(u0,…,u4).

Maximal common up to the names of arguments sub-formula of I′2(y1,…,y6) and I′3(z1,…,z8) is C23(v0,v2,v4,v5,v6,v7) of the form

C23(v0,v2,v4,v5,v6,v7) = V(v6,v2,v7) & V(v2,v4,v6) & V(v2,v5,v6) &V(v2,v0,v4) & V(v2,v0,v5).

It has unifiers λI2,C23—substitution of v2, v4, v6, v7, v5, v0 instead of y1, y2, y3, y4, y5, y6, respectively, and λI3,C23—substitution of v0, v2, v6, v5, v4, v7 instead of z1, z3, z5, z6, z7, z8, respectively. Besides,

I′2(v2,v4,v6,v7,v5,v0) = V(v2,v0,v6) & L(v4,v2,v5) & C23(v0,v2,v4,v5,v6,v7),

I′3(v0,z2,v2,v6,z5,v5,v4,v7) = V(v2,v6,v0) & V(v0,z5,v2) & V(v0,v2,z2) & V(v0,v5,z2) & V(v6,z2,v2) & V(v6,v2,v7) & L(v4,v5,v2) & C23(v0,v2,v4,v5,v6,v7).

As I′2(v2,v4,v6,v7,v5,v0) contains V(v2,v0,v6) and I′3(v0,z2,v2,v6,z5,v5,v4,v7) contains V(v2,v6,v0) and according to the definition of the predicate V, the formula V(x,y,z) & V(x,z,y) is a contradiction, so substitutions with this unifiers cannot give a consistent description of the object. After deleting from I′2(y1,…,y6) and I′3(z1,…,z8), the variables y1 and z3, respectively, a new maximal common up to the names of arguments their sub-formula C’23(v0,v2,v4,v5,v6,v7) of the form C’23(v0,v1,v2) = L(v1,v0,v2) will be received with the unifiers λI2,C’23— substitution of v0, v1, v2 instead of y1, y2, y3, respectively, and λI3,C’23—substitution of v2, v0, v1 instead of z3, z6, z7, respectively. Besides,

I′2(v0,v1,v2,y4,y5,y6) = V(v2,v0,y4) & V(v0,v1,v2) & V(v0,y5,v2) & V(v0,y6,v1) &V(v0,y6,y5) & V(v0,y6,v2) & C’23(v0,v1,v2),

I′3(z1,z2,v2,z4,z5,v0,v1,z8) = V(z1,z5,v2) & V(z1,v2,z2) & V(z1,z5,z2) & V(v2,z1,v1) & V (v2,z1,v0) & V(v2,v1,z4) & V(v2,v0,z4) & V(v2,z4,z1) & V(z4,z2,v2) & V(z4,v2,z8) & V(z4,z2,z8) & C’23(v0,v1,v2).

Maximal common up to the names of arguments sub-formula of I1(x1,…,x6) and I3(z1,…,z8) is C13(w0, …,w6) in the form

C13(w0, …,w6) = V(w2,w4,w6) & V(w2,w5,w6) & V(w2,w0,w4) & V(w2,w0,w5) & V(w0,w1,w2).

It has unifiers λI1,C13— substitution of w2, w4, w0, w6, w5, w6 instead of x1, x2, x3, x4, x5, x6, respectively, and λI3,C13—substitution of w0, w2, w6, w1, w5, w2 instead of z1, z3, z4, z5, z6, z7, respectively. Besides,

I′1(w2,w4,w0,w6,w5,w1) = V(w2,w0,w6) & V(w0,w1,w4) & V(w0,w4,w2) & L(w2,w4,w5) & C13(w0,…,w6),

I′3(w0,z2,w2,w6,w1,w5,w4,z8) = V(w0,w2,w3) & V(w0,w1,w3) & V(w2,w6,w0) & V(w6,w3,w2) & V(w6,w2,w7) & V(w6,w3,w7) & C13(w0,…,w6).

As I′1(w2,w4,w0,w6,w5,w1) contains V(w2,w0,w6), I3(w0,z2,w2,w6,w1,w5,w4,z8) contains V(w2,w6,w0) and according to the definition of the predicate V, the formula V(x,y,z) & V(x,z,y) is a contradiction, so substitutions with this unifiers cannot give a consistent description of the object.

After deleting from I′1(x1,…,x6) and I′3(z1,…,z8) literals with the variables x1 and z3, respectively, a new maximal common up to the names of arguments their sub-formula

C′13(w0,w1,w2) of the form C’13(w0,w1,w2) = L(w1,w0,w2)

will be received with the unifiers λI1,C’13—substitution of w0, w1, w2 instead of x1, x2, x5, respectively, and λI3,C’13—substitution of w2, w1, w0 instead of z3, z4, z5 respectively. Besides,

I′1(w0,w1,x3,x4,w2,x6) = V(w0,w1,x4) & V(w0,w2,x4) & V(w0,x3,w1) & V(w0,x3,w2) & V(w0,x3,x4) & V(w1,w0,x3) & V(w1,x3,w2) & V(x3,w1,w0) & V(x3,x6,w1) & V(x3,x6,w0) & C’13(w0,w1,w2),

I′3(z1,z1,w2,w1,w0,z6,z7,z8) = V(z1,w0,w2) & V(z1,w2,z2) & V(z1,w0,z2) & V(w2,z1,z7) & V(w2,z1,z6) & V(w2,z7,w1) & V(w2,z6,w1) & V(w2,w1,z1) & V(w1,z2,w2) & V(w1,w2,z8) & V(w1,z2,z8) & C′13(w0,w1,w2).

According to the item 4 of the algorithm, we identify new variables substituted instead of the same initial variable. That is we identify the following variables:

  1. u0 and w0 (are substituted instead of the variable x1),

  2. u1 and w1 (are substituted instead of the variable x2),

  3. u2 and w2 (are substituted instead of the variable x4),

  4. u0 and v0 (are substituted instead of the variable y1),

  5. u1 and v1 (are substituted instead of the variable y2),

  6. u2 and v2 (are substituted instead of the variable y3),

  7. v0 and w0 (are substituted instead of the variable z6),

  8. v1 and w1 (are substituted instead of the variable z3),

  9. v2 and w2 (are substituted instead of the variable z7).

The identified variables denote as α 0, α 1, and α 2. So, we have the equalities u0 = v0 = w0 = α 0, u1 = v1 = w1 = α 1, u2 = v2 = w2 = α 2.

As a result, we have the following descriptions of the fragments:

I″1(α 0, α 1,u4,u2, α 2,x6) = V(α 0, α 1,u2) & V(α 0, α 2,u2) & V(α 0,u4, α 1) & V(α 0,u4, α 2) & V(α 0,u4,u2) & V(α 1, α 0,u4) & V(α 1,u4, α 2) & V(x3, α 1, α 0) & V(u4,x6, α 1) & V(u4,x6, α 0) & L(α 1, α 0, α 2),

I″2(α0, α 1,u2,y4, α 2,u4) = V(u2, α 0,y4) & V(α 0, α 1,u2) & V(α 0, α 2,u2) & V(α 0,u4, α 1) & V(α 0,u4, α 2) & V(α 0,u4,u2) & L(α 1, α 0, α 2),

I″3(z1,z2, α 2,z4,z5, α 0, α 1,z8) = V(z1,z5, α 2) & V(z1, α 2,z2) & V(z1,z5,z2) & V(α 2,z1, α 1) & V(α 2,z1, α 0) & V(α 2, α 1,z4) & V(α 2, α 0,z4) & V(α 2,z4,z1) & V(z4,z2, α 2) & V(z4, α 2,z8) & V(z4,z2,z8) & L(α 1, α 0, α 2).

Their conjunction

V(α0, α 1,u2) & V(α 0, α 2,u2) & V(α 0,u4, α 1) & V(α 0,u4, α 2) & V(α 0,u4,u2) &

V(α 1, α 0,u4) & V(α 1,u4, α 2) & V(x3, α 1, α 0) & V(u4,x6, α 1) & V(u4,x6, α 0) &

V(u2, α 0,y4) & V(z1,z5, α 2) & V(z1, α 2,z2) & V(z1,z5,z2) & V(α 2,z1, α 1) &

V(α 2,z1, α 0) & V(α 2, α 1,z4) & V(α 2, α 0,z4) &V(α 2,z4,z1) & V(z4,z2, α 2) &

V(z4, α 2,z8) & V(z4,z2,z8) & L(α 1, α 0, α 2)

allows to “stick together” the images of fragments according to the same variable. The image corresponding to the result of “sticking” is presented in Figure 11.

Figure 11.

Image corresponding to the result of “sticking”.

If a description of the investigated object is presented in the database, it may be found according the principle “the nearest neighbor” with the use of metric for predicate formulas presented in [13].

6. Conclusion

Logic-predicate approach to an AI problem has a rather powerful capability, essentially when an investigated object is a compound one and is characterized by properties of its elements and relations between them.

Setting of pattern recognition problems considered in Section 2 (except the problem (2)) differs from the classical one. The setting of the problems (1) and (3), in which it is needed to find parts of an investigated object, turns out to be a rather difficult one in the frameworks of a standard approach in the frameworks of which an object is regarded as a whole indivisible one.

In particular, an exponential estimation for number of propositional variables in a formula simulating a predicate formula in a finite domain for planning problems T·|ActOP is mentioned in [14]. Here, T is the number of time stages, |Act| is the number of schemes of actions, O is the number of objects in the domain, P is the maximal number of parameters in schemes of actions. In Section 2, the analogous estimate (5′) was received for an exhaustive algorithm solving the problem (4).

The problem (2) is polynomial equivalent to an “open” problem ISOMORPHISM OF GRAPHS [3] and the problems (1) and (3) are NP-complete.

A notion of level description of classes has been introduced in Section 3 in order to decrease the number of steps of algorithms solving these problems. Such a description reduces the solution of the main problem to a series of solutions of the same form problems with the inputs with the essentially less notation lengths. At the same time, the constructing of a level description still deals with big input data. So, a problem with big input data is solving only once, and then the problem with the essentially less input data is solving repeatedly.

The idea of decomposition of a problem to a series of the “less dimension” problems is not a new one and is frequently used. The difficulty consists in a precise definition of the term “common sub-formula of small complexity.”

The development of a precise definition and of an algorithm for the extraction of a common up to the names of arguments sub-formula of two elementary conjunctions (and their unifiers) allows not only to work out an algorithm of level description construction but also to find an approach to the solution of some else AI problems.

Note that the extracted sub-formulas define generalized characteristics of an object. This has an analogy in medical diagnostics: initial characteristics are symptoms and the generalized ones are syndromes.

Level description of classes allowed to introduce the notion of logic-predicate network described in Section 4. Such a network may be regarded as a self-training network which changes its configuration after an additional training. It corresponds to the fact that in the process of a man training, new notions and relations between them are formed in a human brain.

The presence of an algorithm for the extraction of a common up to the names of arguments sub-formula of two elementary conjunctions (and their unifiers) allows to find an approach to a problem of multi-agent description of an object described in Section 5. Just an extraction of such sub-formulas and determining of their unifiers with the input formulas makes possible to “stick together” such parts of descriptions in which different agents gives different names to one element of the whole object.

Note that the formulation of the problem (1) from Section 2 coincides with the one for a well-known problem CONJUNCTIVE BOOLEAN QUERY from [3]. The difference is in the implementation of these problems. While repeated implementation of the problem (1) the premise S(ω) of the sequent Sωx¯Akx¯is different, while every implementation and the conclusion Akx¯is a constant part. That is why just a collection of class descriptions A1x¯1, …, AKx¯Kpermits to construct a level description.

While repeated implementation of the problem CONJUNCTIVE BOOLEAN QUERY, the premise S(ω) of the sequent Sωx¯Akx¯is constant while every implementation and queries Akx¯are different while every implementation. An approach to the construction of a level data base is presented in [15].

The possibility of reduction of an object description length by means of adding a formula setting some properties of initial predicates to the premise of a sequent was mentioned in the model example in Section 2. Properties of initial predicates also were used in the item 3 of the algorithm of multi-agent description. In fact, in the both cases instead the sequent of the form (4) Sωx¯Ax¯it is needed to check another sequent of the form Cy¯Sωx¯Ax¯, where Cy¯is a set of formulas setting properties of initial predicates. Investigation of computational complexity of such a form sequent may be an interesting problem in the further research.

To solve the problem (2) and to extract a maximal common up to the names of arguments sub-formula of two elementary conjunctions it is needed to check whether two elementary conjunctions are isomorphic. A polynomial in time rough algorithm for such a checking was offered in [12] by Petrov. Numerical experiments with this algorithm give over 99.95% of valid results.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Tatiana Kosovskaya (August 29th 2018). Predicate Calculus as a Tool for AI Problems Solution: Algorithms and Their Complexity, Intelligent System, Chatchawal Wongchoosuk, IntechOpen, DOI: 10.5772/intechopen.72765. Available from:

chapter statistics

310total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

On the Computational Analysis of the Genetic Algorithm for Attitude Control of a Carrier System

By Hadi Jahanshahi and Naeimeh Najafizadeh Sari

Related Book

First chapter

Introductory Chapter: 2D Materials

By Yotsarayuth Seekaew and Chatchawal Wongchoosuk

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us