Sage Journals: Discover world-class research

Abstract

In order to reduce the computational tasks in robots with large-scale and complex knowledge, several methods of robotic knowledge localization have been proposed over the past decades. Logic is an important and useful tool for complex robotic reasoning, action planning, learning and verification. This paper uses propositional atoms in logic to describe the affecting factors of robotic large-scale knowledge. Definability in logic reasoning shows that truths of some propositional atoms are decided by other propositional atoms. Definability technology is an important method to eliminate inessential propositional atoms in robotic large-scale and complex knowledge, so the computational tasks in robotic knowledge can be completed faster. On the other hand, by applying the splitting technique, the knowledge base can be equivalently divided into a number of sub-knowledge bases, without sharing any propositional atoms with others. In this paper, we show that the inessential propositional atoms can be decided faster by the local definability technology based on the splitting method, first formed in local belief revision by Parikh in 1999. Hence, the decision-making in robotic large-scale and complex knowledge is more effective.

Keywords

Robotic Knowledge Localization Definability Splitting

1. Introduction

With the rapid worldwide development of science and technology over the past decades, an increasing number of intelligent robots have been designed by scientists to help people work in hazardous environments. However, almost all robots with limited resources need to deal with a large amount of knowledge quickly, such as exchanging information with the cloud system and sharing information with neighbouring robotic companions [1, 2, 3, 4, 5]. Evidently, robots working in such special environments as underwater, mines and building sites need more knowledge than robots working in normal environments. In order to reduce the computational and storage tasks of robots, several methods of robotic knowledge localization have been proposed over the last two decades[6]. Due to the real-time knowledge-based exchange in multi-cloud robotic systems[7], each robot in multi-cloud robotic systems working in a hazardous environment needs to exchange localization knowledge with the cloud system and other cloud robots to satisfy the computational and storage tasks. The logical system is an important and useful tool for robotic reasoning, action planning, learning and verification [8, 9, 10, 11]. We use propositional atoms in logic to describe the affecting factors of robotic large-scale knowledge. In order to simplify the representation of our localization method in large-scale and complex robotic knowledge, we describe robotic knowledge by propositional logic in this paper. Definability in logic has shown that some propositional atoms are defined by other propositional atoms. Therefore, definability technology is important in the robotic knowledge field since it can eliminate inessential propositional atoms [12, 13]. At the same time, the splitting technique splits entire robotic knowledge equivalently into the same simple sub-knowledge without sharing propositional atoms with others [14]. This paper shows the definability technique based on the splitting method, first proposed by Parikh [14] in 1999 for the localization in belief revision [15, 16], which can quickly decide which are the inessential propositional atoms.

It has been widely accepted that computational intractability is also one of the major challenges for knowledge base maintenance. Most of the knowledge base maintenance operations, such as belief revision, knowledge updates and counterfactuals, are computationally intractable even if knowledge (or beliefs) is represented in propositional languages [17, 18]. More remarkably, tractability is not granted even if the language is restricted to Horn formulas, given that the inference problem with Horn clauses is decidable in deterministic polynomial time. It was shown by Eiter and Gottlob that for those formula-based operators, the complexity of knowledge base change can be co-NP-hard even in the case that the knowledge bases are represented in Horn formulas and the size of input information is bound by a constant. The main issue, as observed in [17], is that a small change to a knowledge base could have a dramatic effect on the whole knowledge base, including those items that are irrelevant to the trigger events. For instance, if a knowledge base contains $\neg p \lor (q_{1} \land \dots \land q_{n})$ and $\neg p$ , then a change of p from $\neg p$ to p forces the originally completely irrelevant conjunction $q_{1} \land \dots \land q_{n}$ to become true [17].

One of the main solutions we can potentially use to tackle the above problem is the so-called relevance-based belief change, proposed by Parikh in 1999. The idea is that, whenever a belief set incurs a change, we only revise the relevant beliefs and leave the rest of the beliefs unchanged. The key technique Parikh used to implement his idea is the Finest Splitting Theorem, stating that, for any propositional theory, there is a unique finest splitting of the propositional language that splits the theory into a set of pieces, each of which is represented by a sub-language of the splitting. Based on the observation, it is possible to impose a relevance criterion on belief changes through syntactical restrictions: whenever an element of a belief set is separated through the finest language splitting from the new information, it remains an element of the revised belief set. Parikh has demonstrated that a belief change operator exists that satisfies the basic AGM postulates for belief revision and obeys the relevance criterion. However, Parikh argued that the relevance criterion conflicts conceptually with two other AGM postulates (the supplementary postulates).

Parikh's method has been developed further by [19]. Parikh's finest splitting theorem is restricted to the propositional languages with finitely many atoms. Kourousias and Makinson generalized Craig's interpolation theorem to the so-called parallel interpolation theorem, through which they successfully extended the finest splitting theorem to the infinite case. Furthermore, Kourousias and Makinson has shown that the AGM partial meet contraction applied to the finest splitting of a consistent belief set, which satisfies Parikh's relevance postulate. Although the result does not provide a representation theorem for the whole set of the AGM postulates and Parikh's relevance criterion¹, it tells us that the AGM partial meet operations can be naturally tuned to meet the relevance criterion.

In this paper, we demonstrate a method for making a fast decision on the essential atoms by adopting Parikh's splitting method. In the next section, we recall some preliminaries, such as parallel interpolation theorem, language splitting over propositional logic, definability and Beth's theorem. In the third section, we present some interesting results on local definability of robotic knowledge using propositional logic in order to increase the efficiency of the computational and store task. In the fourth section, we propose a conjecture to index our future computational method in local base on the basis of splitting. In the last section, we conclude our paper.

2. Preliminaries

In this section we review some preliminary knowledge for this paper. We always assume that we describe robotic knowledge with a propositional logic with a set of infinite or finite elementary literals (or atoms) and the zero-ary falsity ⊥ among the primitive connectives. We use lower-case letters $a, b,…, u, v, w,$ $α, β, γ …$ to range over formulas of classical propositional logic. A set of formulas is denoted by upper-case literals $A, B,…, U, V, W, Γ, Δ, Θ …,$ reserving $L$ for the set of all formulas and $P S$ for the set of all atoms (or elementary literals) of the language. We use upper case letters $X, Y, Z$ to range over the subset of $P S$ and lower case letters $x, y, z$ to range over an element of $P S$ . For any formula α, we write $E (α)$ to represent the set of elementary literals occurring in α; similarly for a set of formulas. For $X \subseteq P S$ , $L (X)$ stands for the sub-language generated by X, i.e., $L (X) = {α \in L : E (α) \subseteq X}$ . Classical logic consequence is written as ⊢ when treated as a relation over $2^{L} \times L$ , classical consequence operation is written as $C n$ when treated as an operation on $2^{L}$ into itself. In other words, $C n (A) = {φ : A ⊢ φ}$ . The relation of classical equivalence is written as $⊣ ⊢$ . We say that a set K of formulas is a knowledge set or belief set if it is closed, i.e., $K = C n (K)$ . To lighten notation, $v (A) = 1$ is short for: $v (α) = 1$ for all $α \in A$ where a valuation (or an interpretation) v is a total function from the entire set of elementary literals of the language to ${0,1}$ , while $v (A) = 0$ abbreviates: $v (α) = 0$ for some $α \in A$ .

Formulas from $L$ are interpreted in the standard way. A world (or interpretation, or valuation), where a total function is from the propositional symbols $P S$ of the language to ${0,1}$ , is denoted by $\vec{ω}$ and their set is denoted by Ω. Any world satisfying a given formula φ is said to be a model of φ. A world (or interpretation, or valuation), a total function from $X \subseteq P S$ to ${0,1}$ , is called $X -$ world; their set is denoted by $Ω_{X}$ . We shall identify $\vec{α}$ with the corresponding canonical conjunction of literals over X in order to simplify the notations; for instance, if $X = {a, b, c}$ and $\vec{α} = (a = 1, b = 0, c = 1)$ , then we also write $\vec{α} = a \land \neg b \land c$ .

We recall some basic notions about essential formulas in [20]. A formula β is an essential formula of α if $α ⊣ ⊢ β$ and for every formula γ with $γ ⊣ ⊢ α$ satisfied $E (β) \subseteq E (γ)$ . It is clear that the essential formula of a formula is not unique. However, the essential formulas of a formula have the same atoms by the least atom-set theorem in [20]. We use $E E (A)$ to denote the essential atoms of set A of formulas.

2.1. Interpolation Theorem and Parallel Interpolation Theorem

In mathematical logic, Craig's interpolation theorem is an important result for the relationship between various logical theories. Roughly stated, the theorem says that if a formula φ implies a formula ψ, then there is a third formula θ, called an interpolant, such that every non-logical symbol in θ occurs both in φ and ψ, φ implies θ and θ implies ψ. The theorem was first proved for first-order logic by William Craig in [21]. Variants of the theorem hold for other logics, such as propositional logic. A stronger form of Craig's theorem for first-order logic was proved by Roger Lyndon in 1959 in [22]; the overall result is sometimes called the Craig-Lyndon theorem.

Theorem 1 (Interpolation Theorem [21]) Let $ψ \in L$ and $A \subseteq L$ . If $A ⊢ ψ$ then there is a formula ϕ such that $A ⊢ ϕ$ , $ϕ ⊢ ψ$ and every sentence symbol that occurs in ϕ also occurs in both A and ψ.

In order to prove the finest splitting theorem in any proposition language, Kourousias and Makinson formulated Parallel Interpolation Theorem, which is a new interpolation theorem in [19].

Theorem 2 (Parallel Interpolation Theorem [19]) Let $ψ \in L$ and $\cup_{i \in I} {A_{i}} \subseteq L$ such that the atom sets $E (A_{i})$ are pairwise disjoint. If $\cup_{i \in I} A_{i} ⊢ ψ$ , then for each $i \in I$ there is a formula $ϕ_{i}$ such that $A_{i} ⊢ ϕ_{i}$ , $\cup_{i \in I} {ϕ_{i}} ⊢ ψ$ and every sentence symbol that occurs in $ϕ_{i}$ also occurs in both A_i and ψ for all i.

2.2. Language splitting over propositional logic

It is well known that Parikh's finest splitting theorem plays the fundamental role in local belief revision. He has shown that there was a unique finest splitting for each set of formulas in finite propositional language in [14]. Kourousias and Makinson extended the result to any language that contains an infinite number of propositional variables in [19]. It allows us to carve up a set of formulas into disjoint pieces.

Definition 1 (Splitting formulas) Let $E = {E_{i}}_{i \in I}$ be any partition of $P S$ , i.e., a partition of atoms of language $L$ . $E$ is said to be a splitting of a set, K, of formulas if there is a family ${B_{i}}_{i \in I}$ of formulas, such that $\cup_{i \in I} {B_{i}} ⊣ ⊢ K$ and $E (B_{i}) \subseteq E_{i}$ for all $i \in I$ . In such a case, we said that ${B_{i}}_{i \in I}$ be a splitting witness of K.

We will use a graph to describe the splitting of a set of formulas in Fig 1.

Figure 1.

Graph of Splitting (|I| =2)

Example 1 Assume set ${p, q, r}$ be entire propositional symbols of the proposition language. Let $A = C n ({p, p \to q, p \to r})$ . Then ${p, q, r}$ ( ${{p, r}, {q}}$ , ${{p}, {q, r}}$ , ${{r}, {p, q}}$ , ${{p}, {r}, {q}}$ ) is the splitting of A under the language, since $A ⊣ ⊢ {p, p \to q, p \to r}$ ( $A ⊣ ⊢ {q, p, p \to r}$ , $A ⊣ ⊢ {p, q, q \to r}$ , $A ⊣ ⊢ {r, p, p \to q}$ , $A ⊣ ⊢ {p, q, r}$ ). Moreover, ${p, p \to q, p \to r}$ ( ${q, p, p \to r}$ , ${p, q, q \to r}$ , ${r, p, p \to q}$ , ${p, q, r}$ ) is splitting witness of ${p, q, r}$ ( ${{p, r}, {q}}$ , ${{p}, {q, r}}$ , ${{r}, {p, q}}$ , ${{p}, {r}, {q}}$ ) splitting of A.

The example shows that a splitting witness of K is not unique and there are many splittings for any set of formulas. The finest splitting draws researchers' attention generally. In other words, people often hope to split a set of formulas as fine as possible such that essential relation matters in same piece possibly. Hence we will recall the fineness of splitting.

Assume that $E = {E_{i}}_{i \in I}$ and $F = {F_{j}}_{j \in J}$ are two splittings of a set K of formula. Let R_E and R_F be the corresponding equivalence relations of $E$ and $F$ , respectively. We say that $E$ is at least as fine as $F$ , written by $E \leq F$ , if $R_{E} \subseteq R_{F}$ .

Kourousias and Makinson proved the following finest splitting theorem based on the Parallel Interpolation Theorem in the last subsection:

Theorem 3 (Finest splitting over formula[19]). Every set K of formulas has a unique finest splitting for a given propositional language.

The theorem shows that for every set K of formulas under any finite or infinite proposition language has a unique finest splitting. When discussing the finite proposition language, the results are clear, since we can check all atom subsets. Although with the elementary method, checking all atom subsets, fails when the language is infinite, it also holds when we use the Parallel Interpolation Theorem proposed in [19].

Example 2 Assume as Example 1. ${{p}, {r}, {q}})$ is the finest splitting of set A of formulas under the language.

It is obvious that the splitting witness of K is not unique, but they are equivalent. The computation of the finest splitting of a set of formulas refers to [23].

We can know ${E (A_{1}),…, E (A_{n})}$ is a partition of the set $P S$ of atoms of language $L$ if $E = {E_{i}}_{i \in I}$ is a splitting of a set A of formulas. But ${A_{i}}_{i \in I}$ is not the splitting witness of A by Definition 1. We will give an example to show the result, as follows:

Example 3 Let set ${p, q, r}$ be entire propositional symbols of the proposition language and $A = C n ({p, p \to q})$ . Then set ${p, q, \neg ⊥}$ of formulas is the splitting witness of ${{p}, {q}, {r}}$ finest splits A . However, ${{E (p)}, {E (q)}, {E (\neg ⊥)}}$ , i.e., ${{p}, {q}, \emptyset}$ is not the finest splitting of A under the language $L_{{p, q, r}}$ .

However, the result holds when we revise only the language we discussed.

Proposition 1 Let $A_{1}, A_{2},…, A_{n}, A \subseteq L$ with $E (A_{i}) \cap E (A_{j}) = \emptyset$ for $i \neq j$ and $\cup_{i = 1}^{n} A_{i} ⊣ ⊢ A$ with $⊬ A_{i}$ and $A_{i} ⊬ L$ . Then ${E E (A_{1}),…, E E (A_{n})}$ is a partition of $E E (A)$ , the set of essential atoms of A, if and only if ${{E E (A_{i} {)}}_{i \in I}, {x_{i}}_{x_{i} \in E (A) - E E (A)}}$ is the finest splitting of A under language $L_{A}$ . Moreover, ${E E (A_{1}),…, E E (A_{n})}$ is the finest partition of $E E (A)$ if and only if ${E (A_{i})}_{i \in I}$ is the finest splitting of A under language $L_{E E (A)}$ .

Proof: The proof of this proposition is clear when we focus the non-essential atoms of a set of formulas in a given propositional language by the definition of splitting and essential atoms of language.

2.3. Definability and Beth's theorem

Definability is an important concept and tool in logic reasoning. We will first recall the definition of two forms of definability:

Definition 2 (Implicit Definability). Let $A \subseteq L$ , $X, Y \subseteq P S$ and $y \in P S$ .

A implicitly defines y in terms of X if and only if $\forall \vec{α} \in Ω_{X}$ , $\vec{α} \land A ⊨ y$ or $\vec{α} \land A ⊨ \neg y$ .

A implicitly defines Y in terms of X if and only if A implicitly defines y in terms of X for every $y \in Y$ .

Definition 3 (Explicit Definability; Definition of a propositional symbol). Let $A \subseteq L$ , $X \subseteq P S$ and $y \in P S$ . A explicitly defines y in terms of X if and only if there exists a formula $Φ_{X} \in L_{X}$ s.t. $A ⊨ Φ_{X} \Leftrightarrow y$ . In such a case, $Φ_{X}$ is called a definition of y on X in A.

What is the natural relationship between the two definitions of definability? Beth's definability theorem in mathematical logic is a well-known result that connects implicit definability of a property to its explicit definability; specifically, the theorem states that the two senses of definability are equivalent.

Theorem 4 (Propositional projective Beth's theorem [24]). Let $A \subseteq L$ , $X, Y \subseteq P S$ and $y \in P S$ . A explicitly defines y in terms of X if and only if A implicitly defines y in terms of X.

Using Definition 2 and Definition 3, the following two results, which we will use in the next section, are evident (for details please refer to [13]).

Proposition 2 Let $A, Γ \subseteq L$ , $X, Z \subseteq P S$ and $y \in P S$ .

if A implicitly/explicitly defines y in terms of X and $X \subseteq Z$ , then A implicitly/explicitly defines y in terms of Z, and

if A implicitly/explicitly defines y in terms of X and $Γ ⊢ A$ , then Γ implicitly/explicitly defines y in terms of X.

3. The Local Definability Theorem on Knowledge, Based on Splitting

In the section, we will show some interesting results about the localization of robotic knowledge by propositional definability.

3.1. Implicit local definability theorem, based on splitting

Lemma 1 Let $X \subseteq P S$ and $y \in P S$ . Let ${E_{i}}_{i \in I}$ be the finest splitting of a set A of formulas and the family ${A_{1}, A_{2},…, A_{n}}$ be a splitting witness of A in $L_{P S}$ . If A implicitly defines y in terms of X, then A_i implicitly defines y in terms of $X \cap E (A_{i})$ , where $y \in E_{i}$ . Moreover, A implicitly defines y in terms of X if and only if A_i implicitly defines y in terms of $X \cap E (A_{i})$ where $y \in E_{i}$ .

Proof: A implicitly defines y in terms of X whenever A_i implicitly defines y in terms of $X \cap E (A_{i})$ , where $y \in E_{i}$ because of Proposition 2, $A ⊢ A_{i}$ and $X \cap E (A_{i}) \subseteq X$ . We then need only to prove if A implicitly defines y in terms of X, then A_i implicitly defines y in terms of $X \cap E (A_{i})$ , where $y \in E_{i}$ .

Let any $\vec{β} \in Ω_{X \cap E (A_{i})}$ and for any extension $\vec{α} \in Ω_{X}$ of $\vec{β}$ . By the definition of definability and A implicitly defines y in terms of X, we know $\vec{α} \land A ⊢ y$ or $\vec{α} \land A ⊢ \neg y$ . Without loss of generality, we assume that $\vec{α} \land A ⊢ y$ . Let $\vec{α} = L_{1} \land L_{2} \land … \land L_{m}$ and $A_{j}^{'} = A_{j} \cup {L_{i} : E (L_{i}) \in E (A_{j})}$ . Evidently, we then have $\vec{β} = {L_{i} : E (L_{i}) \in E (A_{i})}$ by $\vec{α}$ is an extension of $\vec{β}$ and still know $A_{1}^{'}, A_{2}^{'},…, A_{n}^{'} ⊢ y$ by $\vec{α} \land A ⊢ y$ and ${A_{1}, A_{2},…, A_{n}} ⊣ ⊢ A$ . Hence, we know that $A_{i}^{'} ⊢ y$ by parallel interpolation theorem and atom $y \in E (A_{i})$ . Hence, $A_{i} \land \vec{β} ⊢ y$ . Moreover, A_i implicitly defines y in terms of $X \cap E (A_{i})$ , since $\vec{β} = {L_{i} : E (L_{i}) \in E (A_{i})}$ .

Theorem 5 (Localization of Implicit Definability Theorem) Let $X \subseteq P S$ and $y \in P S$ , ${E_{i}}_{i \in I}$ be the finest splitting of a set A of formulas and the family ${A_{i} : i \in I}$ be a splitting witness of A in $L_{P S}$ . A implicitly defines y in terms of X if and only if A_i implicitly defines y in terms of $X \cap E_{i}$ , where $y \in E_{i}$ .

Proof: It is evident that the proof holds up by using Lemma 1 repeatedly.

We will use a graph to describe the equal relations between implicit definition and localization of definition on atoms over the finest splitting in Fig 2.

Figure 2.

The Equation Graph about Global-Local Definition on atom over the Finest Splitting

Lemma 2 Let $X, Y \subseteq P S$ , ${E_{i}}_{i \in I}$ be the finest splitting of a set A of formulas and the family ${A_{i} : i \in I}$ be a splitting witness of A in $L_{P S}$ . $X \subseteq \cup_{i} E (A_{i})$ and A implicitly defines Y in terms of X if and only if A_i implicitly defines Y_i in terms of X_i for any i where Y_i is a partition of Y and $X_{i} = X \cap E (A_{i})$ .

Proof: From right to left: Let A_i implicitly define Y_i in terms of X_i for any i and $Y_{i} = Y \cap E (A_{i})$ is the partition of Y. Then A_i implicitly defines y in terms of X_i for any $y \in Y_{i}$ . By Theorem 5 and $X_{i} = X \cap E (A_{i})$ is the partition of X, we have A implicitly defines Y in terms of X. Hence A implicitly defines Y_i in terms of X. Moreover, A implicitly defines Y in terms of X.

From left to right: Let $X \subseteq \cup_{i} E (A_{i})$ and A implicitly define Y in terms of X. We know that A implicitly defines y in terms of X for any $y \in Y$ . By Lemma 1, we have A_i implicitly defines Y in terms of $X \cap E (A_{i})$ where $y \in E_{i}$ . Let $X_{i} = X \cap E (A_{i})$ . Clearly it is the partition of X by $X \subseteq \cup_{i} E (A_{i})$ and A_i implicitly defines Y in terms of X_i. Let $Y_{i} = {y \in Y : A_{i}$ implicitly define y in terms of $X_{i}}$ . Clearly it is the partition of Y.

The Lemma is not suitable for all conditions because $X \subseteq \cup_{i} E (A_{i})$ . Hence we show that the following theorem does not satisfy the condition. The proof is easy when we deal with the splitting witness ${A_{i}}_{i \in I}$ .

Theorem 6 (Localization Implicit Definability Theorem over set of propositional symbols) Let $X, Y \subseteq P S$ , ${E_{i}}_{i \in I}$ be the finest splitting of a set A of formulas and the family ${A_{i} : i \in I}$ be a splitting witness of A in $L$ . A implicitly defines Y in terms of X if and only if A_i implicitly defines Y_i in terms of X_i for any i where ${Y_{i} : i \in I}$ is a partition of Y and $X_{i} = X \cap E_{i}$ .

We will use a graph to describe the equal relations between implicit definition and localization of definition on set over the finest splitting in Fig 3.

Figure 3.

The Equation Graph about Global-Local Definition on set over the Finest Splitting

3.2. Explicit local definability theorem based on splitting

Lemma 3 Let $X \subseteq P S$ and $y \in P S$ . Let ${E_{i}}_{i \in I}$ be the finest splitting of a set A of formulas and the family ${A_{i} : i \in I}$ be a splitting witness of A in $L_{P S}$ . If A explicitly defines y in terms of X, then A_i explicitly defines y in terms of $X \cap E (A_{i})$ where $y \in E_{i}$ . Moreover, A explicitly defines y in terms of X if and only if A_i explicitly defines y in terms of $X \cap E (A_{i})$ where $y \in E_{i}$ .

Proof: A explicitly defines y in terms of X whenever A_i explicitly defines y in terms of $X \cap E (A_{i})$ where $y \in E_{i}$ because of Proposition 2, $A ⊢ A_{i}$ and $X \cap E (A_{i}) \subseteq X$ . We then need only to prove if A explicitly defines y in terms of X, then A_i explicitly defines y in terms of $X \cap E (A_{i})$ where $y \in E_{i}$ .

By A explicitly defines y in terms of X and Beth's Theorem, we have A implicitly defines y in terms of X. We then know that A_i implicitly defines y in terms of $X \cap E (A_{i})$ where $y \in E_{i}$ by Lemma 1. Hence A_i explicitly defines y in terms of $X \cap E (A_{i})$ where $y \in E_{i}$ by Beth's Theorem.

We can prove the Lemma directly without using the results in Lemma 1. However, it is complex.

Theorem 7 (Localization Explicit Definability Theorem over set of propositional symbols) Let $X, Y \subseteq P S$ , ${E_{i}}_{i \in I}$ be the finest splitting of a set A of formulas and the family ${A_{i} : i \in I}$ be a splitting witness of A in $L_{P S}$ . $X \subseteq \cup_{i} E (A_{i})$ and A explicitly defines Y in terms of X if and only if A_i explicitly defines Y_i in terms of X_i for any i where ${X_{i} = X \cap E (A_{i})}_{i \in I}$ and ${Y_{i}}_{i \in I}$ are the partition of X and Y.

Proof: It is evident that the proof uses Lemma 3 repeatedly.

The figure 2 also shows the global-local relation on explicit definability.

Lemma 4 Let $X, Y \subseteq P S$ , let ${E_{i}}_{i \in I}$ be the finest splitting of a set A of formulas and the family ${A_{i} : i \in I}$ be a splitting witness of A in $L_{P S}$ . $X \subseteq \cup_{i} E (A_{i})$ and A explicitly defines Y in terms of X if and only if A_i explicitly defines Y_i in terms of X_i for any i where ${Y_{i} : i \in I}$ is a partition of Y and $X_{i} = X \cap E (A_{i})$ .

Proof: From right to left: Let A_i explicitly define Y_i in terms of X_i for any i and $Y_{i} = Y \cap E (A_{i})$ is the partition of Y. Then A_i explicitly defines y in terms of X_i for any $y \in Y_{i}$ . By Theorem 7 and $X_{i} = X \cap E (A_{i})$ is the partition of X, we have A explicitly defines Y in terms of X. Hence A explicitly defines Y_i in terms of X. Moreover, A explicitly defines Y in terms of X.

From left to right: Let $X \subseteq \cup_{i} E (A_{i})$ and A explicitly define Y in terms of X. We know that A explicitly defines y in terms of X for any $y \in Y$ . By Theorem 1, we have A_i explicitly defines Y in terms of $X \cap E (A_{i})$ where $y \in E_{i}$ . Let $X_{i} = X \cap E (A_{i})$ . Clearly it is the partition of X by $X \subseteq \cup_{i} E (A_{i})$ and A_i explicitly defines Y in terms of X_i. Let $Y_{i} = {y \in Y : A_{i}$ explicitly define y in terms of $X_{i}}$ . Clearly it is the partition of Y.

The Lemma is not suitable for all conditions because $X \subseteq \cup_{i} E (A_{i})$ . Therefore, we show the following theorem to miss the condition. The proof is easy when we deal with the splitting witness ${A_{i}}_{i \in I}$ .

Theorem 8 (Localization Explicit Definability Theorem over set of propositional symbols) Let $X, Y \subseteq P S$ , Let ${E_{i}}_{i \in I}$ be the finest splitting of a set A of formulas and the family ${A_{i} : i \in I}$ be a splitting witness of A in $L_{P S}$ . A explicitly defines Y in terms of X if and only if A_i explicitly defines ${Y_{i} : i \in I}$ in terms of X_i for any i where Y_i is a partition of Y and $X_{i} = X \cap E_{i}$ .

The figure 3 also shows the global-local relation on explicit definability for the set.

4. Related and Future Work

In mathematical logic, Beth definability connects the implicit definability of a property and its explicit definability [12]. Specifically, the theorem proposed by Evert Willem Beth states that the two senses of definability are equivalent [24]. It is a well-known technology in logic that definability can reduce irrelevant factors in knowledge base presented by logic. There has been a lot of literature on Beth definability in logic and related fields [12, 25, 11, 13, 26]. In this paper, we first split robotic knowledge base into the finest robotic sub-knowledge base without common propositional atoms each other. We then proposed the relation of definability of robotic knowledge base and robotic sub-knowledge base. New splitting technology was introduced into definability and given some interesting results on the computational task. To our best knowledge, there is no previous literature related to our methods.

Parikh reviews the relationship between interpolation theorem and definition in [13]. Interpolation theorem in mathematical logic was first proved for first-order logic by William Craig in 1957 [21, 12] and is a study on the relationship between various logical theories. Craig's interpolation has many applications, including consistency proofs, model checking, proofs in modular specifications and modular ontologies [11].

Kourousias and Makinson's framework was built upon classical propositional logic. An open question was posted in [19]: How far can the results be established for sub-classical (e.g., intuitionistic) consequence relations or supra-classical ones? This is by no means a trivial question, because Kourousias and Makinson's proof of the Finest Splitting Theorem is based on Craig's Interpolation Theorem, which fails in many non-classical logics [12]. In addition, Parikh's relevance criterion is a syntactical requirement, which is sensitive to variations of languages.

Parikh also discusses the relationship between interpolation theorem and parallel interpolation theorem. A natural question was proposed as follows [13]:

Question:: Is there also a parallel counterpart to the Beth definability theorem?

In the future we will continue to discuss Parikh's open problem.

Now we simply discuss an interesting result in the base computation proposed by [25] using localization method based on splitting technology proposed by Parikh [14]. Because of the equivalence between implicitly defines and explicitly defines, we now use $X ⊑_{A} Y$ to represent A implicit/explicitly defines Y in terms of X. We will first recall the definition of base about definability in [25].

Definition 4 (Base) Let $A \in L$ and $X, Y \subseteq P S$ . X is a minimal defining family, for short a base, for Y w.r.t. A, if and only if $X ⊑_{A} Y$ holds and there is no proper subset $X^{'}$ of X such that $X^{'} ⊑_{A} Y$ . The set of all bases for Y w.r.t. A is denoted by $B S_{A} (Y)$ .

We will show the relation between the set of bases over an entire set of atoms and the set of bases for all its elements in [25].

Lemma 5 Let $A \in L$ and $Y = {y_{1}, y_{2},…, y_{p}} \subseteq P S$ .

B S_{A} (Y) = m i n ({\cup_{i = 1}^{p} B_{i} | B_{i} \in B S_{A} ({y_{i}})}, \subseteq) .

By the lemma, we can propose a conjecture about the computation of base by all atoms set over the relevant sub-knowledge base of the sub-language. This will reduce the computational task after the splitting of the knowledge base.

Conjecture 1 Let $A \in L$ and $Y = {y_{1}, y_{2},…, y_{p}} \subseteq P S$ . If ${E_{i}}_{i \in I}$ is the (finest) splitting of A, i.e., $A_{1}, A_{2},…, A_{n} ⊣ ⊢ A$ , $E (A_{i}) \cap E (A_{j}) = \emptyset for a n y i \neq j$ and $E (A_{i}) \subseteq E_{i}$ for all $i \in I$ then

B S_{A} (Y) = m i n ({\cup_{i = 1}^{p} B_{i} | B_{i} \in B S_{A_{i}} ({y_{i}})}, \subseteq) .

In the future, we will continue to discuss the base computation using the localization method based on Parikh's splitting technology.

5. Conclusion

Recently, an increasing number of robots with limited resources for computation and storage need to exchange vast common knowledge using the cloud system and share external environment information quickly with their neighbouring robotic companions. Evidently, it is impossible for all robots to receive knowledge from the cloud system and neighbour robotic companions in real time. Hence, we can only exchange relevant and local knowledge that comes from large-scale and complex knowledge between intelligent robots and the cloud system or neighbour robotic companions. As for the localization of intelligent robots, especially cloud robots or robots working in special environments such as underwater, mines and building sites, knowledge-base change is more important. In order to decide quickly on the definability in propositional logic, we demonstrate two interesting results on the local definability of robotic large-scale and complex knowledge, which uses propositional logic by computing the sub-language's knowledge based on Parikh's splitting method.

Footnotes

6. Acknowledgements

The authors thank the three anonymous referees for their useful comments. This material is based upon work funded by the National Nature Science Foundation of China under grant No. 61262029, 61370173, Zhejiang Provincial Natural Science Foundation of China under Grant No. LY16F020015, Science and Technology of Zhejiang Province under grant No. 2014C31084.

1

This is because the contraction operation is applied to the finest splitting of the original belief set. The finest splitting of a belief set is not necessarily logically closed.

References

Craig

J.J.

. Introduction to Robotics. Pearson Prentice Hall. Upper Saddle River, NJ, 2005.

Oudeyer

P-Y

. On the impact of robotics in behavioral and cognitive sciences: from insect navigation to human cognitive development. IEEE Transactions on Autonomous Mental Development, 2(1):2–16, 2010.

Gutiérrez-Garcia

Ana G.

del Angel Ortiz

Rusalky

Contreras

Carlos M.

González

Montes Fernando M.

. Social interaction test between a rat and a robot: A pilot study. International Journal of Advanced Robotic Systems, 2016.

Liu

Yong

Tang

Feng

, and Zeng

Zhiyong

. Feature selection based on dependency margin. IEEE Transactions on CYBERNETICS, 45(6):1209–1221, 2015.

Liu

Yong

Xiong

Rong

, and Li

. Robust and accurate multiple-camera pose estimation toward robotic applications. International Journal of Advanced Robotic Systems, 2014.

Moubarak

Paul

Ben-Tzvi

Pinhas

. Modular and Reconfigurable Mobile Robotics. Journal of Robotics and Autonomous Systems, 60(12):1648–1663, 2012.

Abbeel

Pieter

Goldberg

Ken

Kehoe

Ben

Patil

Sachin

. A Survey of Research on Cloud Robotics and Automation. IEEE Transaction on Automation Science and Engineering, 12(2):398–409, 2015.

Thielscher

Michael

. Reasoning Robots: The Art and Science of Programming Robotic Agents. Springer, 2005.

Hertzberg

Joachim

Chatila

Raja

. AI Reasoning Methods for Robotics. Springer Handbook of Robotics, 207–223, 2008.

10.

Jianmin

. A cognitive architecture for a service robot: an answer set programming approach. In Proceedings of the 25th International Conference on Logic Programming (ICLP-09), LNCS 5649, 532–533, 2009.

11.

Harrison

John

. Handbook of Practical Logic and Automated Reasoning. Cambridge, New York: Cambridge University Press, 2009.

12.

van Benthem

Johan

. The many faces of interpolation. Synthese, 164(3):451–460, 2008.

13.

Parikh

Rohit

. Beth definability, interpolation and language splitting. Synthese, 179(2):211–221, 2011.

14.

Parikh

Rohit

. Beliefs, belief revision, and splitting languages. Logic, language, and Computation, 2:266–278, 1999.

15.

Alchourrón

Carlos E.

Gärdenfors

Peter

, and Makinson

David

. On the logic of theory change: Partial meet contraction and revision functions. J. Symb. Log., 50(2):510–530, 1985.

16.

Hansson

Sven Ove

. A textbook of belief dynamics: Theory change and database updating. Kluwer Academic Publishers, 1999.

17.

Eiter

Thomas

Gottlob

Georg

. On the complexity of propositional knowledge base revision, updates, and counterfactuals. Artificial Intelligence, 57(2–3): 227–270, 1992.

18.

Nebel

. Syntax-based approaches to belief revision. In Gärdenfors , editor, Belief Revision, pages 52–88. Cambridge University Press, 1992.

19.

Kourousias

George

Makinson

David

. Parallel interpolation, splitting, and relevance in belief change. J. Symb. Log., 72(3):994–1002, 2007.

20.

Makinson

David

. Friendliness for logicians. In We Will Show Them! essays in honour of Gabbay, Vol 2, pages 259–292, 2005.

21.

Craig

William

. Three uses of the herbrand-gentzen theorem in relating model theory and proof theory. J. Symb. Log., 22(3):269–285, 1957.

22.

Gabbay

Dov M

Maksimova

Larisa

. Interpolation and definability: modal and intuitionistic logics. Clarendon Press, 2005.

23.

Maonian

Zhang

Mingyi

. Algorithms and application in decision-making for the finest splitting of a set of formulae. Knowl.-Based Syst., 23(1):70–76, 2010.

24.

Chang

C.C.

Keisler

H.J.

. Model Theory. North Holland, 1990.

25.

Lang

Jérôme

Marquis

Pierre

. On propositional definability. Artif. Intell., 172(8–9):991–1017, 2008.

26.

Maonian

Zhang

Dongmo

, and Zhang

Mingyi

. Language splitting and relevance-based belief change in horn logic. In AAAI 2011, 268–273, 2011.

The Local Definability of Robotic Large-Scale Knowledge Based on Splitting

Abstract

Keywords

1. Introduction

2. Preliminaries

2.1. Interpolation Theorem and Parallel Interpolation Theorem

2.2. Language splitting over propositional logic

2.3. Definability and Beth's theorem

3. The Local Definability Theorem on Knowledge, Based on Splitting

3.1. Implicit local definability theorem, based on splitting

3.2. Explicit local definability theorem based on splitting

4. Related and Future Work

5. Conclusion

Footnotes

6. Acknowledgements

1

References