Self-Organizing Models[1]

Posted on

We discussed in the previous post one of self-organizing models which is Emergent Motion Control Model and talked briefly about flocking algorithm, in this post we’ll talk about its opposite.

Unlike many social animals that stay together as a group showing a collective behaviors such as flocking, there are some animals that survive due to different social behaviors called solitary behaviors, and that’s we are going to talk about in this post — the behavior of solitary animals [Anti-Flocking].

Overview

The Cooperative behavior of the solitary animals can be thought of high-level cooperative communication based on neighborhood or without explicit communication in most of the cases.

This cooperation pattern relies on achieving implicit communication between the cooperating agents via the environment, for example through marking trees by spraying urine and anal gland secretions.

Anti-flocking algorithm is inspired by this cooperative behavior that targets mainly maximizing search coverage and minimizing overlapping.

Anti-Flocking Algorithm

Rules of Anti-Flocking algorithm can be summarized as follows:

  1. Collision Avoidance: Stay away from the nearest obstacle that’s within safe distance.
  2. De-Centering: attempt to move apart from its neighbors
  3. Selfishness: if neither the above two situations happen, move to a directions which can maximize one’s own interest.

1

  • About the first rule — Collision avoidance — it’s very easy to understand and implement, using mobile sensors the obstacles can be detected whatever it’s an outer obstacle or a neighbor unit, and the mentioned safe distance can be achieved through experiments or other more intelligent adaptive algorithms such as Fuzzy Neural Network.
  • The second rule is decentralizing or we can name it dispersing which is the method of scattering the available sensing resources over the whole area of interest.With setting the neighborhood radius, which is usually decided by the communication range of mobile sensors, each mobile sensor moves away from the center of its neighbors.
  • About the last rule — Selfishness — is applied when neither obstacles nor neighbors appears, in this case, the mobile sensor moves to the direction that maximizes one’s interest.

Algorithm 

Require: AOI Map, Neighborhood Radius, Gain Growth Rate.
1: Initialization environment:
2: Setup specfications of mobile sensors
3: Setup gain model of AOI
4: repeat
5:     Sensing obstacles
6:    Sensing neighbors
7:    if obstacles exist then
8:          Invoke obstacle avoidance routine
9:    else if neighbors  != null then
10:        Calculate centroid of neighbors
11:         Move to the opposite direction to the centroid
12:  else
13:        Calculate gains of surrounding directions
14:        Move to the direction with maximum gain
15:  end if
16: Update gain of AOI
17: until Command of Task-End

References:

  • Novel Mobility Model for Mobile Sensors Deployment in Surveillance Systems – Alaa Khamis.
  • A Study of Mobility Models in Mobile Surveillance Systems – Yun-Qian Miao.

Self-Organizing Models[0]

Posted on Updated on

Overview

In field of swarm robotics, we have to define a model that describes the way that each robot behaves locally  and the set of robots globally, as they acting as a one unit, some questions must be asked: how they can communicate with each other ?!, how they will take their decisions ?! , what if more than on robot took the decision to navigate to the same point ?! .. and so on. This is the self-Organizing.

What’s Self-Organization ?!

Self-Organization is the process where some form of global order or coordination arises out of the local interactions between the components of an initially disordered system.This process is not controlled by any Agent or subsystem inside or outside of the system The result of this process, the organization is wholly decentralized over all of the components of the system, such of these systems are very robust and able to survive and self-repair substantial damage.

 Examples of Self-Organizing systems:

  • Swarming in groups of animals
  • The way neural networks learn to recognize complex patterns
  • Swarm Robotics

Self-Organization usually relies on 3 ingredients:

  • Strong dynamical non-linearity, often though not necessarily involving positive and negative feedback.
  • Balance of exploitation and exploration.
  • Multiple interactions.

We can notice all of these ingredients in Swarm Robotics Systems. In swarm robotics, self-Organization is used to produce emergent behavior. Let’s talk more about these behaviors in Swarm Robotics.

Mobility Models of Mobile Sensors:

The mobility control strategy for mobile is a coordination strategy that addresses the inter-dependency management among these distributed agents. Based on this strategy, mobile sensors can move together in such a concert that achieves certain objectives.

There are multiple models, we’ll talk in details about them in the upcoming posts, but we pick one of them in this post, which is Emergent Motion Control Model.

Emergent Motion Control Model:

self-Organizing formation is an emergent process of making whole forms by local interactions of distributed simple autonomous entities without global information at all and without depending on initial position and orientation of the elements.

These simple autonomous entities store local information and guiding rules needed for the colonial self-organization.

The outcome is an adaptable complex systems that can perform many tasks , learn and change itself accordingly.

Properties of Self-Organizing systems:

  1. The main property in this model is the absence of central control
  2. Adaptable due to emerging structures
  3. High scalability

The most noticeable matter in all of these models, all of them are inspired by nature, and this self-organization can be easily noticed in fish schooling which each fish can utilize the pressure field created by the next fish when they cruise in a close group, also can be noticed clearly in bird flocking  … etc

Let’s watch  real experiments

In the upcoming posts we’ll talk more about other mobility models like anti-flocking model.

References:

Novel Mobility Model for Mobile Sensors Deployment in Surveillance Systems – Alaa Khamis.

Why a Robot should study Probability ?

Posted on Updated on

In the previous post, we mentioned that one of the most challenges that face any robot in the real world is the uncertainty. So in this post we will try to go deeper in this problem and try to propose an introduction to a powerful solution called “Probabilistic Robotics”.

Can anyone answer the question mentioned in the title, “Why a Robot should study Probability?” The answer is very obvious: The Robot has an exam tomorrow 🙂 . I’m kidding of course not, In order to answer this question we have first to talk about the classical usual approach for robotics systems and why we cannot use it to solve the uncertainty problem.

The designer of the robot has his own human conception of the environment. This conception may be expressed in very abstract terms using analytic, geometric and symbolic descriptions:

  • Analytic functions to encode the laws of physics
  • Geometric language to describe the shapes of the objects and their positions and movements in the 3 dimensions space.
  • Symbolic notation to name objects and concepts.

The programmer, in some sense, imposes his own model of the environment to the robot when using these terms in his programs, (see Figure 1). Everything is fine with this approach as long as the environment is not too complex. For instance, in the field of industrial robotic, the environment of the robot may be controlled and kept simple enough to build model using this kind of descriptions.

By “autonomous robotics” we mean precisely, cases where the environment may not be constrained. In these cases the classical technique just described run into some very serious troubles. The principal difficulty is a very classical artificial intelligence issue known as the “symbol grounding” problem. The robot has to bridge the gap between the raw signals coming from its sensors and the abstract model used in its programs.

In practice, it means that the robot should be able to reason using uncertain knowledge (Noisy Sensors) and using incomplete knowledge.

The basic idea is to invert the process by which the programmer imposes his conception of the environment to the robot. We want the robot to build its own “internal representations” of the environment and to propose these “models” to the programmer as the basic programming tools (see Figure 2).

To reach this new robotics approach to solve the uncertainty problem, we can rely on the “Probability as logic” theorem. By inference we mean simply: deductive reasoning whenever enough information is at hand to permit it; inductive or probabilistic reasoning when – as is almost invariably the case in real problems – all the necessary information is not available. Thus the topic of “Probability as Logic” is the optimal processing of uncertain and incomplete knowledge.

So, What is Probabilistic robotics ?

Probabilistic robotics is a new approach to robotics that pays tribute to the uncertainty in robot perception and action. The key idea of probabilistic robotics is to represent uncertainty explicitly, using the calculus of probability theory. Put differently, instead of relying on a single “best guess” as to what might be the case in the world; probabilistic algorithms represent information by probability distributions over a whole space of possible hypotheses. By doing so, they can represent ambiguity and degree of belief in a mathematically sound way, enabling them to accommodate all sources of uncertainty mentioned in this post. Moreover, by basing control decisions on probabilistic information, these algorithms degrade nicely in the face of the various sources of uncertainty described above, leading to new solutions to hard robotics problems.

For Example:- Localization Problem 

Let us illustrate the probabilistic approach with a motivating example: mobile robot localization. Localization is the problem of estimating a robot’s coordinates in an external reference frame from sensor data, using a map of the environment. The specific localization problem studied here is known as global localization, where a robot is placed somewhere in the environment and has to localize itself from scratch. In the probabilistic paradigm, the robot’s momentary estimate (also called belief) is represented by a probability density function over the space of all locations. This is illustrated in the first diagram in the below figure, which shows a uniform distribution (the prior) that corresponds to maximum uncertainty. Suppose the robot takes a first sensor measurement and observes that it is next to a door. The resulting belief, shown in the second diagram in the below figure, places high probability at places next to doors and low probability elsewhere. Notice that this distribution possesses three peaks, each corresponding to one of the (indistinguishable) doors in the environment. Furthermore, the resulting distribution assigns high probability to three distinct locations, illustrating that the probabilistic framework can handle multiple, conflicting hypotheses that naturally arise in ambiguous situations. Finally, even non-door locations possess non-zero probability. This is accounted by the uncertainty inherent in sensing: With a small, non-zero probability, the robot might err and actually not be next to a door. Now suppose the robot moves. The third diagram in the below figure shows the effect of robot motion on its belief, assuming that the robot moved as indicated. The belief is shifted in the direction of motion. It is also smoothed, to account for the inherent uncertainty in robot motion. Finally, the fourth and last diagram in the below figure depicts the belief after observing another door. This observation leads our algorithm to place most of the probability mass on a location near one of the doors, and the robot is now quite confident as to where it is.

 We can use the Markov Property to model the localization problem.Markov localization addresses the problem of state estimation from sensor data.
Markov localization is a probabilistic algorithm: Instead of maintaining a single hypothesis as to where in the world a robot might be, Markov localization maintains a probability distribution over the space of all such hypotheses. The probabilistic representation allows it to weigh these different hypotheses in a mathematically sound way.
This Markov representation is based on the famous probability theorem “Bayes Theorem“(see the figure below) ,so in the next post we will talk more about this theorem and show how it is very powerful to solve the uncertainty localization problem.
Bayes Rule

Reference

Uncertainty In Robotics

Posted on

Scientific Definition

Assume that we want to make a scientific definition for word “ROBOTICS”, we can simply say:

Robotics is the Science of perceiving and manipulating the physical world through computer-controlled mechanical devices.

Robotics Systems Examples:

  • Arms that are used in assembly lines
  • Autonomous vehicles
  • Actuated arms that can assist surgeons
  • Warrior Robots

Robotics Systems have in common that they are situated in the physical world, perceive their environments through sensors, and manipulate their environment through things that move.
hence, the main goal in building any robotics system is to develop a robust software that enables the robot to treat with the numerous challenges arising in unstructured and dynamic environments.

from this sense we got the concept of Uncertainty, this uncertainty comes from the lack of information available to the robot in order to make some task, there are five different factors that affect on the Uncertainty of robots:

  1. Environment
    • from the above mentioned examples, the degree of uncertainty in assembly lines in very small as the environment is well-structured somehow, in contrast the autonomous vehicles on highways.

  • Sensors
    • Sensors are considered as the five senses of robots to collect information about the environment, there are two primary factors that affect on the limitations of sensors:
      1. Range and  resolution of the sensor.
      2. The noise that affect on the measurements
    • for example ultrasonic sensor, the measurements of ultrasonic are very poor in accuracy in contrast the accuracy of laser sensors.
  • Robots
    • Robot actuation involves motors that are, at least to some extent, unpredictable, due effects like control noise and wear-and-tear. Some actuators, such as heavy-duty industrial robot arms, are quite accurate. Others, like low-cost mobile robots, can be extremely inaccurate.

  • Models:
    • Models are inherently inaccurate. Models are abstractions of the real world. As such, they only partially model the underlying physical processes of the robot and its environment. Model errors are a source of uncertainty that has largely been ignored in robotics, despite the fact that most robotic models used in state-or-the-art robotics systems are rather crude.

  • Computation:
    • Robots are real-time systems, which limits the amount of computation that can be carried out. Many state-of-the-art algorithms are approximate, achieving timely response through sacrificing accuracy some of these algorithms are in the reference of the post.

References:

Probabilistic Robotics — Sebastian Thrun

Introduction to Area Exploration Problem

Posted on

Problem Definition

In Robotics, the exploration problem deals with the use of a robot to maximize the knowledge over a particular area. The exploration problem arises in mapping and search & rescue situations, where an environment might be dangerous or inaccessible to humans  (Wikipedia Definition)

Overview

The exploration problems appeared when the humans think to use robots discover unknown areas that may be dangerous or inaccessible for humans.
To date a large number of algorithms to solve the problem of autonomous exploration and mapping has been presented.
In general mobile robots need a map in order to operate in a particular environment. The ability of robots to autonomously travel around an unknown environment gathering the necessary information to obtain a useful map for navigation is called autonomous exploration.

Trials

Current state of the art system in absence of global position information, simultaneous localization and mapping (SLAM) techniques are deployed to construct a map.

As the robots move to unexplored zones, these zones are included in the map.Thus, the problem of autonomous exploration could be understood as a traveling salesman problem where the robot must plan the order to visit the remaining unexplored zones while minimizing the total traveled distance.

This way, there are greedy approaches where the robots move to the nearest or biggest unexplored zone, and more elaborated heuristic approaches. However,this is dynamic process in which the set of places to visit is changing continuously.

Unfortunately, closed form solutions to these problems are computationally expensive, have poor scalability, and are impractical in real world applications. In this sense, there are lots of techniques available in the literature that provide partial solutions to the problem.

In the wide spectrum of exploration methods, we can find techniques that focused in different aspects of the exploration, for instance trying to reduce the exploration time or increasing the map quality.

(MRS) Multi-Robots Systems and Area Exploration

Some techniques coordinate a multi-robot team, other techniques are designed for a single robot to explore unknown area, but currently most of research areas are interested in mutli-robot systems (MRS)  or actually swarm of robots because of many reasons like:

  1.  Reduce the exploration time, Multiple robots can explore area faster than one robot.
  2.  Improve the efficiency of mapping.
  3.  Ensure the success of the mission under any circumstances.
  4.  Easiness of enhancing the capabilities of the by joining new robots with enhanced features.

This was a simple introduction about area exploration problem, we’ll talk later about the key concepts in the exploration problem, and the developed techniques to solve this problem from the side of reducing the time of exploring unknown area using MRS.

References

Introduction to Swarm Robotics

Posted on Updated on

The computer revolution changed the human societies in different important fields like communication, transportation, industrial production and technological advances science. However, some problems cannot be tackled with traditional hardware and software; hence we need a new computing technique to solve these hard problems in the most efficient and optimized way. The Bio-Computing technique is new alternative for the standard computing as it becomes one of the most important techniques in the new science’s era.

Swarm intelligence is a very hot topic related to the bio-computing which its main goal is the performance optimization and robustness.

What is Swarm Intelligence ?

SI (Swarm Intelligence) systems are typically made up of a population of simple agents or boids interacting locally with one another and with their environment. The inspiration often comes from nature, especially biological systems. The agents follow very simple rules, and although there is no centralized control structure dictating how individual agents should behave, local, and to a certain degree random, interactions between such agents lead to the emergence of “intelligent” global behavior, unknown to the individual agents.

What is Swarm Robotics ?

Swarm robotics is a relatively new field that focuses on controlling large-scale homogeneous multi-robot systems. These systems are used to develop useful macro-level behaviors while being made of modules that are very simple in design and compact in size. These properties allow robot swarms to reach populations ranging from a dozen modules to hundreds of modules. The theme of simplicity and elegance resonates throughout swarm robotics research in both the designs of the robots as well as the algorithms that are devised for these systems.

Swarm Robotics vs. Single Robot

Robotic swarms have several advantages over their more complex individual robot counterparts and are the results of using many robots instead of just one. This is made possible by the simple design of the robot modules because they are often less expensive and easier to build. When comparing the capabilities of a robot swarm to the capabilities of an individual robot, it is best to view the swarm as an individual entity performing complex behaviors at the macro-level.

The first improvement is an obvious one: robot swarms are able to cover more area than an individual robot. This is analogous to distributed search algorithms that are able to cover different parts of a search space at once.

The second improvement over individual robots is swarm robots are fault tolerant because the swarm robotics algorithms do not require robots to depend on one another. If a single module fails, the rest of the swarm can continue performing its actions as if that module never existed. Meanwhile, an individual robot system may become worthless if there is a failure in a critical component. This type of robustness is an extremely important feature in complex or hostile environments. Another feature of robot swarms is their effectiveness scales well with the number of members. Adding more robots is all that has to be done to increase the effectiveness of a swarm. The algorithms for swarms scale well and do not depend on the number of robots. On the other hand, it is not always clear how to improve the effectiveness of an individual robot system. Often times improvements in hardware require additional software upgrades, which is not the case with swarms. These properties make multi-robot systems suitable for several application domains.

A very interesting video talking about a cooperative swarm between heterogeneous systems
Have Fun with the Future of Swarm

Reference