A distributed approach to the control of multi-robot systems using XP colonies

Abstract

This paper proposes and demonstrates the viability of a novel approach to control multi-robot systems. This approach is based on computing with membranes (P systems) that is a branch of molecular computing inspired by the structure and function of biological cells. There are many variants to the original P system model that have been introduced and theoretically studied over the last two decades. Most of them were proved to be computationally universal. Many applications for P systems have been proposed including the recent use of numerical P systems to control a single robot. This paper makes several contributions to the area of P systems applied to robot control. First, it approaches the problem of controlling multi-robot systems containing dozens of robots with very limited capabilities. Second, it proposes the use of a symbolic approach based on XP colonies. Third, this paper presents a detailed comparison of the proposed solution to a standard one based on finite state machines, which highlights the advantages and disadvantages of the proposed solution. Finally, in addition to using physically realistic simulations, this paper demonstrates the feasibility of the proposed approach on real robots. The source code is available from an online repository, which makes all the experiments fully reproducible. Online demonstration videos illustrate all of the experiments.

Keywords

Multi-robot systems distributed control P systems XP colonies P swarm Kilobot

1. Introduction

A multi-robot system (MRS) is a group of robots where sensing, data processing, actuation and the energy supply are distributed among the robots [1]. MRSs have raised a great deal of interest in the last three decades from both theoretical and practical points of view. There are many ways to classify MRSs [2] and several dimensions can be taken into consideration [3], e.g. size, communication, processing, reconfigurability, heterogeneity, task allocation and group architecture. Of particular interest are MRSs composed of many simple, identical robots, where there is no centralized control and the sensing and communication are only local.

MRSs can accomplish complex tasks faster and more reliably than single robots. There are also tasks that cannot be solved or are unreachable for single robots. Applications for MRSs include: disaster management, playing team games, exploration of unknown environments [4], demining, object transportation, security, surveillance and recognition.

The problem of how MRSs can be designed is still an open question of paramount importance [5, 6]. Centralized control relies on a single central entity that receives and processes all the information about all the robots. This approach can prove to be computationally infeasible and impossible to implement in the case of large MRSs. On the contrary for decentralized or distributed control, a central entity is not present, while the global behaviour emerges from simple local control rules. Stigmergy is often used as an indirect communication mechanism through a shared environment [7]. How to go from high-level specifications for the MRS, as a whole, to local interaction rules for individual robots can prove to be a difficult problem to solve. Often, this is achieved through a slow and tedious trial-and-error process. Also, the distributed approach can be challenging due to dependencies between robots and the collaborative nature of the given tasks [8]. Further topics of interest include morphological and accidental heterogeneity and their effects, as well as sensor fusion in MRSs.

In this context, there are many tasks in which distributed MRSs were shown to perform better than any form of centralized control. These tasks include localization of multiple sources, following trails, aggregation, dispersion, flocking, foraging, object clustering and sorting, navigation, path formation, deployment, multi-target observation [9], collaborative manipulation (e.g. stick pulling) and transportation, cooperative coverage and task allocation.

While there are many approaches for controlling collective robotic systems (for a comprehensive review, see [1]), efficient MRS designs can be inspired by collective behaviours that can be seen in nature and that were not specifically designed, but emerged as a result of simple local interaction mechanisms. As a result, bio-inspired MRSs, like their natural counterparts, show capabilities that are greater than the sum of the capabilities of the individual robots in the system.

In this paper, the key component of the proposed approach to control the MRSs are P systems. In the context of bio-inspired computation, P systems (PSs) have attracted a large interest since their introduction in 2000. PSs are bio-inspired, distributed and parallel computing models [10], which take their inspiration from the membrane structure of a biological cell. Many variants to the original PS model have been proposed and their mathematical properties, in terms of computing power, have been analysed extensively. It has been shown that most of the PS variants are computationally universal and that they can solve NP-complete problems in less than exponential time [11]. P systems have a wide-ranging array of applications in areas as diverse as, for example, biology, computer graphics, approximate optimization and economics [12].

Recently, numerical PSs have been used to design controllers for single mobile robots [15]. These controllers are called membrane controllers in the literature. An extension of numerical PSs was introduced in [16] and enabled the development of new robot control applications, such as trajectory-tracking control of wheeled mobile robots, which is a nonlinear problem with non-holonomic constraints [17]. The problem with multi-objective mobile robot path planning in dynamic environments has been approached using membrane computing and particle swarm optimization in [18]. The use of PCol automata for rudimentary robot control has been investigated in [19, 20]. However, these recent developments refer only to experiments conducted on single robots and only in simulation.

Three basic questions arise from the developments: (1) is it possible to control MRSs with PSs; (2) how does the performances of this approach compare to traditional methods for controlling MRSs; and (3) is it feasible to control real robots with this approach?

To address these three questions, this paper proposes a bottom-up approach to generate collective behaviours in an MRS by using XP colonies (a variant of PSs). This idea builds upon the structural and functional similarities between MRSs and XP colonies. Additionally, the parallel and distributed nature of these computing models make them ideal candidates for efficient implementations on parallel hardware. Starting from these conceptual considerations, this paper makes several contributions. First, MRSs with a dozen robots are considered. Secondly, it is shown that a symbolic approach based on XP colonies can be successful in controlling MRSs. Furthermore, this paper presents a critical analysis of the advantages and disadvantages of the proposed approach and compares it to a standard control strategy. Lastly, this paper demonstrates that it is possible to control real robots using symbolic approaches based on XP colonies.

The experiments presented in this paper are fully reproducible both in simulation and with real Kilobot robots, because the following are open access: the cross-platform XP colonies simulator (Lulu) [21], the XP colony robot controller [22] and the FSM controller [23] used for comparing control strategies. Demonstration videos, which showcase the effectiveness of the original design both in simulation and with real robots, are available from [24]. This reference also contains the numerical data and the associated R script used to process the information and to show relevant (graphical) information.

The next section gives further details on MRSs, collective behaviours and decentralized control strategies. The functioning of a P/XP colony is explained in detail and the simulators and the real robots are briefly described. The third part includes the segregation experiment description and a presentation of the proposed controller using XP colonies. The fourth part is dedicated to discussions, including performance evaluations using both simulated and real robots and to comparing the proposed model with a Finite State Machine model. The paper ends with conclusions and directions for further work.

2. Preliminaries

2.1 Collective behaviours in MRSs

Topics of high interest in MRSs now include the issue of communication, how to design and develop control architectures, task allocation, control, motion coordination [25], cooperative navigation [26], localization [27], mapping, exploration, multi-robot learning, human-MRS interfaces [28], socially-aware MRSs, role-switching [29], distributed consensus with visual perception [30], target tracking [31], heterogeneity and pattern formation.

Pattern formation is an interesting and challenging aspect in the study of MRSs. There are eight challenges in pattern formation identified in the literature [32]: establishment, maintenance, obstacle avoidance, collision avoidance, transformation of patterns, role assignment, scalability and coordinating multiple patterns. Bio-inspired techniques for pattern formation are reviewed in [33].

Foraging is a fundamental behaviour that appears in natural systems and represents the collective search for food sources and the transportation of food back to nests. Foraging is extensively studied in the context of MRSs, where foraging robots must be able to find key areas and objects and transport the objects back to predefined collection points. The dispersion of robots is a key factor in assuring an efficient foraging behaviour and indicates how the robots efficiently deploy themselves and cover the environment.

Aggregation, in a sense, is the opposite of dispersion and in this case, the robots are required to meet at a location [34]. In [35], it is argued that “aggregation is of particular interest since it stands as a prerequisite for other forms of cooperation”. In the context of MRSs, segregation means the separation of the robots into groups based on certain criteria and maintaining this division into groups simultaneously with safe navigation, as well as avoiding obstacles and collisions with other robots or groups. Segregative behaviours are often displayed by natural collective systems and have been investigated by many researchers. In [36], a method to achieve segregative behaviours is proposed based on hierarchical abstractions, flocking behaviours and collision avoidance. In [37], a differential artificial potential method is used to achieve segregation in a swarm of heterogeneous robots, while in [38], segregation is achieved based on the Brazil nut effect.

Robotic swarms are MRSs composed of a large number of robots with very limited capabilities, such as the Kilobot robot. Collective decision-making in a swarm of 100 Kilobots has been investigated in [39]. A collective algorithm for shape formation is demonstrated for a 1000-Kilobot swarm in [40]. Other swarm behaviours, such as foraging, formation control, phototaxis and synchronization, have been tested on Kilobot swarms in [41]. Buzz is a programming language designed to express collective (swarm) behaviours [42].

Figure 1.

A membrane structure for a standard P system.

2.2 P systems

2.2.1 The standard P system

The standard P system is a collection of regions that are surrounded by membranes that act as a border between regions. An example P system is presented in Fig. 1. The system is composed of five membranes, where the peripheral membrane M1 is known as the skin membrane. Each membrane can contain, within its region, zero or more child membranes. In this case, M2 and M5 are the child membranes for M1. Membranes that do not contain any other membranes are known as elementary membranes, which, in this case, are M3, M4 and M5. The hierarchical structure of a P system is important because membranes exchange information only between parent and child membranes.

In each compartment, there are multisets of objects and evolution rules that define how these multisets evolve with each time step. For a simple example of a standard P system, the reader is referred to [10].

Figure 2.

Graphical representation of the simulation steps for the addition of a P colony. The program executed for the current configuration is marked in bold, while the changes that it produces are also presented in bold in the next simulation step. The simulation is 2 steps long (a and b) because, in the third step (c), there are no $l_{+}$ objects in the environment to trigger the addition, so the program’s execution halts.

2.2.2 P and XP colonies

P colonies have been introduced in [43] as formal computing models based on single membrane agents that have objects, rules and programs (sets of rules). In this context, an object is an item that is defined in the P colony alphabet and is used to build multisets that describe the state of each agent and of the P colony. A multiset stores the multiplicity of each of the contained objects and is usually described using subscript numbers to denote the multiplicity, such as a ${}_{2}$ b ${}_{3}$ [44]. The shared environment surrounds the agents and contains an infinite number of basic objects $e$ and a finite number of final objects $f$ .

Formally, a P colony with capacity $m$ is a construct:

$\displaystyle\Pi=(A,e,f,B_{1},\ldots,B_{n})$ (1)

where $A$ is an alphabet (a set of objects), $e\in A$ is the basic object of the colony, $f\in A$ is the final object of the colony and $B_{i}(i=\overline{1,n})$ are the agents. Each $B_{i}$ is of the form $(O_{i},P_{i})$ , where $O_{i}$ is a multiset of $m$ copies of the basic object $e$ (the initial state of the agent) and $P_{i}=\{p_{i,1},p_{i,2},\ldots,p_{i,k_{i}}\}$ is a finite set of programs. Each program $p_{i,j}$ consists of $m$ rules. Usually, there are two types of rules: evolution rules of the form $a\to b$ (rewriting object $a$ into object $b$ ) and communication rules of the form $c\leftrightarrow d$ (object $c$ from the agent will move into the environment and object $d$ from the environment will move into the agent). A checking program is where the agent can check for the presence of a given object $d$ in the environment and it has the following form: $<$ $a\to b;c\leftrightarrow d/c^{\prime}\leftrightarrow d^{\prime}$ $>$ . This type of program can be compared to a conditional branch because it can be executed in two ways. If objects $a$ and $c$ are present in the agent and object $d$ is in the environment, the evolution rule $a\to b$ and the communication rule $c\leftrightarrow d$ are applied. Otherwise, if object $d$ is not in the environment, but object $d^{\prime}$ is present, the communication rule $c^{\prime}\leftrightarrow d^{\prime}$ will be applied instead of $c\leftrightarrow d$ . If neither $d$ nor $d^{\prime}$ are present in the environment, the entire program is considered non-executable. Note that $c$ and $c^{\prime}$ can coincide.

A simple P colony with one agent and two programs (each having one evolution rule and one communication rule) is introduced in [45] and has the following formal definition:

$\displaystyle\Pi_{1}=(\{l_{+}\},e,f,\,(\{e,e\},<e\to f;e\leftrightarrow l_{+}>,$ $\displaystyle\quad∼{}<l_{+}\to e;f\leftrightarrow e>))$ (2)

Figure 3.

Lulu_Kilobot control loop.

The execution process can be visualized in Fig. 2 in a step-by-step manner. Initially, there is one object $f$ and one object $l_{+}$ in the environment (Fig. 2a). There are two objects $e$ inside the agent initially. Only the first program can be executed, which results in the transformation of $e$ into $f$ and the exchange of the other internal $e$ with the external $l_{+}$ (Fig. 2b). In the next step, only the second program can be executed: $l_{+}$ will be transformed into an $e$ and the internal $f$ will be exchanged with an external $e$ . There will be two objects $f$ in the environment and no $l_{+}$ , while the agent will return to its initial configuration with two objects $e$ inside (Fig. 2c). Consequently, neither of the two programs can be applied anymore and the computation halts due to a lack of executable programs. This P colony can be considered as an incremental P colony.

In the context of P colonies, a computation is a sequence of steps. When it is possible to apply more programs in a given step, the actual program to be executed is selected non-deterministically. It was also demonstrated that P colonies can compute whatever is algorithmically computable [43].

XP colonies were introduced in [46] as extensions of the classical P colonies allowing multiple colonies to interact with each other via a shared global environment. Note the similarity with a multi-robot system, where robots can also interact with each other via a shared environment. To achieve this, an XP colony includes exteroceptive rules of the form $c\Leftrightarrow d$ , where an object $c$ first appears inside the agent and then moves into the global environment (shared by multiple XP colonies). Another object $d$ will first appear in the global environment and then moves into the agent. To a checking program, an exteroceptive checking program has the following form $c\Leftrightarrow d/c^{\prime}\Leftrightarrow d^{\prime}$ . This program allows an object $c^{\prime}$ from the agent to be exchanged with object $d^{\prime}$ from the global environment if object $c$ is not present in the agent or if object $d$ is not present in the global environment.

P swarms are colonies of either independent P colonies or interacting XP colonies as formally introduced in [46]. A P swarm has a number of member P/XP colonies that share a global environment (in the same sense, a P colony has a number of agents that share a local environment). The P colonies that compose a P swarm can run independently of one another or, on the contrary, they can interact and even synchronize themselves to produce more complex behaviours. In the latter case, the interactions between XP colonies is realized through the use of exteroceptive rules [46].

Figure 4.

Kilobot controller structure modelled as an XP colony. Dashed lines are used for connections that require background processing.

2.3 Lulu and Kilobot

Lulu is a software simulator for P/XP colonies and P swarms that was developed in Python and is distributed under an open-source license. Lulu is composed of a single Python script that abstracts all of the theoretical components of an XP colony and of a P swarm into classes that allow the parsing, instantiation and simulation of this bioinspired computing model [46]. Since the version presented in [46], the simulator has been optimized and adapted for execution on a micro-controller (and a desktop computer) as a compiled application written in C.

The P/XP colony definition is read from a text file written in a language that closely resembles the one used for the theoretical definition. After parsing the input file and the instantiation of the required classes, the simulation process can begin.

Lulu was designed as a library with the main goal of allowing an external application to flexibly control the simulation process and optionally insert or remove information from the agent or environment multisets [46]. This design consideration has been maintained for the C implementation, where additional improvements were made in terms of memory usage. This enabled the full-segregation Kilobot controller to use only 45% and 50% of the 32 Kb Program and 2 Kb RAM memories respectively (see the experiments reported in this paper).

Kilobot is a simple robot with basic characteristics that make it an ideal candidate for swarm robotics experiments. Unlike ordinary robots, which have standard DC motors for locomotion, this robot has two vibration motors, which enable a differential drive. This robot can send and receive messages using an infrared communication system that points downward, which can also measure the distance to neighbouring robots. No obstacle detection and avoidance is possible. An ambient light sensor is also available. An RGB LED allows the display of up to 64 colours. Additional technical details for the Kilobot can be found in [47].

2.4 Lulu_Kilobot – a P/XP colony based controller

Lulu_Kilobot is the application that is executed on real and Kilombo-simulated Kilobot robots. Each robot is controlled locally by an individual P/XP colony. During the preparation phase, the P/XP colony read from a text input file, converted into C code and compiled into two standalone applications: a desktop simulation and a firmware image for the Kilobot.

The controller application consists of the main robot control loop presented in Fig. 3, where the conversion of numeric values to and from symbolic values precede and succeed the P colony execution process.

At each control step, numeric sensor input values are thresholded into two or more discrete values (such as ambient light low/high) and inserted into the multiset of the corresponding agent. It must be noted that the robots are controlled in a distributed manner and do not have access to any information other than that obtained from the sensors.

After the P colony agents have received new sensor input, the P colony simulator executes a new simulation step, where each agent’s executable programs are used.

Once the P colony execution step ends, the new configuration is processed by the controller to determine which newly generated command symbols are present in the agents. If a new symbol is found, it is converted into a Kilobot command.

These two pre/post-processing steps are required to interface the P colony to a robot and together, they have the role of a Hardware Abstraction Layer.

Table 1
Short description of the basic objects used for symbolic conversion of the input data [48]

Object	Creating agent	Meaning
d_all	Command	Requests the minimum distance from current neighbours
S_all	Msg_distance	There is at least one neighbour robot that is at a Small distance from the robot executing the P colony
B_all	Msg_distance	All neighbour robots are at a Big distance from the robot executing the P colony
T_Start/T_Stop	Command	Start/stop the internal timer
T_I	Timer	A timer interrupt has occurred (at a predefined rate)
c_R/c_G/c_B/c_W	Command	Colour the robot’s RGB LED in red/green/blue/white
m_0/m_S/m_L/m_R	Command	Send the motion command to stop/move_{straight/left/right}
END	Any	Finalize a message that is stored in the OUT P swarm environment and allows the backend to send the
		message (about the contents of the OUT P swarm environment) to other robots.

2.5 Modelling kilobot with an XP colony

It is common for robot controllers to have a modular architecture, which groups together input and output modules and has one or more decision modules [19]. This approach improves the clarity of the model and in the case of P colonies, one module can be directly associated with a P colony agent. Six modules (agents) are used to represent all the sensing and actuation components present on the Kilobot robot. This is shown in Fig. 4.

After analysing the structure presented above, one can see that it closely matches the capabilities of a real Kilobot. As all modules are represented by agents in the P colony, the only means of inter-agent communication is by exchanging objects with the P colony environment. This method of communication, as opposed to a peer-to-peer exchange method, imposes the requirement that objects must be uniquely defined (by only one module) so that the receiver of the message can correctly determine the sender and process the data.

To include a P colony model within the control loop of a robot, the former must receive and send input and output values respectively. In the case of numerical models, such as (but not limited to) numerical P systems, this task is simply a matter of assigning one important sensor/effector value to one P system object [17]. In the context of P colonies, their symbolic nature imposes certain transformations between numeric and symbolic values at the interfaces between the P colony model and the rest of the robot control software. This is discussed in Section 2.4. For clarity, a special control alphabet (of symbolic objects) has been created to model the required input/output devices found on the Kilobot including the infrared communication mechanism. This alphabet is discussed in detail in [48] and a section of it, which includes all of the symbolic objects used in this paper, is presented in Table 1.

From an effector’s point of view, the Kilobot has limited movement precision because it uses vibrating legs for locomotion instead of wheels. For this reason, the movement directions are limited (by means of calibration values) to four possible directions mapped with symbolic objects that can be interpreted by the motion agent: left (m_L), right (m_R), straight (m_S) and stop (m_0). The secondary effector available to the robot is an RGB LED that can represent various colours by combining the basic three colours (red, green, blue). These basic colours are represented by objects associated with the led_rgb agent: red (c_R), green (c_G), blue (c_B), white (c_W) and so on.

The output module of the controller is less difficult to model because of the nature of the robot’s effectors, which impose the use of discrete values that are easily representable using symbolic objects. On the other hand, the input modules, which perceive the environment, cannot be directly transformed into a symbolic form due to their continuous nature. A second issue that had to be addressed was how to limit the dataflow that sensors usually offer and how to extract meaningful information without flooding the environment with objects faster than they can be processed.

The solution to the data discretization issue was inspired by the majority of the algorithms [39, 41] that use the Kilobot robot, where the only relevant information offered by the neighbour-distance sensor is the distance from each robot and the variation (increase, decrease and constant) of the distance from each robot. The same two types of information are required from the ambient light sensor.

In regards the second issue, the solution was the use of a request-response model, where the command agent should request a certain type of information from one of the input agents and, upon processing the input, reply by publishing in the environment the requested information in the form of a special object. The significance of each symbolic object is presented in Table 1.

The two-way conversion between numerical values and symbolic objects is done continually throughout the execution of the P colony controller. In Fig. 4, the dashed lines that connect the agents to the controller input and output denote the background processing needed to convert symbolic objects to and from numeric values, where the latter are used by the robot control functions provided by the Kilobot API.

As MRSs generally require a form of inter-robot communication, which has been included in the model by using two multisets: IN and OUT P swarm environments. Because of the need for inter-robot communication, the XP colony was chosen to model the Kilobot. These IN/OUT multisets are external to the XP colony and can be accessed in the same manner as the P swarm environment, which uses corresponding IN/OUT exteroceptive rules. This separation was necessary because each environment models an input/output buffer, which is similar in concept to the TAPE First In First Out device that is part of the Turing Machine. More details regarding this topic and other implementation details can be found in [48].

3. Case study

After considering the theoretical and conceptual aspects of modelling a robot using XP colonies, the following robot experiment is presented to highlight different quantitative aspects of the control model, such as the total time required to reach a final state and the energy consumption.

The case study is a classical multi-robot experiment and allows one to evaluate the performance of the controller using the comparative results presented in Section 4.

Figure 5.

The most important XP colony programs that were used to implement the segregation experiment were: a) when receiving signals from a single type of leader; and b) when multiple types of messages are received in a short amount of time (between two simulation steps).

3.1 Segregation in multi-robot systems

The experiment presented in this section was selected because of its higher complexity in terms of control logic and the fact that it requires inter-robot communication. This multi-robot task has been extensively considered in the literature and uses the leader-follower pattern. In [49], the authors considered three types of leader robots (coloured red, green and blue) that are stationary and emit a unique message. The follower robots receive messages from a leader robot and colour themselves using the colour of that leader. Afterwards, they start emitting messages of the “same colour” to attract other followers. If a follower robot receives messages from two or more different leaders, then it will move randomly until it receives messages from only one leader.

Messages that are received over infrared represent the input source available to the controller, while the output is composed of sent messages, LED colour and occasionally, movement. The message exchange process was modelled using the previously presented P swarm concept by considering that XP colonies are connected by means of one or more multisets that are used for data exchange. Because of the locality of the infrared communication device available on the Kilobot, the link between the XP colonies is formed using the IN/OUT P swarm environments (see Section 2.5). The backend part of the controller ensures that objects present in the OUT environment are sent once a message ending object END is added to the multiset. Similarly, once a message is received by the robot, it is processed and all identified objects are inserted into the IN environment.

The control logic relies on the use of symbolic objects to retain the current state of the robot (red, green or blue) and to temporarily store the latest received signal. If these two objects coincide or if an object was not received, then the XP colony will maintain its current state and colour the robot accordingly. Otherwise, a random movement is prepared and executed, which returns the robot to its initial neutral state. A sample of the Lulu implementation for both cases is presented in Fig. 5.

The random movement has a 50% probability of going forward and a 25% chance of going left or right. These proportions have been chosen empirically. Each random direction is represented as a P colony program and all four programs (two forward, one left and one right) have the same execution requirements, such that the P/XP colony simulator is required to randomly choose one of the four executable programs.

The leaders were pre-programmed to constantly emit the same message and maintain the same LED colour.

In quantitative terms, the XP colony used for this experiment had a capacity of three and the decision part of the command agent consisted of three and five simulation steps when single and multiple messages were received respectively.

4. Discussions

In this work, two pairs of control models and execution environments were considered to assess the feasibility of using XP colonies to control multiple robots. An XP colony-based controller was assigned to each robot and was interfaced with various devices found on the robot.

Another widely used control model, the Finite State Machine, will be presented in the beginning of this section and afterwards, compared with the proposed XP colony model for each of the experiments.

A Finite State Machine (FSM) is composed of a finite number of states, transitions between states and actions [50]. To interact with the environment, which is often a requirement for embedded systems, the machine must respond to several external or internal triggers known as events. These events can trigger a state transition if certain criteria are met and actions can be executed either when entering, leaving or while in a state. For these reasons, the model is depicted as an Event-driven Finite State Machine [50].

Using this type of control model, sensor input can be mapped to events and end-effectors can be controlled using actions. Among the different software methods for implementing an FSM, such as a simple chain of conditional instructions (if-else or switch-case) or a table of handler functions indexed by events, the latter has the advantage of simplicity and maintainability [50].

Layers in a subsumption architecture [51] are made up by processors (or modules) that are augmented (with some instance variables) finite-state machines (AFSM). Inhibition and suppression signals are used for communication between AFSMs.

4.1 Execution environments

At the end of each simulation and experiment on real robots, the data was exported as CSV files and was processed using the statistical language R [52]. Details regarding the data acquisition process for each environment are presented in the following subsections.

4.1.1 Physically realistic simulations

The following experiments were executed using Kilombo, a robot simulator that supports the Kilobot robot and allows for the same C source code to be used for both simulation and the real robot [53]. The use of this simulation environment allowed not only for faster testing, but it also allowed for easier and noise-free data collection. The cost of the “reality-gap” is justified by the accurate recording of robot states.

The following experimental results were obtained from simulation by measuring various performance indicators of an XP colony controller and comparing them to results obtained when using an alternative control model. The data acquisition process relied on precise internal recordings (at 0.04 second intervals) from several robot-specific parameters. Details regarding the chosen parameters, as well as the processing methods, are provided individually for each parameter.

The aim of this execution environment is to observe the evolution of the controller under perfect conditions, which is accomplished by emphasizing the (internal) performance of the controller that can receive perfect input. The infrared communication device/distance sensors used in the experiments were modelled with a 360 ${}^{\circ}$ view angle and always returned the exact distance between the sensor and the closest Kilobot.

It must be noted that, although this simulator does not feature a physics engine, it does simulate basic physical interactions between robots and adds noise-to-distance estimations, as well as message transmission success rates. It must also be noted that the previous aspect of perfect input actually refers to the normal distribution of the noise occurrence rate. For the simulations presented in this paper, the message success rate was set to 20%.

One side effect of this type of simulation is that all robots move the same distance for a given output value without considering engine calibration differences that are always present in real Kilobots. This fact can be safely omitted because no aggregate metrics are used in these experiments. Instead, they use only individual robot measurements that do not depend on relative positions.

The framework for the FSM controller is the same one that was used for the P colony controller, but it was adapted for controlling robots using a version of the Event-driven FSM presented in [50] and it was interfaced with the Kilobot framework.

4.1.2 Experiments on real robots

Due to the limited computing frequency (8 Mhz) and memory capacity (32 Kb) of a Kilobot robot, real robot trials were performed to establish whether the proposed XP colony controller can function properly under these restrictions. Apart from these limitations, real Kilobots also exhibit varying input/output device data due to differences in calibration parameters.

The previously presented constraints indicate that the robot control application must be flexible enough to handle both the computational restrictions, as well as the functional differences between the robots.

Each real robot has an AprilTag [54] attached for the purposes of identification and position/rotation tracking. Using a video recording of each experiment, the previously mentioned information was extracted using the open-source AprilTag software and then stored as CSV files in the same format as the simulation data. Any errors that could appear during this acquisition stage were filtered out during the processing stage, which is detailed in the following section.

4.2 Results on segregation

The segregation experiment has been performed in sets of 10 tests for each type of controller/platform using 16 real/simulated Kilobots. Each test was considered finished when all robots reached a stable state (colour) and did not move for at least 3 seconds.

The robots were arranged identically for all trial runs. They were placed in a circular shape with three leader robots forming a triangle in the centre of the follower circle as seen in Fig. 6. This circular layout was preferred for multiple reasons: (a) the leader group is placed at an approximately equal distance to the follower group; (b) most robots will initially receive at least two different colour signals; and (c) there is a limited time span for the follower robots to receive signals from the leader group, which requires the follower robots to reach a consensus.

Figure 6.

Layout of the Kilobots for the segregation experiments at initial and final positions, for real robots (a) and Kilombo simulations (b).

During each trial run, the position, rotation and ID of each robot (real and simulated) was recorded at a rate of 24 recordings per second. These three variables, along with the current number of seconds, represents the input values.

The output variables were obtained after processing (in R) the execution time and energy consumption. The execution time is the last time measurement taken during execution, while the energy consumption was estimated based on the robot’s movements. Using the position and orientation input variables, two intermediate variables were obtained, namely deltaPos and deltaTeta. These refer to the linear distance and the variation in robot orientation between two measurements. The energy consumption was estimated using the following formula:

$\displaystyle\textit{consumption}_{i}=\begin{cases}{\frac{\textit{deltaPos}_{i% }}{2},|{\textit{deltaTeta}_{i}}|>0.1}\\ {\textit{deltaPos}_{i},|{\textit{deltaTeta}_{i}}|\leqslant 0.1}\\ \end{cases}$ (3)

where $i$ is the current row in the data table and 0.1 is an empirically determined value. Variations in robot orientation that were smaller than the latter value were considered negligible and the robot’s movement was considered straight. In this case, it is safe to assume that the linear distance between the current and previous measurements was a good estimate for the energy consumption because both vibrating motors are used. In the case of a turn, only one of the motors is used and only half of the distance was considered for the energy consumption estimation.

During the data processing phase, a small noise was noticed in the position input variable of some real robots. More precisely, stationary robots had small position variations that could amount to a larger variation for moving robots. To correct this issue, the maximum recorded deltaPos value for stationery robots was subtracted from all deltaPos values. Any resulting negative values were considered to be 0.

Figure 7.

Colour segregation Finite State Machine. Each event is coloured according to the received colour.

Table 2

Common statistical observations regarding the total experiment duration for each controller type (XP colony/FSM) and execution method (real robot/simulation) for ten experiments

	Standard deviance	Minimum	1 ${}^{\rm st}$ quaternion	Median	Mean	3 ${}^{\rm rd}$ quaternion	Maximum
XP colony real	30.16	15.79	33.44	51.90	55.29	71.77	120.62
FSM real	58.76	62.79	81.03	89.40	121.24	159.60	242.21
XP colony sim.	23.96	48.58	74.18	90.42	88.34	102.25	132.79
FSM sim.	15.85	383.30	385.90	388.00	392.70	388.90	436.70
XP colony 50 robot sim.	49.02	133.90	139.40	189.10	187.90	230.00	262.80
FSM 50 robot sim.	75.68	230.50	278.40	329.40	329.60	360.20	458.80

The XP colony controller is compared, in terms of experiment duration and energy consumption, to the FSM controller presented in Fig. 7. The FSM controller was implemented using the same libraries as the XP colony controller to facilitate a comparison for both real Kilobot robots and the Kilombo simulator.

4.2.1 Comparison between real and simulated executions

Both the real and simulated experiments provided the same output data using the same metrics, which made a direct comparison between the two execution environments possible. These different execution methods will be compared using results obtained for each of the two controllers (XP colony and FSM). The total experiment time was considered as a comparison criterion because significant differences between the two execution environments have been observed for this variable.

The mean execution time for all ten experiments was greater for the simulations than for the real robots. This is seen in Fig. 8 and can be attributed to two causes. First, all robots move an equal distance at each time step of the simulation. Similarly, all rotations are performed with the same speed and precision. These two characteristics are only possible in simulation due to the imprecise vibrating movement of the Kilobots and to the unavoidable calibration differences. Second, although most robot parameters are adjustable in Kilombo (including error levels), the communication range for each robot was static and equal to that for all robots. This contributed to the longer average experiment duration because robots must move further away to reach a consensus, while the real robots exhibited occasional communication range fluctuations that speed up the segregation algorithm. Also, the fast response (during the same execution step) of the FSM controller meant that robots moved more often, but over shorter distances than those controlled using an XP colony. It was noticed that, especially in simulation where the communication range was constant, the FSM controlled robots did not disperse efficiently after receiving multiple colour signals. This was because the short movement distance also meant a short turning radius. As a result, the robots maintained their initial circular formation, which lengthened the time interval required to segregate.

Figure 8.

Mean execution times for each execution environment grouped by the controller type.

Figure 9.

Scaled execution times for each controller type and execution environment for ten experiments. The smoothest lines are those that correspond to simulations.

As previously discussed in Section 4.1, the simulations allowed for error-free data collection from the robot system evolution. On the other hand, it was noticed that there was a smaller variation for each experiment’s duration in the simulations compared to the real trials. These differences in variation can be observed using the corresponding values of the standard deviation of the overall experiment duration, which is presented in Table 2. These differences can also be viewed graphically in Fig. 9, where the experiment times have been scaled by dividing each value by the root-mean-square [55] of the entire set of values for that execution/controller type.

Table 3

Common statistical observations regarding the energy consumption for each controller type (XP colony/FSM) and execution method (real robot/ simulation) for ten experiments

	Standard deviance	1 ${}^{\rm st}$ quaternion	Median	Mean	3 ${}^{\rm rd}$ quaternion	Maximum
XP colony real	11.29	0.00	1.18	5.90	6.48	78.79
FSM real	6.06	0.66	3.29	5.39	7.97	31.32
XP colony sim.	25.15	11.46	25.99	31.20	44.38	99.41
FSM sim.	3.63	12.42	15.73	14.48	16.03	19.35
XP colony 50 robot sim.	32.08	0.00	0.00	19.07	27.91	161.98
FSM 50 robot sim.	11.28	0.00	0.00	9.56	19.50	36.94

4.2.2 Comparison between XP colony and FSM controllers

Another variable that can be used to evaluate the two different controller models is the energy consumption that was estimated using Eq. (3). In the following comparison, the best implementation is one that achieves the lowest mean energy consumption over all ten trials.

The movement period of each robot and the corresponding energy consumption is determined by the time interval required to receive new colour signals and to process them to stop the robot if the current robot colour and the received colour coincide. The time interval is influenced by the physical communication rate and by the number of control steps required for processing.

Figure 10.

Mean energy consumption for each controller type grouped by execution environment.

Although the original communication rate of the Kilobot was specified at 1200 bytes/second under congestion [47], the current firmware achieved a rate of only 36 bytes/second, which corresponds to 3 messages per second. This rate proved sufficient for most types of experiments and, in Kilombo, this rate was set at 2 messages per second. From this point of view, both the XP colony and the FSM controllers were limited by the communication rate. At a minimum, there will be at least a 0.5 second movement before a new message is received.

On the other hand, the controller simplicity is entirely dependent on the control paradigm. For the FSM implementation, only one execution step is required for the reception of a signal, triggering of an event and the handling of that event. For the XP colony controller, a total of four execution steps are required to receive, process and to stop the robot. Out of these, the first three take place within the command agent and include the check for new signals, the generation of a stop command and then sending it into the XP colony environment. A fourth simulation step is required for the motion agent to receive the stop command.

Figure 11.

Boxplot comparison of the total energy consumption (a) and total experiment duration (b) between the control models at different population sizes.

From the perspective of controller simplicity, the FSM is superior, but when comparing the energy efficiency, this proves to be an advantage only for simulations, as seen in Fig. 10. Numeric data regarding the energy consumption is presented in Table 3. The fixed communication range represents the main reason why the difference in consumption is more pronounced for the Kilombo simulation than for the real robots. In the real robot experiments, it was noticed that the communication range varied greatly from robot to robot and that this contributed to a faster consensus. During the simulations, the static communication range, combined with the increased complexity of the XP colony controller, resulted in robots moving for longer distances and frequently spreading over a wider area compared to the FSM’s execution.

4.2.3 Performance comparison under increased robot population

Scalability in the context of multi-robot systems [56] can be viewed as the ability to maintain (and possibly increase) a certain level of performance as more robots join the system. This is often an issue for centralized multi-robot systems due to communication delays and is generally avoided by distributed architectures.

The XP colony design that has been presented in this paper was tested on 16 real and simulated Kilobot robots and a comparison with FSM controllers has been performed. In order to better study the effect of a larger population on the proposed model, the segregation experiment was redone in simulation using a population of 50 robots. These experiments are included in the supplementary material available online. The data was gathered after ten trials, in the same manner as for the previous comparisons and used the same comparison criteria: (i) energy consumption and (ii) execution time.

In terms of total energy consumption, the previously observed higher values for the XP Colony controller were also observed for the 50 robot system, as seen in Fig. 11a. The only difference in this case was the increase in variance for both control models.

The correlation between the small and large population experiment outcomes can also be seen for the total experiment duration (Fig. 11b). In this case, the XP Colony maintains a lower execution time even with the increase in population size. As was the case for the previous criteria, an increase in variance is also noticeable with an increased population. In both cases, the increased variance can be explained by the increased number of connections between robots and the corresponding increase of the time interval required to reach global consensus.

5. Conclusions and further work

In this paper, XP colonies have been designed to control cooperating robots that are part of a multi-robot system.

The performance of the proposed symbolic controller was evaluated using two numeric values: the total experiment time until all robots found a stable state (colour) and the energy consumption required to reach that state. These two metrics were used to compare the evolution of the XP colony controller against a structurally simpler Finite State Machine controller. The tests were carried out on real and simulated Kilobot robots and precise identification and position information was extracted from both execution environments.

Data was gathered from a total of 40 trials (ten for each controller/platform) and processed using statistical methods. The results showed that the XP colony controller achieved a lower average experiment duration in simulation and for real robots. Despite its higher code complexity, the mean energy consumption for real robots using the XP colony controller was only slightly higher than that of the FSM controller. The fact that this difference was much larger in the simulations contribute to the conclusion that real communication delays and the imperfect calibration of perception devices, across a multi-robot system, can compensate for the greater number of execution steps required by the proposed model compared to the FSM. These observations were shown to hold as the robot population increased. On the other hand, the higher abstraction level and the tree structure of P colonies pave the way for more complex algorithms that are described using simple symbolic rules. Also, the perspective on parallel execution is clear because of the membrane structure and because of the functioning principles of the P/XP colony. Together, these two characteristics may help the developer in designing a controller, where multiple agents simultaneously exchange data through a common data channel, the P colony environment or the P swarm environment. A careful design of the interactions between agents can prevent many of the human errors that appear due to poor synchronization of threads or processes.

As for further developments, there is the idea of developing a layered controller that is composed of a high-level symbolic controller written using P colonies, which is placed on top of a numerical controller written using numerical P systems. Such a system could be used for the control of a humanoid robot, where the numerical component would extract features from the environment and the symbolic one would reason based on the current observations.

Footnotes

Acknowledgments

This work was supported by a grant from the Ministry of National Education: CNCS-UEFISCDI, project number PN-II-ID-PCE-2012-4-0239, Bioinspired techniques for robotic swarms security (Contract #2/30.08.2013). The authors would like to thank the reviewers for their constructive suggestions.

References

Kernbach

. Handbook of collective robotics: Fundamentals and challenges. Pan Stanford Publishing 2013.

Dudek

Jenkin

Milios

Wilkes

. A taxonomy for multi-agent robotics. Auton Robots 1996; 3. doi: 10.1007/BF00240651.

Cao

Fukunaga

Kahng

. Cooperative mobile robotics: Antecedents and directions. Auton Robots 1997; 4: 7-27. doi: 10.1023/A:1008855018923.

Wang

Liu

. Unknown environment exploration of multi-robot system with the FORDPSO. Swarm Evol Comput 2016; 26: 157-174. doi: 10.1016/j.swevo.2015.09.004.

Prokopenko

. Advances in applied self-organizing systems. Springer London 2013. doi: 10.1007/978-1-4471-5113-5.

Bouffanais

. Design and control of swarm dynamics. Singapore: Springer Singapore 2016. doi: 10.1007/978-981-287-751-2.

Heylighen

. Stigmergy as a universal coordination mechanism I: Definition and components. Cogn Syst Res 2016; 38: 4-13.

Tumova

Dimarogonas

. Multi-agent planning under local LTL specifications and event-based synchronization. Automatica 2016; 70: 239-248. doi: 10.1016/j.automatica.2016.04.006.

Parker

. Cooperative robotics for multi-target observation. Intell Autom Soft Comput 1999; 5: 5-19. doi: 10.1080/10798587.1999.10750747.

10.

Păun

. Computing with membranes. J Comput Syst Sci 2000; 61: 108-143.

11.

Păun

. A quick introduction to membrane computing. J Log Algebr Program 2010; 79: 291-294.

12.

Wang

Shi

Peng

. Membrane computing model for IIR filter design. Inf Sci (Ny) 2016; 329: 164-176.

13.

Huang

Suh

Abraham

. Dynamic multi-objective optimization based on membrane computing for control of time-varying unstable plants. Inf Sci (Ny) 2011; 181: 2370-2391.

14.

Yan

Shao

Guo

. Weight optimization for case-based reasoning using membrane computing. Inf Sci (Ny) 2014; 287: 109-120.

15.

Buiu

Vasile

Arsene

. Development of membrane controllers for mobile robots. Inf Sci (Ny) 2012; 187: 33-51. doi: 10.1016/j.ins.2011.10.007.

16.

Pavel

Buiu

. Using enzymatic numerical P systems for modeling mobile robot controllers. Nat Comput 2011; 11: 387-393.

17.

Wang

Zhang

Neri

Jiang

Zhao

Gheorghe

, et al. Design and implementation of membrane controllers for trajectory tracking of nonholonomic wheeled mobile robots. Integr Comput Aided Eng 2016; 23: 15-30. doi: 10.3233/ICA-150503.

18.

Wang

Zhang

Zhao

Rong

Ipate

Lefticaru

. A modified membrane-inspired algorithm based on particle swarm optimization for mobile robot path planning. Int J Comput Commun Control 2015; 732-745.

19.

Langer

Cienciala

Ciencialová

Perdek

Kelemenová

. An application of the PCol automata in robot control. 11th Brainstorming Week Membr Comput 2013; 153-164.

20.

Cienciala

Ciencialová

Langer

Perdek

. The abilities of P colony based models in robot control. Proc 15th Int Conf Membr Comput, Springer International Publishing 2014; 155-168.

21.

Florea

Buiu

. Lulu_C – an open-source software simulator of P colonies and P swarms written in C 2017. https://github.com/andrei91ro/lulu_pcol_sim_c.

22.

Florea

Buiu

. P/XP colony controller for real and simulated Kilobots 2017. https://github.com/andrei91ro/lulu_kilobot_c.

23.

Florea

Buiu

. Finite state machine controller for real and simulated Kilobots 2017. https://github.com/andrei91ro/fsm_kilobot_c.

24.

Florea

Buiu

. Experimental results for the color segregation multi-robot task implemented on real and simulated Kilobots using P colonies and finite state machines 2017. doi: 10.17632/d23k8z255y.1.

25.

Parker

. Path planning and motion coordination in multiple mobile robot teams. Encycl Complex Syst Sci, New York, NY: Springer New York 2009; 5783-5800. doi: 10.1007/978-0-387-30440-3_344.

26.

Ducatelle

Di Caro

Förster

Bonani

Dorigo

Magnenat

, et al. Cooperative navigation in robotic swarms. Swarm Intell 2014; 8: 1-33. doi: 10.1007/s11721-013-0089-4.

27.

Caglioti

Citterio

Fossati

. Cooperative, distributed localization in multi-robot systems: A minimum-entropy approach. Distrib Intell Syst Collect Intell Its Appl IEEE 2006; 25-30. doi: 10.1109/DIS.2006.20.

28.

Kolling

Walker

Chakraborty

Sycara

Lewis

. Human interaction with robot swarms: A survey. IEEE Trans Human-Machine Syst 2016; 46: 9-26. doi: 10.1109/THMS.2015.2480801.

29.

Martinson

Arkin

. Learning to role-switch in multi-robot systems. IEEE Int Conf Robot Autom (Cat. No. 03CH3 7422) IEEE 2003; 2727-2734. doi: 10.1109/ROBOT.2003.1242005.

30.

Montijano

Sagüés

. Distributed consensus with visual perception in multi-robot systems. Cham: Springer International Publishing 2015. doi: 10.1007/978-3-319-15699-6.

31.

Nascimento

Moreira

Scolari Conceição

Bonarini

. Intelligent state changing applied to multi-robot systems. Rob Auton Syst 2013; 61: 115-124. doi: 10.1016/j.robot.2012.10.011.

32.

Yasuda

. Multi-robot systems, trends and development. InTech 2011. doi: 10.5772/544.

33.

Ramezan Shirazi

Sun

Jin

. Bio-inspired self-organising multi-robot pattern formation: A review. Rob Auton Syst 2017; 91: 83-100. doi: 10.1016/j.robot.2016.12.006.

34.

Gauci

Chen

Dodd

Groß

. Evolving aggregation behaviors in multi-robot systems with binary sensors. Springer, Berlin, Heidelberg 2014; 355-367. doi: 10.1007/978-3-642-55146-8_25.

35.

Trianni

. Evolutionary swarm robotics: Evolving self-organising behaviours in groups of autonomous robots. Springer 2008.

36.

Santos

Campos

MFM

Chaimowicz

. On segregative behaviors using flocking and velocity obstacles. Springer, Berlin, Heidelberg 2014; 121-133. doi: 10.1007/978-3-642-55146-8_9.

37.

Kumar

Garg

Kumar

. Segregation of heterogeneous units in a swarm of robotic agents. IEEE Trans Automat Contr 2010; 55: 743-748. doi: 10.1109/TAC.2010.2040494.

38.

Gross

Magnenat

Mondada

. Segregation in swarms of mobile robots based on the Brazil nut effect. IEEE/RSJ Int Conf Intell Robot Syst, IEEE 2009; 4349-4356. doi: 10.1109/IROS.2009.5353942.

39.

Valentini

Ferrante

Hamann

Dorigo

. Collective decision with 100 Kilobots: Speed vs accuracy in binary discrimination problems. IRIDIA – Tech Rep Ser 2015.

40.

Rubenstein

Cornejo

Nagpal

. Robotics programmable self-assembly in a thousand-robot swarm. Science 2014; 345: 795-799.

41.

Rubenstein

Ahler

Hoff

Cabrera

Nagpal

. Kilobot: A low cost robot with scalable operations designed for collective behaviors. Rob Auton Syst 2014; 62: 966-975.

42.

Pinciroli

Lee-Brown

Beltrame

. Buzz: An extensible programming language for self-organizing heterogeneous robot swarms 2015.

43.

Kelemen

Kelemenová

Păun

. Preview of P colonies: A biochemically inspired computing model. Work Tutor Proceedings, ( Bedau

et al. eds ). Ninth Int Conf Simul Synth Living Syst (Alife IX), Boston, Mass 2004; 82-86.

44.

Păun

. Introduction to membrane computing. Appl Membr Comput. Ciobanu

Păun

Pérez-Jiménez

(editors). Springer Berlin Heidelberg 2006; 1-42. doi: 10.1007/3-540-29937-8_1.

45.

Kelemen

Kelemenová

. On P colonies, a simple bio-chemically inspired model of computation. 6th Int Symp Comput Intell. Rudas

(editor). Budapest Tech 2005; 40-56.

46.

Florea

Buiu

. Development of a software simulator for P colonies – applications in robotics. Int J Unconv Comput 2016; 12: 189-205.

47.

Rubenstein

Ahler

Nagpal

. Kilobot: A low cost scalable robot system for collective behaviors. IEEE Int Conf Robot Autom, IEEE 2012; 3293-3298. doi: 10.1109/ICRA.2012.6224638.

48.

Florea

Buiu

. Membrane computing for distributed control of robotic swarms: Emerging research and opportunities. IGI Global, USA 2017. doi: 10.4018/978-1-5225-2280-5.

49.

Lopes

Leal

Dodd

Groß

. Application of supervisory control theory to swarms of e-puck and Kilobot robots. Swarm Intell, Springer International Publishing 2014; 62-73. doi: 10.1007/978-3-319-09952-1_6.

50.

Dash

Dasgupta

Chepada

Halder

. Event driven programming for embedded systems – a finite state machine based approach. Sixth Int Conf Syst 2011; 19-23.

51.

Brooks

. A robust layered control system for a mobile robot. IEEE J Robot Autom 1986; 2: 14-23 doi: 10.1109/JRA.1986.1087032.

52.

R Core Team. R: A language and environment for statistical computing 2016. https://www.r-project.org/.

53.

Jansson

Hartley

Hinsch

Slavkov

Carranza

Olsson

TSG

, et al. Kilombo: A Kilobot simulator to enable effective research in swarm robotics. arXiv Prepr arXiv151104285 2015.

54.

Wang

Olson

. AprilTag 2: Efficient and robust fiducial detection. Proc IEEE/RSJ Int Conf Intell Robot Syst 2016.

55.

R Core Team. Scale function | R Documentation. https://www.rdocumentation.org/packages/base/versions/3.4.1/topics/scale (accessed July 8, 2015).

56.

Kernbach

. Improving the scalability of collective systems. In: Handb Collect Robot Fundam Challenges. Kernbach

(editor). Pan Stanford 2013; 309-353.

A distributed approach to the control of multi-robot systems using XP colonies

Abstract

Keywords

1. Introduction

2. Preliminaries

2.1 Collective behaviours in MRSs

2.2.1 The standard P system

2.4 Lulu_Kilobot – a P/XP colony based controller

Table 1 Short description of the basic objects used for symbolic conversion of the input data [48]

3. Case study

4. Discussions

4.1 Execution environments

4.1.1 Physically realistic simulations

4.1.2 Experiments on real robots

4.2 Results on segregation

5. Conclusions and further work

Footnotes

Acknowledgments

References

Table 1
Short description of the basic objects used for symbolic conversion of the input data [48]