In this paper, we study the translational and rotational ($SE(N)$) invariance properties of locally interacting multi-agent systems. We focus on a class of networked systems, in which the agents have local pairwise interactions, and the overall effect of the interaction on each agent is the sum of the interactions with other agents. We show that such systems are $SE(N)$-invariant if and only if they have a special, quasi-linear form. The $SE(N)$-invariance property, sometimes referred to as "left invariance", is central to a large class of kinematic and robotic systems. When satisfied, it ensures independence to global reference frames. In an alternate interpretation, it allows for integration of dynamics and computation of control laws in the agents' own reference frames. Such a property is essential in a large spectrum of applications, e.g., navigation in GPS-denied environments. Because of the simplicity of the quasi-linear form, this result can impact ongoing research on design of local interaction laws. It also gives a quick test to check if a given networked system is $SE(N)$-invariant.
We propose a new formulation and algorithms for the Vehicle Routing Problem (VRP). To accommodate persistent surveillance missions, which require executions in infinite time, we define Persistent VRP (P-VRP). The vehicles consume a resource, such as gas or battery charge, which can be replenished when they visit replenish stations. The mission specifications are given as rich, temporal logic statements about the sites, their service durations, and the time intervals in which services should be provided. We define a temporal logic, called Time-Window Temporal Logic (TWTL), whose formulae allow for simple, intuitive descriptions of such specifications. Two different optimization criteria are considered. The first is the infinite-time limit of the duration needed for the completion of a surveillance round. The second penalizes the long-term average of the same quantity. The proposed algorithms, which are based on concepts and tools from formal verification and optimization, generate collision-free motion plans automatically from the temporal logic statements and vehicle characteristics such as maximum operation time and minimum replenish time. Illustrative simulations and experimental trials for a team of quadrotors involved in persistent surveillance missions are included.
In this work, we present a novel method for automating persistent surveillance missions involving multiple vehicles. Automata-based techniques were used to generate collision-free motion plans for a team of vehicles to satisfy a temporal logic specification. Vector fields were created for use with a differential flatness-based controller, allowing vehicle flight and deployment to be fully automated according to the motion plans. The use of charging platforms with the vehicles allows for truly persistent missions. Experiments were performed with two quadrotors over 50 runs to validate the theoretical results.
We develop a sampling-based motion planning algorithm that combines long-term temporal logic goals with short-term reactive requirements. The mission specification has two parts: (1) a global specification given as a Linear Temporal Logic (LTL) formula over a set of static service requests that occur at the regions of a known environment, and (2) a local specification that requires servicing a set of dynamic requests that can be sensed locally during the execution. Our method consists of two main ingredients: (a) an off-line sampling-based algorithm for the construction of a global transition system that contains a path satisfying the LTL formula, and (b) an on-line sampling-based algorithm to generate paths that service the local requests, while making sure that the satisfaction of the global specification is not affected. Building on our previous work [1], the focus of this paper is on the on-line part of the overall method.
In this paper, we propose a sampling-based motion planning algorithm that finds an infinite path satisfying a Linear Temporal Logic (LTL) formula over a set of properties satisfied by some regions in a given environment. The algorithm has three main features. First, it is incremental, in the sense that the procedure for finding a satisfying path at each iteration scales only with the number of new samples generated at that iteration. Second, the underlying graph is sparse, which guarantees the low complexity of the overall method. Third, it is probabilistically complete. Examples illustrating the usefulness and the performance of the method are included.
This paper presents a new computational paradigm which can be successfully applied in robotics for the control of autonomous mobile robots. Membrane computing is a naturally parallel and distributed model of computation inspired by the structure and functioning of living cells. Numerical P systems, a type of membrane systems which operates with numerical values, and the extension, enzymatic numerical P systems, were used for modeling robot behaviors. Current results and developments of this innovative approach are also discussed and analyzed.
This paper provides the proof that Enzymatic Numerical P systems with deterministic, but parallel, execution model are universal, even when the production functions used are polynomials of degree 1. This extends previous known results and provides the optimal case in terms of polynomial degree.
We study the computing power of a class of numerical P systems introduced in the framework of autonomous robot control, namely enzymatic numerical P systems. Three ways of using the evolution programs are investigated: sequential, all-parallel and one-parallel (with the same variable used in all programs or in only one, respectively); moreover, both deterministic and non-deterministic systems are considered. The Turing universality of some of the obtained classes of numerical P systems is proved (for polynomials with the smallest possible degree, one, also introducing a new proof technique in this area, namely starting the universality proof from the characterization of computable sets of numbers by means of register machines). The power of many other classes remains to be investigated.
We developed a sampling-based motion planning algorithm that combines long-term temporal logic goals with short-term reactive requirements. The mission specification has two parts: (1) a global specification given as a Linear Temporal Logic (LTL) formula over a set of static service requests that occur at the regions of a known environment, and (2) a local specification that requires servicing a set of dynamic requests that can be sensed locally during the execution. The proposed computational framework consists of two main ingredients: (a) an off-line sampling-based algorithm for the construction of a global transition system that contains a path satisfying the LTL formula, and (b) an on-line sampling-based algorithm to generate paths that service the local requests, while making sure that the satisfaction of the global specification is not affected. The off-line algorithm has three main features. First, it is incremental, in the sense that the procedure for finding a satisfying path at each iteration scales only with the number of new samples generated at that iteration. Second, the underlying graph is sparse, which guarantees the low complexity of the overall method. Third, it is probabilistically complete. We also provide a conditional result showing that the incremental checking procedure has the best possible complexity bound. The on-line algorithm leverages ideas of potential functions, which ensure progress towards satisfaction of the global specification, and on monitors for LTL. Examples illustrating the usefulness and the performance of the framework are included.
Membrane computing is an interdisciplinary research field focused on new computational models, also known as P systems, inspired by the compartmental model of the cell and the membrane transport mechanisms. Numerical P systems are a type of P systems introduced by Gh. Păun in 2006 for possible applications in economics. Recently, an extension of numerical P systems, enzymatic numerical P systems, has been defined in the context of robot control. This paper presents a new approach to modeling and implementing autonomous mobile robot behaviors and proposes a new odometry module implemented with enzymatic numerical P systems for robot localization. The advantages of modeling robot behaviors with enzymatic membrane controllers and the experimental results obtained on real and simulated robots are also discussed.
The main contribution of this paper is the introduction of the new concept of membrane controller based on the structure and functioning of a deterministic numerical P system. The procedure for developing a membrane controller and for using it to control a mobile robot is explained and several test cases are given in which membrane controllers are used to control both simulated and real mobile robots and to generate various desired behaviours (obstacle avoidance, wall following, and follow the leader). The experiments reported in this paper validate the concept and prove that the performance of a membrane controller is comparable to or better than that of other controllers (such as fuzzy logic controllers).
The main result of the paper is the proof that Enzymatic Numerical P Sytems with deterministic, but parallel, execution model are universal, even when the production functions used are polynomials of degree 1. This extends previous known results and provides the optimal case in terms of polynomial degree.
Membrane controllers have been developed using Numerical P Systems and their extension, Enzymatic Numerical P Systems, for controlling mobile robots like e-puck and Khepera III. In this paper we prove that membrane controllers can be easily adapted for other types of robotic platforms. Therefore, obstacle avoidance and follower behaviors were adapted for Koala robots. The membrane controllers for Koala robots have been tested on real and simulated platforms. Experimental results and performance analysis are presented.
This paper presents PyElph, a software tool which automatically extracts data from gel images, computes the molecular weights of the analyzed molecules or fragments, compares DNA patterns which result from experiments with molecular genetic markers and, also, generates phylogenetic trees computed by five clustering methods, using the information extracted from the analyzed gel image. The software can be successfully used for population genetics, phylogenetics, taxonomic studies and other applications which require gel image analysis. Researchers and students working in molecular biology and genetics would benefit greatly from the proposed software because it is free, open source, easy to use, has a friendly Graphical User Interface and does not depend on specific image acquisition devices like other commercial programs with similar functionalities do.
PyElph software tool is entirely implemented in Python which is a very popular programming language among the bioinformatics community. It provides a very friendly Graphical User Interface which was designed in six steps that gradually lead to the results. The user is guided through the following steps: image loading and preparation, lane detection, band detection, molecular weights computation based on a molecular weight marker, band matching and finally, the computation and visualization of phylogenetic trees. A strong point of the software is the visualization component for the processed data. The Graphical User Interface provides operations for image manipulation and highlights lanes, bands and band matching in the analyzed gel image. All the data and images generated in each step can be saved. The software has been tested on several DNA patterns obtained from experiments with different genetic markers. Examples of genetic markers which can be analyzed using PyElph are RFLP (Restriction Fragment Length Polymorphism), AFLP (Amplified Fragment Length Polymorphism), RAPD (Random Amplification of Polymorphic DNA) and STR (Short Tandem Repeat). The similarity between the DNA sequences is computed and used to generate phylogenetic trees which are very useful for population genetics studies and taxonomic classification.
PyElph decreases the effort and time spent processing data from gel images by providing an automatic step-by-step gel image analysis system with a friendly Graphical User Interface. The proposed free software tool is suitable for researchers and students which do not have access to expensive commercial software and image acquisition devices.
This paper presents an original approach to the control of mobile robots using natural computing based solutions, which fall beyond traditional use of Artificial Intelligence and bio-inspired methods in robot control. The idea is to use the modeling power of P systems, which are based on the structure and functioning of living cells. Results obtained so far are presented in a synthetic way and directions for further developments are given.
This paper presents a particle swarm optimization (PSO)-inspired multi-robot search application based on an innovative software system for collaborative robotic applications. The system has a multi-layer architecture which provides low- and high-level interfaces to the robots, resource (robots) management, security policies and concurrent robot access. The main result is the successful testing of the PSO-inspired algorithm on real-world experiments, using Khepera III and e-puck robots. Simulated results obtained in other studies are therefore validated by the real-world experiments. Differences between simulation and real-world experiments are presented and discussed critically.
A multi-agent control architecture for swarm robotics applications which includes an innovative human-swarm interface is proposed. The architecture is designed to allow an operator to monitor and guide a robotic swarm to accomplish its missions. The system is composed of three types of agents, a graphical user interface agent, and a pair of a local and a social agent for each robot in the swarm. The local agent implements low level robot-specific functionalities like movement, obstacle avoidance and localization. The control algorithm is implemented in the social agent and is based on an adapted distributed version of the Particle Swarm Optimization technique. An original method, Gravity Points Method, for representing goals which are used by the human-swarm interface is also proposed. Experimental results using simulated e-puck robots are presented and directions for further developments are given.
A cognitive collaborative multi-agent control architecture that addresses real-world control problems for swarms of mobile robots is proposed. The swarm's emergent behaviour is obtained by using a distributed Particle Swarm Optimization inspired algorithm. A swarm-user interface is also presented and offers a way for a human operator to interact with and guide the robotic swarm without limiting its emergent intelligence. The architecture is designed as a multi-agent system developed using JADE Framework. Three types of agents were defined: local behaviour agent, social behaviour agent and graphical user interface (GUI) agent. Each robot is associated with a pair of a local and a social behaviour agents which implement the reactive component and the interaction between the robots. The swarm forms a hierarchical structure composed of subswarms and neighbourhoods based on tasks and goals defined by the user or the swarm itself. The GUI agent is used as a link between the human expert and the swarm. The architecture was tested on a swarm of e-puck robots.
Ecology is a challenging application area for mobile service robots. They should be able to automate tasks that are too tedious or dangerous for humans to execute, such as collecting waste material. Such a robot must make use of several senses, of which the most important and difficult to implement is vision. This paper presents the cognitive vision system of ReMaster One, an autonomous service robot that is able to recognize and sort waste in an indoor environment. A first prototype has been built and tested with success.
