Generation of rapidly-exploring random trees by using a new class of membrane systems

Generation of rapidly-exploring random trees by using a new class of membrane systems Ignacio P´erez-Hurtado, Mario J. P´erez-Jim´enez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: {perezh,marper}@us.es Abstract. Methods based on Rapidly-exploring Random Trees (RRTs) have been in use in robotics to solve motion planning problems for nearly two decades. On the other hand, models based on Enzymatic Numerical P systems (ENPS) have been applied to robot controllers for more than six years. These controllers in real robots handle the power of motors according to motion commands usually generated by planning algorithms, but today there is a lack of planning algorithms based on membrane systems for robotics. With this motivation, we provide in this paper a new variant of ENPS called Random Enzymatic Numerical P systems with Proteins and Shared Memory (RENPSM) oriented to RRTs for planning in robotics and we illustrate it by presenting a model for generation of RRTs with holonomic limitations. We are working on the ENPS framework with the idea of moving towards a complete mobile robot system based on membrane systems, i.e. including controllers and planning; and we have incorporated new ingredients into the ENPS framework to meet the requirements of the RRT generation algorithm. 1 Introduction Robots are machines oriented to objectives equipped with actuators, sensors and computation units acting under physical constraints. Regardless of their morphology, they should accomplish tasks by acting in the real world. This is one of the main reasons by which Robot Motion Planning [4] is an eminent research area in Robotics. In general terms, the problem of motion planning can be defined in the configuration space of a robot as follows: Given (1) a start configuration state, (2) a goal configuration state, (3) a geometric description of the robot, and (4) a geometric description of the environment: find a path that moves the robot gradually from start to goal. A configuration state is a specification of the positions of all robot points relative to a fixed coordinate system. This is usually expressed as a vector of positions and orientations, for example, a rigid-body robot in a 2D world can be expressed as a vector (x, y, θ) representing the center (x, y) of the robot in a fixed coordinate system and its yaw angle θ. Since the shape of the robot is described, all of its points are then known. Several constraints can be added to this problem, the most common is to reach the goal while never touching any obstacle in the environment. Others can also be added, for example, a social robot could restrict configuration states in order to guarantee the human comfort. The configuration space of a robot can also be constrained by the type of movements the robot can perform. In this sense, non-holonomic robots are those that cannot instantly modify its direction without employing rotation in-place. On the other hand, holonomic robots can do it (assuming zero mass). For example, a holonomic robot in a 2D world can move along the xaxis and the yaxis, as well as modify its yaw angle if needed. But a non-holonomic robot can only move forward/backward and/or modify its yaw angle. This is the typical case of dual-wheeled mobile robots. Classical path planning algorithms have been widely adapted and applied to the problem of motion planning with constraints in robots, for example, in [16], an application of the Dijkstra for robot path-planning was presented. In such solutions, the general problem is usually divided into two smaller problems: the global path planning problem, as described above; and the local path planning, where the robot tries to connect two consecutive states in real-time considering constraints not included in the global plan as, for example, obstacles in movement. The accumulated error during the local planning conducts to periodically recompute the global plan. For this reason, the computational complexity of global planners is a critical point regarding to real-time constraints. Many efforts have been made to provide good global planners. For example: in [15], a new search algorithm, called D∗, is presented for path planning in real-time environments. In [7], a variant of the classical search algorithm A∗is applied to grids with blocked and unblocked cells. In [5], a new tool for path planning, called Rapidly-Exploring Random Trees (RRT), was presented. The class of RRT algorithms for path planning is based on the randomized exploration of the constrained configuration space by building a tree where nodes represent states that can be reached by the state of the corresponding parent in a fixed amount of time, so each edge contains a valid motion command to reach the state in child node. It is currently one popular method in Robot Motion Planning due to its good properties. The created RRT can be used to explore the constrained configuration space by applying search algorithms or, as presented in [6], the RRT generation algorithm can be used by itself as path planning algorithm, where two RRTs are built simultaneously, one beginning from the start configuration and another one beginning from the goal configuration. In order to execute the planned motions, each motor of the robot must be able to maintain a certain speed command for a fixed period of time. This is the function of a type of software called controller on-board of the robot. Thus, Robot Control [1] is the branch of robotics dedicated to the study and practice of controlling robots. Robot controllers are usually based on common silicon microprocessors, but in the recent years, some classes of membrane systems [8] have been in use for modelling them [12] [10] [11] [18]. Membrane systems (or P systems) are models 535 of computation based on the structure and functions of the living cells. In a Membrane system, there are objects being evolved inside compartments according to rules in a non-deterministic way with a high-level of parallelism. They were firstly used as a new technique to attack the Pversus NP problem [13], but several applications of membrane systems have been also presented: Stochastic P systems for modelling biological phenomena [14], Probabilistic P systems for modelling real ecosystems [2], Spiking Neural P systems incorporating fuzzy reasoning, for fault diagnosis and learning [17], and others. In relation to Robot Control, Numerical P Systems (NPS) were used for modelling and simulating robot controllers [12], although the initial application of NPS was related to models of Economical Processes [9]. Enzymatic Numerical P systems (ENPS) [10] were introduced as an improvement and applied to the distributed control of a swarm of mobile robots. Indeed, reactive and proportional-integral-derivative (PID) dual-wheeled robot controllers have been successfully designed and simulated by means of ENPS, as well as software simulator tools [18]. On the other hand, the robot must know its position in the environment by using sensors, that is the Robot Localization problem [3], and it has also been attacked by using ENPS [11]. The main contribution of this paper is to introduce a new variant of ENPS called Random enzymatic numerical P systems with proteins and shared memory (RENPSM), in order to simulate RRT algorithms. Since the current applications of membrane systems to Robotics are focused on controllers, localization and local planners, we propose an approximation from “the other side”: global path planning with physical constraints. The idea is to provide a complementary approach walking towards a mobile dual-wheeled robot system based completely on membrane systems. We are using ENPS because it is the framework of the state of the art in membrane computing and robotics. On the other hand, the motivation of the new ingredients is related to meet the requirements for the computation of the RRT algorithm: –Random numbers: Since the RRT algorithm is a randomized method to explore the physical space. –Shared memory: Because the algorithm can be parallelized using processes sharing common variables (for instance, at some instant each membrane must read a specific value stored in a distinguished membrane: the shared memory). –Proteins: Since the algorithm performs steps that must be sequentially executed, proteins for synchronization are used. This paper is structured as follows. In the next section, the rapidly-exploring random trees (RRTs) are described with some details. Section 3 is devoted to introduce the Membrane Computing framework called random enzymatic numerical P systems with proteins and shared memory (RENPSM, for short), where the RRT generation algorithm will be simulated. In Section 4, the simulation of the RRT algorithm by using RENPSM systems is presented. Finally, conclusions and future work are drawn. 536 2 Rapidly-exploring Random Trees A RRT [5] is a randomized tree structure for rapidly exploring a state space X from an initial position/state xinit. It can be successfully used for nonholonomic and kinodynamic path planning in robotics [6]. Nodes in a RRT represent possible reachable states in a 2D or 3D world, for robots with nonholonimic constraints in a 2D environment this is given by (x, y, θ) where (x, y) are the Cartesian coordinates of the robot position and θ is the heading angle. If we consider a kinodynamic planning problem, a node encodes both position and velocity of the robot. For robots with holonomic constraints in a 2D world, the heading angle can be ignored. It is assumed that a fixed obstacle region Xobs ⊂Xmust be avoided, so the nodes of the RRT are states in Xfree, the complement of Xobs in X. Edges in a RRT represent transitions between reachable states, they are labelled with the command uthat the robot should execute for a fixed amount of time ∆t in order to change the corresponding states. For a dual-wheeled robot with nonholonomic constraints, it can be represented by the pair of linear and angular velocity (v, ω) to be sent to the controller. If we are working with holonomic constraints, all the points in the space can be reached applying a linear velocity, so edges are labelled with instant linear velocities and a new state xnew can be reached from another state xconnected by an edge labelled with uby applying xnew =x+u·∆t Algorithm 1 GENERATE RRT(xinit, K, ρ, ∆t, X, Xobs, dmin) Vτ← {xinit} Eτ← ∅ for k= 1 to Kdo xrand ←RANDOM STATE(X); xnear ←NEAREST NEIGHBOR(xrand, τ); if DISTANCE(xrand, xnear )≥dmin then u←SELECT INPUT(xrand, xnear ); if ¬COLLISION(xnear , u, ∆t, Xobs)then xnew ←NEW STATE(xnear , u, ∆t); Vτ←Vτ∪ {xnew } Eτ←Eτ∪ {(xnear , xnew )} end if end if end for return τ= (Vτ, Eτ) This is an iterative algorithm to generate a RRT [5], where: –xinit is the initial state. –Kis the number of iterations to build the RRT. –ρis a prefixed distance metric. 537 –∆t is a fixed amount of time for transitions. –Xis the state space. –Xobs is the obstacle state space. –dmin is the minimum distance threshold according to ρin order to include a new node in the RRT. –τ= (Vτ, Eτ) is the RRT generated. –RANDOM STATE(X) is a function to get a random state from X –NEAREST NEIGHBOR(xrand, τ) is a function to get the closest node to xrand in τaccording to ρ. –DISTANCE(xrand, xnear) is a function to get the distance of xrand to xnear according to ρ. –SELECT INPUT(xrand, xnear) is a function to get the velocity input that should be commanded to the robot in order to achieve state xrand from xnear. –COLLISION(xnear, u, ∆t, Xobs) is a function returning true if a collision could be produced moving the robot from state xnear by applying the input ufor ∆t time considering the obstacles in Xobs. –NEW STATE(xnear, u, ∆t) is a function to get a new state xnew by applying the input uto the robot for ∆t time starting at state xnear. In Figure 1 it is represented a RRT generated after 5000 iterations by using Algorithm 1 with holonomic constraints and the Euclidean distance as distance metric. Fig. 1. RRT generated after 5000 iterations In order to provide a first approximation based on Membrane Computing, we use in this paper a simplified version of the standard RRT algorithm 2 for 538 holonomic robots where no obstacles have been considered and ρis the euclidean distance. Algorithm 2 GENERATE RRT((x0, y0), K, ∆t, X, dmin) Vτ← {(x0, y0)} Eτ← ∅ for k= 1 to Kdo (xrand, yrand)←RANDOM STATE(X); (xnear , ynear )←NEAREST NEIGHBOR((xrand, yrand), τ); z←ρ((xrand, yrand),(xnear , ynear )) if z≥dmin then u1←(xrand −xnear )/z, u2←(yrand −ynear )/z, xnew ←xnear +u1·∆t ynew ←ynear +u2·∆t Vτ←Vτ∪ {(xnew , ynew )} Eτ←Eτ∪ {(xnear , ynear ),(xnew , ynew )} end if end for return τ= (Vτ, Eτ) 3 Random enzymatic numerical P systems with proteins and shared memory In this section a variant of enzymatic numerical P systems incorporating new features is presented in order to simulate the generation of RRTs. Definition 1. A random enzymatic numerical P systems with proteins and shared memory (RENPSM, for short) of degree (p, q),p, q ≥1, is a tuple Π= (H, µ, P, Emem, Emem(0),{(Ph(0), V arh, V arh(0), Prh)|h∈H},R, h0) where: 1. H ={1, . . . , p ·q}∪{mem},mem /∈ {1, . . . , p ·q}, is the set of labels of the system; 2. µ is a dynamical membrane structure (a rooted tree) initially consisting of only one membrane with label h0∈ {1, . . . , p ·q}in such manner that along the computation new membranes will be created with labels in {1, . . . , p ·q}; 3. mem is the label of a distinguished component (the shared memory of the system); 4. P is a finite set of objects, called catalyzator proteins, and Ph(0) is the protein initially associated with region labeled by h; 539 5. Emem is a finite set of variables, called enzymes, disjoint with V armem, and Emem(0) is the initial values of the enzymes; 6. V arh, h ∈H, is a finite set of variables xj,h associated with region (a membrane or the shared memory) labeled by h, its values must be natural numbers (they can also be zero), the value of xj,i at time t∈Nis denoted by xj,i(t); 7. V arh(0) is a vector that represents the initial values for variables in V arh; 8. Prh, h ∈H, is a finite set of programs associated with region labeled by h, having the following syntactical format: F(x1,h, . . . , xkF,h)e(F);α(F) −−−−−−−→ c1|v1, . . . , cnF|vnF where: •F(x1,h, . . . , xkF,h)is a computable function (the production function), being x1,h, . . . , xkF,h variables in V arh; •c1|v1, . . . , cnF|vnFis the repartition protocol associated with the program, being c1, . . . , cnFnatural numbers specifying the proportion of the current production distributed to variables v1, . . . , vnF∈V arh∪V arpar(h)∪ V arch(h)}, being par(h)the parent of hand ch(h)the set of child of h in µ; •e(F)∈Ehis an enzyme and α(F)∈Pis a protein, both of them associated with program F, if no enzyme or protein is used in a program then it will be omited; 9.Ris a finite set of rules of the following form: •Protein evolution rules:[α→α0]h, where h∈H, α ∈Pand α0∈P. •Writing-only communication rules between the shared memory and the membranes (h , Xh/Yh,mem , mem)W α where Xh∈V arh, Yh,mem ∈V armem, α ∈Pin such manner that there is, at most, one rule for each membrane h∈ {1,...p ·q}. Variables Yh,mem, Yh0,mem should be different for two membranes h, h0. •Reading-only communication rules between the shared memory and the membranes: (h , Xh/Ymem , mem)R α where Xh∈V arh, Ymem ∈V armem, α ∈P. Variable Ymem is the same for each h∈ {1,...p·q}. •Membrane creation rules: X1,h , X2,h, , . . . , Xn,h hh0;α where h, h0∈ {1,...p·q}are different, α∈Pand X1,h , . . . , Xn,h ⊆ V arh. The term region h(h∈H) is used to refer to membrane hin the case h∈ {1, . . . , p ·q}, as well as to refer to the shared memory in the case h=mem. Next, we describe the semantics of RENPSHs. A configuration of a RENPSH at any instant tis described by the current membrane structure, together with 540 proteins and all values of the variables and enzymes associated with all regions (compartments of the current membrane structure and the shared memory). The initial configuration is (µ, Emem(0),{Ph(0), V arh(0)|h∈H}), where µ={h0}. A program F(x1,h, . . . , xkF,h)e(F);α(F) −−−−−−−→ c1|v1, . . . , cnF|vnFassociated with a region is applicable to a configuration Ct, at moment t, if the value of e(F) at that instant is greater than min{x1,h(t), . . . , xkF,h(t)}and protein α(F) is inside the region hof Ct. When applying such a program, variables associated with configuration Ctare processed as follows: first, the value F(x1,h(t), . . . , xkF,h(t)) is computed as well as the value q(t) = F(x1,h(t), . . . , xkF,h(t)) c1+···+cnF This value represents the unary portion at instant tto be distributed among variables v1, . . . , vnhaccording to the repartition expression. Thus, q(t)·csis the contribution added to the current value of vs(1 ≤s≤nh), at step t+ 1. So, vs(t+ 1) = vs(t) + q(t)·csand vs(t) = 0, i.e, it is assumed that variable vs is “consumed” (become zero) when the production function is used and other variables retain their values. Each program in each membrane can only be used once in every computation step, and all the programs are executed in parallel manner. A protein evolution rule [ α→α0]his applicable to a configuration Ctat moment tif protein αis in membrane hof Ct. When applying such a rule the protein αin hevolves to protein α0in h. These rules are applied in a maximal manner. A writing-only communication rule between the shared memory and the membranes, (h , Xh/Yh,mem , mem)W α, is applicable to a configuration Ctat moment tif protein αis in membrane hof Ct. When applying such a rule the value Xh(t) is assigned to the variable Yh,mem(t+ 1) of the shared memory, that is Yh,mem(t+ 1) ←Xh(t) . These rules are applied in a maximal manner. A reading-only communication rule between the shared memory and the membranes, (h , Xh/Ymem , mem)R αis applicable to a configuration Ctat moment tif protein αis in membrane hof Ct. When applying such a rule the value Ymem(t) is assigned to the variable Xh(t+ 1) of membrane h, that is Xh(t+ 1) ←Ymem(t). These rules are applied in a maximal manner. A membrane creation rule X1,h , X2,h, , . . . , Xn,h hh0;αis applicable to a configuration Ctat moment tif protein αis in membrane h0of Ct. When applying such a rule, a new membrane labelled by his created in such manner that h0is the parent of hand the set of its variables is V arh={X1,h , . . . , Xn,h}. Given a random enzymatic numerical P system with proteins and shared memory Π, we say that configuration Ctat time tyields configuration Ct+1 in one transition step if we can pass from Ctto Ct+1 by applying in parallel each program in each membrane only once, and by applying the rules in a maximal parallel way following the previous remarks. A computation of Πis a (finite or infinite) sequence of configurations such that: (a) the first term is the initial configuration of the system; (b) for each n≥2, the n-th configuration of the 541 sequence is obtained from the previous configuration in one transition step; and (c) if the sequence is finite (called halting computation) then the last term is a halting configuration (a configuration where no rule of the system is applicable to it). All the computations start from an initial configuration and proceed as stated above; only halting computations give a result, which is encoded by the objects present in the output region iout associated with the halting configuration. If C={Ct}t<r+1 of Π(r∈N) is a halting computation, then the length of C, denoted by |C|, is r. For each i(1 ≤i≤q), we denote by Ct(i) the finite multiset of objects over Γcontained in all membranes labelled by iat configuration Ct. 4 Simulation of one iteration of the RRT algorithm The input of an algorithm generating a Rapidly-Exploring Random Tree T= (VT, ET) consists of the following parameters (xinit, K, ∆t, X, Xobs, dmin), where: –xinit is the initial state. –Kis the number of iterations to build the RRT. –∆t is a fixed amount of time for transitions. –Xis the state space. –Xobs ⊆Xis the obstacle state space. –dmin is the minimum distance threshold according to some distance metric ρin order to include a new node in the RRT. For holonomic robots in a 2D environment the state space can be given by the Cartesian coordinates (x, y) of the possible robot positions. For instance, by means of a grid with p≥1 columns and q≥1 rows. In this case, any state or position (i, j)∈ {1,...p}×{1,...q}can be encoded by the natural number (i−1) ·q+j. In such a manner that, given a natural number nencoding a state (i, j), the following holds: i= 1 + qt(n, q) and j=rm(n, q). Initially, VT={xinit}and ET=∅and for each iteration a new node and a new arc can be added to Taccording the following scheme: – A new state xrand is randomly selected by using a function RANDOM STATE(X). – The node xnear in Tclosest to xrand is selected by means of the function NEAREST NEIGHBOR(xrand,T, Threshold) in such manner that if the minimum distance is lesser or equal to T hreshold, then no node is selected in this iteration. – The unitary vector Ufrom node xnear to node xrand is computed. – The new node Xnew is obtained by applying the unitary vector Uto the robot for ∆t time starting at state xnear, that is, Xnew =xnear +U·∆t. This node will be obtained by using the function SELECT NEW NODE(xnear, U, ∆t). – The node Xnew and the arc (Xnear, Xnew) is added to the tree T. This algorithm will be simulated by a random enzymatic numerical P system with proteins and shared memory of degree (p, q) Π= (H, µ, P, Emem, Emem(0),{(Ph(0), V arh, V arh(0), Prh)|h∈H},R, h0) defined as follows: 542