An Application of the PCol Automata in Robot Control

An Application of the PCol Automata in Robot Control Miroslav Langer1, Ludˇek Cienciala1, Lucie Ciencialov´a1, Michal Perdek1, and Alice Kelemenov´a1 Institute of Computer Science and Research Institute of the IT4Innovations Centre of Excellence, Silesian University in Opava, Czech Republic {miroslav.langer, ludek.cienciala, lucie.ciencialova, michal.perdek, alice.kelemenova}@fpf.slu.cz Summary. The P colonies were introduced in [6] as a variant of the bio-inspired computational models called membrane systems or P systems. In [2] we divided agents into the groups according the function they provide; we introduced the modularity on the P colonies. PCol automata are an extension of the P colonies by the tape (see [1]). This is an accepting computational device based on the very simple computational units. In this paper we combine the approach of the modules in the P colonies and of the PCol automata and we introduce the PCol automaton driven robot. 1 Introduction Recently, the robotics has been more and more expanding and intervening in various branches of science like biology, psychology, genetics, engineering, cognitive science, neurology etc. An effort to create robots with an artificial intelligence which are able to cogitate or solve various types of problems refers to hardware and software limits. Many of these limits are managed to be eliminated by the interdisciplinary approach which allows creating new concepts and technics suitable for the robot control and facture of the new hardware. Very robot control is often realised by the classical procedures known from the control theory (see [9]), concepts inspired by the biology, evolution concepts (see [5]) or with use of the decentralized approaches (see [8]). The autonomous robot’s behaviour and its control are realized by the control unit. Robots are equipped with the various types of sensors, cameras, gyroscopes and further hardware which all together represents the robots perception. These hardware components provide to the control unit the information about the actual state of the environment in which the robot is present and also the information about the internal states of the robot. After the transformation of these inputs 154 M. Langer et al. there are generated a new data which are forwarded to the actuators like the wheels, robotic arm etc. Thus the robot can pass the obstacle by using the sensors and adjusting the speed of the particular wheels. So the objective of the control unit is to transform input signals to the output signals which consequently affect the behaviour of the robot. These changes in the behaviour cause that the robot interacts with the environment and in the sight of the observer the robot seems to be intelligent. Transformation of these signals can be done computationally in various ways with use of the knowledge or fuzzy knowledge systems, artificial neural networks, or just with use of the membrane systems or the P systems as it will be shown in this paper. The development, design and the realization of the new approaches and techniques through which is possible to realize function of the control unit is one of the key subject of the development of the artificial intelligence and the robotics. P colonies were introduced in 2004 as abstract computing devices composed from independent single membrane agents, reactively acting and evolving in a shared environment. P colonies reflect motivation from colonies of grammar systems, i.e. the idea of the devices composed from as simple as possible agents placed in a common environment; the system, which produce nontrivial emergent behaviour, using the environment only as the communication medium with no internal rules. P colonies consist of single cells “floating” in a common environment. Sets of rules of cells are structured to simple programs in P colonies. Rules in a program have to act in parallel in order to change all objects placed into the cell, in one derivation step. Objects are grouped into cells or they can appear in their completely passive environment in which these cells act. We assume that the environment contains several copies of the basic environmental objects (denoted in the formal definition of P colonies by e), as many as needed to perform a computation. Moreover the environment can contain also finite number of non-basic objects, and each entity contains a fixed (intuitively small) number of (possibly identical) objects. Cells as basic computing agents of P colonies are of as much as possible restricted complexity and the capability. Each agent is associated with a small number of objects present inside it and with a set of rules forming programs for processing these objects. Two types of rules are considered, namely the evolution rules acting inside agents, and the communication rules providing elementary interactions between the agents and the environment. Each of the evolution rules is able to rewrite one object in the agent into another object which will remain inside this agent. Evolution rule is denoted by a→b. The communication rules consist in the mutual exchanging of one object inside the agent, and one object in its environment. We denote communication rule by c↔d, where the object appearing in the agent is written in the left side of the relation ↔. Moreover checking rules are considered to extend the abilities of agents follows: assume that communication rule can be chosen from two possibilities with the first one having higher priority. The rule associated with the agent An Application of the PCol Automata in Robot Control 155 with greater priority has to be active. The agent checks the possibility to execute the communication rule having higher priority. Otherwise, the second communication rule can be treated. We denote a checking rule being a pair c↔d/c0↔d0. AP colony with checking rules will be called also a P colony with priority. The program of an agent allows changing all objects in the cell simultaneously and deterministically by different rules, so the number of objects in an agent is identical with the number of rules in each of its programs. P colony starts a computation with given objects in the environment and in each agent. We associate a result with a halting computation, in the form of the number of copies of a distinguished object in the environment. Both parallel as well as sequential computational mode of P colonies is discussed depending on the amount of agents acting in one derivation step. In the first case, each agent which can apply any of its programs has to choose one non-deterministically, and apply it; in the sequential case one agent, non-deterministically chosen, is allowed to act. P colonies are computationally complete, i.e. all the number sets computable by Turing machines are computable also by P colonies. This gives the interpretation that the environment is essential as a medium for communication and for storing information during the computation, even with no structure and no information in the environment at the beginning of the computation. The power of cooperating agents of a very restricted form can be dramatically different from the power of individual agents. For overview on P colonies we refer to [7], [3], [4]. Pcol automaton was introduced in order to describe the situation, when P colonies behave according to the direct signals from the environment (see [1]). This modification of the P colony is constructed in order to recognize input strings. In addition to the writing and communicating rules usual for a P colony cells in Pcol automata have also tape rules. Tape rules are used for reading next symbol on the input tape and changing an object in cell(s) to the read symbol. Depending on the way how tape rules and other rules can take a part in derivation process several computation modes are treated. After reading the whole input word, computation ends with success if the Pcol automaton reaches one of its accepting configurations. So, in accordance with finite automata, Pcol automata are string accepting devices based on the P colony computing mechanisms. Agents can be grouped to different modules specified for some activities as illustrated in [2] for P colonies. This approach will be used in the present paper for Pcol automata illustrated in the case of robot control. Throughout the paper we assume that the reader is familiar with the basics of the formal language theory. 2 Preliminaries on the P colonies P colony is a computing device composed from the environment and the independent organisms called agents or cells. The agents live in the environment. Each agent is represented by a collection of objects embedded in a membrane, which 156 M. Langer et al. is constant during the computation. A set of programs, which are composed from the rules, is associated with each agent. The rule can be either evolution rule or communication rule. The evolution rules are of the form a→b. It means that the object ainside the agent is rewritten (evolved) to the object b. The communication rules are of the form c↔d. When the communication rule is performed, the object cinside the agent and the object din the environment swap their places. Thus after execution of the rule, the object dappears inside the agent and the object c is placed in the environment. In [6] the set of programs was extended by the checking rules. These rules give an opportunity to the agents to opt between two possibilities. The rules are in the form r1/r2. If the checking rule is performed, then the rule r1has higher priority to be executed over the rule r2. It means that the agent checks whether the rule r1is applicable. If the rule can be executed, then the agent is compulsory to use it. If the rule r1cannot be applied, then the agent uses the rule r2. The environment contains several copies of the basic environmental object denoted by e. The number of the copies of ein the environment is sufficient, it means that each agent which wants to receive the symbol efrom the environment using the communication rule will receive it. We will handle parallel model of P colonies with checking rules (denoted by NPCOLparK) in this paper. At each step of the parallel computation each agent tries to apply one usable program. If the number of applicable programs is higher than one, then the agent chooses one of the rules nondeterministically and the maximal possible number of agents is active at each step of the computation. Each P colony is characterised by three characteristics; the capacity k, the degree nand the height h; denoted by NP COLparK(k, n, h). The capacity kis the number of the objects inside each agent, the degree nis the number of agents in the P colony, the height his the maximal number of programs associated with the agent of the P colony. 2.1 Modularity in the therms of P colonies The research of the P colonies suggested that particular agents are providing the same function during the computation. This served as the inspiration to introduce the modules in the P colonies. In the [2] we grouped agents of the P colony simulating computation of the register machine into the modules. The agents providing subtraction were classified into the subtraction module, agents providing addition were sorted into the addition module, agents controlling the computation were grouped into the control module, etc. The program of simulated register machine is stored in the control module, so changing the program of the register machine does not mean reprograming all the agents of the P colony but the change of the control module. The inspiration to introduce modularity was found in living organisms where group of cells providing one function evolved into the organs and whole organism is composed by these organs. An Application of the PCol Automata in Robot Control 157 In this paper, this approach to define modules will be used for the robot control. One module for each module of the robot (sensors, actuators) will be defined. For planning the robots action will be used the tape; PCol automaton. 2.2 PCol automata By extending the P colony by the input tape we obtain a string accepting/ recognizing device; the PCol automaton (see [1]). The input tape contains the input string which can be read by the agents. The input string is the sequence of the symbols. To access the tape the agents use special tape rules (T-rules). The rules not accessing the tape are called non-tape rules (N-rules). The computation and use of the T-rules is very similar to the use of the rules in the P colonies. Once any of the agents uses its T-rule, the actual symbol on the tape is considered as read. The only difference between the tape and the environmental symbol is that the tape symbol can access arbitrary many agents at the same time. Definition 1. PCol automaton of the capacity kand with nagents, k, n ≥1is a construct Π= (A, e, VE,(O1, P1), . . . (On, Pn), F), where •Ais a finite set, an alphabet of the PCol automaton, its elements are called objects; •eis an environmental object, e∈A; •VEis a multiset over A− {e}defining the initial content of the environment; •(Oi, Pi),1≤i≤nis an i-th agent –Oiis a multiset over Adefining the initial content of the agent, |Oi|=k, –Piis a finite set of the programs,Pi=Ti∪Ni, Ti∩Ni=∅, where every program is formed from krules of the following types: ·the tape rules (T-rules for short) ·aT →bare called the rewriting T-rules; ·aT ↔bare called the communicating T-rules; ·the non-tape rules (N-rules for short) ·a→bare called the rewriting N-rules; ·c↔dare called the communicating N-rules; ·Tiis a set of tape programs (T-programs for short) consisting from one T-rule and k−1N-rules. ·Niis a set of non-tape programs (N-programs for short) consisting only from N-rules. •Fis a set of accepting configurations of the PCol automaton, each state is a(n+ 1)-tuple (vE;v1, . . . , vn), where: –vE⊆(A−{e})∗is a multiset of the objects different from the object eplaced in the environment; –vi,1≤i≤nis a content of the i-th agent; 158 M. Langer et al. The configuration of the PCol automaton is (n+2)-tuple (wT;wE;w1, . . . , wn), where wT∈A∗the unprocessed (unread) part of the input string, wE∈(A− {e})∗ is a multiset of the objects different from the object eplaced in the environment of the PCol automaton and wi,1≤i≤nis a content of the i-th agent. The computation starts in the starting configuration defined by the input string on the tape the initial content of the environment and the initial content of the agents. Actual symbol on the input tape we consider as read iff at least one agent uses its T-program in the particular derivation step. We define the rule rin following way: r=aT/ −→ b⇒       left (r) = a right (r) = b export (r) = ε import (r) = ε r= (cT/ ←→ d)⇒       left (r) = ε right (r) = ε export (r) = c import (r) = d For each configuration (wE, w1, . . . , wn) we define set of applicable programs P(wE,w1,...,wn): • ∀p, p0∈P, p 6=p0, p ∈Pi, p0∈Pj⇒i6=j •for each p∈Pand p∈Pileft(p)∪export(p) = wi •S p∈P import(p)⊆wE For each configuration (wE, w1, . . . , wn) we define set of all sets of applicable programs P(wE,w1,...,wn) For the configuration (wE, w1, . . . , wn) and the input symbol awe define: •t-transition, ⇒a t: If there is at least one set of applicable programs P∈ P such that each p∈Pis the T-program with T-rule of the form xT →aor xT ↔a, x ∈Aand Pis the maximal set (there does not exists other set P0∈ P where |P0|>|P|fulfilling stated conditions). •n-transition, ⇒n: If there is at least one set of applicable programs P∈ P such that each pi∈Pis the N-program and Pis the maximal set. •tmin-transition ⇒a tmin: If there is at least one set of applicable programs P∈ P such that there exists at least one program Pis the T-program and it is in the form xT →aor xT ↔a, x ∈A, it can contain also the N-programs and Pis the maximal set. •tmax-transition ⇒a tmax: If there is at least one set of applicable programs P∈ P such that P=PN∪PTwhere PNis a set of nontape programs and PTis a maximal set of applicable tape programs of the form xT →aor xT ↔a, x ∈A, and P=PN∪PTis maximal; We denote An Application of the PCol Automata in Robot Control 159 (wE, w1, . . . , wn)⇒a/ trans (w0 E, w0 1, . . . , w0 n), trans ={t, n, tmin, tmax} where: for each j, 1≤j≤nfor which there exists p∈P∧p∈Pj,w0 j= right(p)∪import(p), if there does not exists p∈P∧p∈Pjso w0 j=wj;w0 E= wE−S p∈P import(p)∪S p∈P export(p). PCol automaton works in the t(tmax, tmin) mode of computation if it uses only t- (tmax-, tmin-) transitions. PCol automaton works in the nt (ntmax or ntmin) mode of computation if at any computation step it may use a t- (tmax- or tmin-) transition or an n-transition. A special case of the nt mode is called initial, denoted by init, if the computation of the automaton is divided in two phases: first it reads the input strings using t-transitions and after reading all the input symbols it uses n-transitions to finish the computation. The computation ends by (types of acceptance): halting (halt) - there does not exist an applicable set of programs corresponding to the computation mode. Computation is successful if it ends and the whole input tape is read. reading the last input symbol (lastsym) - the computation (successfully) ends if the last input symbol is read and there does not exist set of applicable programs corresponding to the computation mode. The computation is unsuccessful if it ends before reading the last symbol from the input tape. final state reached (finstate) - the computation ends whenever the last symbol is read as far as the automaton would not stop further. The computation is successful if the input tape is read and PCol automaton reaches the configuration from the set of the final states F. The language accepted by the PCol automaton Πis defined as a set of the words for which there exist successful computation in particular mode and type of acceptance. Definition 2. L(Π, mod, acc) = {w∈A∗|wis accepted by the computation in the mode mod with type of acceptance acc }, where mod ∈ {t, nt, tmax, ntmax, tmin, ntmin, init}and acc ∈ {halt, lastsym, finstate}. 3 Robot control using the PCol automaton Main advantage of using PCol automaton in the controlling robot behaviour is the parallel proceeding of the data done by very primitive computational units using very simple rules. By conjunction modularity and PCol automaton we obtain a powerful tool to control robot behaviour. PCol automaton is parallel computation device. Collaterally working autonomous units sharing common environment provide fast computation device. Dividing agents into the modules allows us to compound agents 160 M. Langer et al. controlling single robot sensors and actuators. All the modules are controlled by the main controlling unit. Input tape gives us an opportunity to plan robot actions. Each input symbol represents a single instruction which has to be done by the robot, so the input string is the sequence of the actions which guides the robot to reach his goal; performing all the actions. We construct a PCol automaton with four modules: Control unit,Left actuator controller,Right actuator controller and Infra-red receptor. Entire automaton is amended by the input and output filter. The input filter codes signals from the robots receptors and spread the coded signal into the environment. In the environment there is the coded signal used by the agents. The output filter decodes the signal from the environment which the actuator controllers sent into it. Decoded signal is forwarded to the robots actuators. The control unit is the main module which controls the computation. It reads the sequence of the actions from the input tape. According to the type of the action read from the tape it asks the data from the sensors modules by sending particular objects into the environment. If the answer from the sensors allows to perform the action, the control unit sends the command to the actuator controllers to perform demanded action. After sending the command to the actuator controllers the control unit waits for the announcement of the successful or the unsuccessful performance of the demanded action from the actuator controllers. If the action was fulfilled then the control unit continues in reading the input tape and performs following action. The infra-red receptors consume all the symbols released into the environment by the input filter. It releases actual information from the sensors on demand of the control unit. The infra-red receptors remove unused data from the environment. The left and right actuator controllers wait for the activating signal from the control unit. After obtaining the activating signal the controllers try to provide demanded action by sending special objects - coded signal for the output filter into the environment. When the action is performed successfully the actuators send the announcement of the successful end of the action to the control unit, the announcement of the unsuccessful end of the action otherwise. Let us introduce the formal definition of the mentioned PCol automaton: Π= (A, e, VE,(O1, P1), . . . (O7, P7),∅), where A={0L,0R,1L,1R, e, FF,FF, FL, FL, FR, FR, GF, GL, GR, IF, IL, IR, MF, ML, MR, NF, NF, NL, NL, NR, NR, R, RT, WF, WL, WR, WT}, VE={e}, Control Unit: An Application of the PCol Automata in Robot Control 161 O1={T, e}, P1={< RT T →MF;e→e >;< GFMF→MFMF>;< MFMF→ee >; < e ↔GF/e ↔R;MF→MF>;< RMF→eWT>; < RT T →ML;e→e >;< GLML→MLML>;< MLML→ee >; < e ↔GL/e ↔R;ML→ML>;< RML→eWT>; < RT T →MR;e→e >;< GRMR→MRMR>;< MRMR→ee >; < e ↔GR/e ↔R;MR→MR>;< RMR→eWT>; < ee →eWT>;< WT→e;e↔RT>} O2={T, e}, P2={< RT T →MF;e→IF>;< IF↔e;MF→WF>; < WF→e;e↔FF/e ↔NF>;< FF→GF;e→e >; < GF↔e;e→WT>;< RT T →ML;e→IL>; < IL↔e;ML→WL>;< WL→e;e↔FL/e ↔NL>; < FL→GL;e→e >;< GL↔e;e→WT>;< RT T →MR;e→IR>; < IR↔e;MR→WR>;< WR→e;e↔FR/e ↔NR>; < FR→GR;e→e >;< GR↔e;e→WT>;< R ↔e;e→WT>; < WT→e;e↔RT>} Infra-red module: O3={e, e}, P3={< e ↔FF;e→FF>;< FF↔IF/FF→e;FF→e >; < e ↔NF;e→NF>;< NF↔IF/NF→e;NF→e >; < IFe→ee;>} O4={e, e}, P4={< e ↔FL;e→FL>; < FL↔IL/FL→e;FL→e >;< e ↔NL;e→NL>; < NL↔IL/NL→e;NL→e >;< ILe→ee;>} O5={e, e}, P5={< e ↔FR;e→FR>; < FR↔IR/FR→e;FR→e >;< e ↔NR;e→NR>; < NR↔IR/NR→e;NR→e >;< IRe→ee;>} Left Actuator controller: O6={e, e}, P6={< e ↔MF;e→1L>;< MF→RT; 1L↔e >; < e ↔MR;e→1L>;< MR→RT; 1L↔e >; < e ↔ML;e→0L>;< ML→RT; 0L↔e >; < RT↔e;e→e >} Right Actuator controller: O7={e, e}, P7={< e ↔MF;e→1R>;< MF→RT; 1R↔e >; < e ↔MR;e→0R>;< MR→RT; 0R↔e >; < e ↔ML;e→1R>;< ML→RT; 1R↔e >; < RT↔e;e→e >}