Feeds:
Posts
Comments

Archive for the ‘Nature Inspired Computing’ Category

I came across a very cool video today morning and that gives this post its name. Before I get into that, I think it would be much desirable to give an introduction to Ornithopters in general and talk about some robotic ornithopters. For those interested solely in the video, well it is at the end of the post (second last video).

______

Introduction

An Ornithopter basically means an aircraft (even a robot) that can fly by flapping its wings. Though the word might sound complicated initially (Although the prefix Ornith- is well known). All of us at some point in time (whether as a childhood fantasy or as a serious hobby or professional work) have wanted Ornithopters. Ornithopters have been a fantasy since very ancient times, and it is obvious to have been as birds have always fascinated and amazed humans. There have been many reported Ornithopters in Hindu mythology. Also the legend of Daedalus and Icarus is well known, in which Daedalus designed feathered wings to fly out of the island of Crete on to which he was imprisoned.

The legendary Leonardo Da Vinci – A genius  imprisoned in a time where his ideas just could not have been realized, made some designs of Ornithopters and other glider type flying machines (but let’s avoid machines that do not have any moving wings in this post, though some are very cool). Some of which were very good engineering designs.

design_for_a_flying_machine

Click to Enlarge

Though we tend to regard the idea of wing powered machines as failed because of the success of modern day style aircraft there have been many successful flights. The first reported to have flown successfully was made in 1929 by Alexander Lippisch, it flew about 300 meters before the flight was terminated due to the obvious limitations of human muscle power. A number of motorized ornithopters have been made since then. A number of people take  Ornithopters as a serious hobby.

______

Modern Ornithopters

These days though, the interest has been more in ornithopters that resemble insects, such as bees, both as toys and sophisticated autonomous flying spy robots. The size of such Miniature Aerial Vehicles would ensure they are impossible to detect and hence are perfect for spying missions. Especially in the case of urban warfare when the opposing party might be holed up in a building. Thus, needless to say these can be very helpful in counter-terror operations. The aim in making such bots would be to make them very low cost with flight times as high as 5-6 hours. Let me cite some examples of some cool miniature aerial vehicles of the ornithopter category.

After some early feasibility studies done at the Lincoln laboratories at the MIT, DARPA in 1997 began a multi-million dollar program to make some sophisticated Miniature Aerial Vehicles (MAVs), some of the designs and projects also included ornithopters.

One such ornithopter was the MicroBat ornithopter developed at the California Institute of Technology along with AeroVironment and UCLA.

microbat

[The MicroBat Ornithopter, Image Source]

This paper reports the making  of the MicroBat Ornithopter. The excerpt to the paper:

This paper reports the successful development of “Microbat,” the first electrically powered palm-sized ornithopter. This first prototype was flown for 9 seconds in October 1998. It was powered by two 1-farad super capacitors. Due to the rapid discharge of the capacitor power source, the flight duration was limited. To achieve a longer flight, a rechargeable battery as a power source is preferred. The second prototype houses a small 3-gram rechargeable Ni-Cad battery. The best flight performance for this prototype lasted 22 seconds. The latest and current prototype is radio-controlled and is capable of turning left or right, pitching up or down. It weighs approximately 12.5 grams. So far, the best flight duration achieved is 42 seconds. The paper also discusses the study of flapping-wing flight in the wind tunnel using wings developed by MEMS technology. This enables a better understanding the key elements in developing efficient wings to achieve aerodynamic advantage in flapping-wing flight.

Another research group led by Robert C. Michelson made another Ornithopter called the Entomopter. This went one step ahead and can be called a milestone in MAV ornithopter development. The aim was to closely mimick the flight of birds and thus totally eliminate the usage of gears and motors. The entomopter is driven by wings that are driven by a reciprocating chemical muscle.

yellow_sla_entomopter

Click to Enlarge

______

Ornithopter Toys

There are now a number of companies that offer ornithopter toys. One of the most well known probably is the FlyTech Dragonfly from WowWee, It is a remote controlled wireless ornithopter. It seems like a pretty fun toy. You can see a video on this toy here >>

800px-flytech_dragonfly_blue_1200px [FlyTech DragonFly Ornithopter]

A number of people take making ornithopters as a very serious hobby. If you wish to make one, then I would direct you to this page.

______

Butterfly Ornithopter

Finally I come to the part that gave this blog post its title. ;-)

In a paper at IROS 2008, researchers from the Shimoyama – Matsumoto Lab at the university of Tokyo presented their work on an extremely light butterfly ornithopter.

butterfly_ornithopter_univ_tokyo

[Butterfly Ornithopter: Image Source]

The artificial butterfly wing consists of a thin polymer membrane which is supported by viens of plastic having rectangular cross section. The purpose of this paper was to study the effect of veins on the performance of flight. The parameters for this “butterfly” are more or less comparable to that of an actual butterfly.The weight of the ornithopter including the wings is just about 0.39 gms and the flapping frequency 10 Hz.

Here is a fantastic video of the Ornithopter depicted in the figure above:

______

Some more work on Ornithopters at Shimoyama – Matsumoto Lab:

Since I have just mentioned the work on the Butterfly Ornithopter, there is some cool work going at the Shimoyama – Matsumoto Lab on ornithopters.

>> Dragonfly Type of Ornithopters

>> Butterfly Type of Ornithopters

>> Hovering Flight of Ornithopters

taji1

[Hovering Type Ornithopter: Image Source]

______

Bio-Inspired Flying Robots

Finally before ending, I would like to post a bonus video ;-)

This video was the winner at the AAAI – 08 video contest. Like the video on Morphogenesis (Swarm Intelligence) which I posted about 10 months back, which was also a winner in the same contest, this video too is excellent.

______

Quick Links:

1. MAVSTAR – Micro Aerial Vehicles for Search Tracking and Reconnaissance.

2. A Reciprocating Chemical Muscle for Micro Air Vehicle “Entomopter” Flight – GTRI

3. Nano Air Vehicle – DARPA

4. Ornithopter Zone – Excellent site for the hobbyist.

5.  Project Ornithopter – Project on making Ornithopters on a much larger scale than those discussed in this post.

______

Onionesque Reality Home >>

Advertisements

Read Full Post »

In a number of seminars at a lot of universities or industry interactions one of the hot topics these days is efficient wireless power transfer and the pressing need and desirability of it. It is even more interesting given that wireless power is nothing new at all. One of the earliest patents in this area was given in 1900 to the legendary Nikola Tesla (Patent number: 649621) and there has been a discussion on it ever since. Probably now is the time to really realize Tesla’s vision with the number of devices of daily usage growing rapidly.

[Left Nikola Tesla | Right Alanson Sample, Intel Engineer Demonstrating WREL (Image Source)]

Intel has been at present working on what they call the Wireless Resonant Energy Link, which is based on the work of some MIT physicists. In the image above, an Intel engineer is seen demonstrating powering of a 60 W bulb wirelessly. Doing so requires more power than what is needed to charge a laptop. The implications of this technology can be immense. However the adverse effects of such technology on humans remain to be seen but are not viewed as a major impediment to its development.

Another area that is being discussed extensively these days is claytronics, catoms or simply programmable matter. Let’s take a brief digression into this before coming back to the original topic.

Claytronics: Claytronics seems to be one of the most futuristic and promising application areas of the intersection of Robotics, Swarm Intelligence and Computer Science among others. Claytronics is a field concerning reconfigurable nanoscale robots (which are called Claytronic Atoms or Catoms) which can operate as a swarm and can be desgined to form much more complex elements and perform complex tasks. These sub-millmeter computers eventually would have the ability to move around, communicate with other computers, and even electrostatically attach to each other to allow the swarm to take different shapes.

Catoms also referred to as programmable matter could reconfigure to form almost any shape, take any color or texture. Some interesting speculations include that catoms could be morphed to form replicas of humans (for virtual meetings) as well.  For a brief initiating idea have a look at the video below:

Work on this has been done by Prof Seth Goldstein and his group at Carnegie Mellon and is still on under the name the Claytronics Project. This work has been expanded upon by Intel researchers.

A senior researcher at Intel Jason Campbell has the following to say on just SOME possibilities that we could have in the future from programmable matter.

Think of a mobile device, My cell phone is too big to fit comfortably in my pocket and too small for my fingers. It’s worse if I try to watch movies or do my e-mail. But if I had 200 to 300 milliliters of catoms, I could have it take on the shape of the device that I need at that moment. For example, the catoms could be manipulated to create a larger keypad for text messaging. And when the device wasn’t being used, I could command it to form its smallest shape or even be a little squishy, so I can just drop it in my pocket.

Battery Powered Robots, An impediment to Research in SI based Robotic Systems:

There has been a lot of research going on swarm robotics. Taking just two examples, consider the work of James McLurkin of the CSAIL, MIT and the work at Ecole Polytechnique Federale de Lausanne (EPFL) in Lausanne, Switzerland. A lot of James’ work can be seen here, with a number of videos and papers available for download.

In the video below, a swarm of 278 miniature e-puck robots move around. All of them are battery powered. Battery powered robots can not only be a headache but a severe research impediment as the size of the swarm increases.

It thus would be very desirable that the swarm is wirelessly powered.

So, in short a lot of work is being done in the above two fields but what is also required is an intersection of the two, and this is exactly what Travis Deyle of Georgia Tech and Dr Matt Reynolds of Duke have done. Their work, Surface based wireless power transmission and bidirectional communication for autonomous robot swarms. presented at the IEEE ICRA this year details the construction of a 60cmx60cm surface that provides wireless power and bi-directional communication to an initial swarm of 5 line following robots. Each robot had a power consumption of about 200 mW.

[Image Courtesy : Travis Deyle]

An actual robot looks like the following in close up.

Wirelessly Powered Robot Swarm from Travis on Vimeo.

For more extensive details about the setup and circuit details have a look at their paper and the presentation slides.

Related Posts:

Morphogenesis and Swarm Robotics

Onionesque Reality Home >>

Read Full Post »

L-systems are very simple and elegant grammars (a set of rules and symbols) originally developed by biologist Aristid Lindenmayer to describe the growth of plants and trees.

tsr-fractals.jpg

These as we can see can lead to very beautiful figures as above!

Photo Credit.

The Lindenmayer system is recursive in nature which leads to self-similarity and hence fractal like structures. Plant models and natural-looking organic forms are similarly easy to define, as by increasing the recursion level the form slowly ‘grows’ and becomes more complex.

The components of a L-system are:

A) The alphabet, which is a finite set V of formal symbols or characters, generally they are taken to be letters A,B,C etc. These are the variables as they can be replaced. A set of symbols which will remain fixed are constants. These may be represented as another finite set.

B) The start, axiom or initiator ω, it basically is a string of symbols from V. If suppose V = {a,b,c} then ω can be aabc, abcc, abcab etc. There are many possibilities. This defines the initial state of the system.

C) Production rules, P that define how a variable can be replaced by a combination of variables and constants.

The rules of the L-system grammar are applied iteratively starting from the initial state. As many rules as possible are applied simultaneously, per iteration. This is the distinguishing feature of a L-system from a language.

There are many examples of the same that lead to very beautiful structures!

Some are:

A) Cantor Dust:

variables : A B

constants : none

start : A {starting character string}

rules : (A → ABA), (B → BBB)

Let A mean “draw forward” and B mean “move forward”.

Put in a different manner. We could say that a cantor dust fractal may be reconstructed using string rewriting using an initial cell {1} and then iterating the below rules.

{0->[0 0 0; 0 0 0; 0 0 0],1->[1 0 1; 0 0 0; 1 0 1]}.

Thus we would get the fractal as :

cantordustfractal_700.gif

B) Fractal Tree:

variables : X F

constants : + −

start : X

rules : (X → F-[[X]+X]+F[+FX]-X),(F → FF)

angle : 25°

Here, F means “draw forward”, – means “turn left 25º”, and + means “turn right 25º”. X does not correspond to any drawing action and is used to control the evolution of the curve. For n=6 the following figure may be generated.

453px-fractal-plantsvg.png

C) The Sierpinski Triangle:
variables : A B

constants : + −

start : A

rules : (A → B−A−B),(B → A+B+A)

angle : 60°

Here, A and B mean both “draw forward”, + means “turn left by angle”, and − means “turn right by angle”. The angle changes sign at each iteration so that the base of the triangular shapes are always in the bottom (they would be in the top and bottom, alternatively, otherwise).

Evolution for n = 2, n = 4, n = 6, n = 9

Other curves include the famous Koch Curve, Dragon Curve, Penrose Tilings etc.

Good places to do initial research on L-Systems:

1. Wikipedia

2. Fractinct L-system True Fractals, A tutorial by William Mcworter.

3. Fractals and Cellular Automata. by Daniel Shiffman.

4. Fractals and Recursion in the Nature of Code.

I would try to follow these initial posts on fractals with applications in RFID and in other smart antenna applications.

Also check out this voronoi fractal on this post. Credits to the image given in the original post.

voronoi-fractal

Read Full Post »

There have been quite a few posts on nature inspired computing. Here is another, this is a really cool video on the same. Have a look at the gait of the yellow salamander mimic bot and also the caterpillar bot at the end of the video!

Have fun!

The introduction to this video reads as:

Robotics researchers are increasingly turning to nature for inspiration. Watch a robotic salamander, a water strider robot, mechanical cockroaches and some cool self-configuring robots.

Footage courtesy of: University of Essex, Ecole Polytechnique Federale de Lausanne, Carnegie Mellon University, ULB-EPFL, Tokyo Institute of Technology, National Institute of Advanced Science and Technology (AIST).

My congratulations and best wishes to the researchers who are trying to develop such bots and also to New Scientist for such a good video!

Read Full Post »

There are four distinct advantages in using self organized, emergent, decentralized or “swarm intelligent” systems [1], these are in fact the benefits of a social insect colony as well. We see these colonies as the inspiration to developing artificial decentralized systems.

  1. Flexible: The system can react to internal and external changes.
  2. Robust: Tasks are completed even if some individuals fail
  3. Decentralized: There is no central control over the system
  4. Self Organized: Paths to solutions are emergent rather than pre-defined which leads to better utilization of resources and gives a dynamic character to the solution finding process.

Ants Behavior, Stigmergy and cues in Routing
Ants are very simple insects but collectively they can perform complex tasks with good consistency. Examples of such complex problem solving behavior have been documented, and a few examples are as follows.

  1. Building nests (ant hills) and maintenance.
  2. Regulating nest ambient temperature fluctuations very low and maintaining required levels of oxygen with small variations.
  3. Co-operating in carrying large prey.
  4. Finding the shortest routes from the nest to the food.
  5. Prefentially exploiting the richest food source available.

Stigmergy refers to communication indirectly, by using markers such as pheromones in ants. In the above examples, two distinct types of stigmergy are observed. One is called sematectonic stigmergy, it involves a change in the physical environment characteristics. An example of sematectonic stigmergy is nest building wherein an ant observes a structure developing and adds its ball of mud to the top of it. Another form of stigmergy is sign-based and hence indirect. Here something is deposited in the environment that makes no direct contribution to the task being undertaken but is used to influence the subsequent behaviour that is task related.

Here is an example of what sematectonic stigmergy can achieve (one has to keep in mind that individual termites are very simple creatures):

stigmergy1.jpg

Sign based stigmergy is very highly developed in ants. Ants use chemicals called as pheromones to develop a very sophisticated signaling system. Ants foraging for food lay down some pheromone which marks the path that they follow. An isolated ant moves at random but an ant encountering a previously laid trail will detect it and decide to follow it with a high probability and thereby reinforce it with a further quantity of pheromone. Since the pheromone will evaporate the lesser used paths will gradually vanish. We see that this is a collective behaviour.

The foraging behavior in ants can be best understood with the following illustrations.

Two ants start with equal probabilities of going on either path.

picture1.png

Ant taking the “lower” path has a shorter to and fro time from the nest to the food.

picture2.png

picture3.png

The pheromone density on the path traversed by ant on the lower path is greater because of the two passes by that ant on this path. Hence other ants say C and D are bound to follow this path because of the stronger scent.

picture6.png

Over many iterations many ants start using this path thus further reinforcing it and after a while this path i.e the shorter path is almost exclusively used.

So we see how randomness is followed by “positive feedback” which causes amplification and the consequent exclusive use of the shortest path. This is an apt example of how ants choose shortest paths.

Now if the shorter path is blocked or unavailable, then in this scenario the longer route may still be used and made the preferred route by repeated use(positive feedback) and the consequent amplification.

By repeated use of the other path, the pheromone concentration here gets stronger that leads to that path being used. Thus this is how ants develop a solution when a path is blocked. Thus this illustrates how swarm intelligent systems adapt with changes in the environment.

Mathematically we put the above as : Suppose the distance between two points i and j is dij and τij is the pheromone concentration on the link ij. Suppose ‘m’ agents are traversing this link and building a tour. At each step of the tour, the probability to go from one point ‘i’ to another point ‘j’ is (τij)a (dij)-b .

After building a tour of length L each agent reinforces the edges it has used by an amount proportional to 1/L. Also the pheromone evaporates such that τà(1-ρ)τ.

The above is used to solve the traveling salesman problem as well. There are a few key concepts that we gather from the above illustrations.

A) Positive feedback – build a solution using local solutions, by keeping good solutions in memory.

B) Negative feedback – want to avoid premature convergence, evaporate the pheromone.

C) Time scale – number of runs are also critical.

These key points then in turn can be summed up for an ant colony as very simple rules: lay pheromone, and follow trails of other ants.

Applications to Routing Scenarios
Routing is the mechanism that handles and directs messages at switching stations. The important points we see are that messages must reach their destinations, it should take as little time as possible to reach from source to destination, and also the traffic is constantly changing hence routing should adapt accordingly. The inspiration for using the example of ants for routing in communications networks arises from the fact that the present routing systems depend upon global information for their efficient operation. Ant systems on the other hand, rely on pheromone traces that are laid down in the network as the ant moves through the network. Global information is frequently out of date and transmission of the information required from one node to all others consumes considerable network bandwidth. Ideally, we would like to have the network adapt routing patterns to take advantage of free resources and move existing traffic if possible.

Now if we consider a telephone network. A telecommunication environment is highly unpredictable. With delays or problems when least expected at times. Suppose a phone call is made form Mumbai to Shanghai. This phone call has to go through several intermediate steps/nodes such as maybe Kolkatta and Bangkok etc. such a system requires a routing mechanism that will tell the call where it should hop next to establish a connection, a good routing technique as we have already listed would minimize this time (ants finding shortest path) and avoid congestions. Backup routes are very important in such a system. In some special circumstances when there is an explosion or if there is a news programme that requires calling, then it leads to localized surges in the phone traffic. This then requires the phone traffic to be re routed to the less congested parts of the network (ants adapting and finding an alternative path).

This can be simulated as follows. Hordes of agents can roam the network and leave bits of information which can be thought of as an analogous to pheromone to reinforce paths through uncongested areas. Phone calls are then routed by following the trails of these ants like agents. To exactly mimic the ants working, these “pheromones” can be evaporated by a certain mechanism by a rate that may be decided by certain considerations. Now if suppose a certain path that was very swift becomes congested then the agents to this route can be delayed by certain time spans. This time span will allow the virtual pheromone to evaporate and thus reinforcement process can be overcome. Hence after a while this route is abandoned. The ant-like agents (as seen above) can discover new paths to re-route the traffic. The advantages of such a system are: the calls get forwarded at a good speed and also the congested areas gradually get de congested. Also the bucket brigade process makes the routing process more robust.

A detailed approach to ant based routing has been described by White (1996)[2]. Such systems have three types of agents: explorers, allocators and deallocators. Explorer agents mimic the foraging behaviour of ants and follow trails of pheromones laid down by previous explorers (as quantitatively described in the Mumbai- Shanghai phone call example). Allocator agents move across the paths determined by explorer agents and allocate the bandwidth on the links used in the path. Similarly, when the path is no longer required deallocator agents traverse the path and deallocate the bandwidth used on the links.
References:

[1] E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm Intelligence: From Natural to Artifcial Systems. NY: Oxford Univ. Press, 1999.

[2] White A.R.P., Routing with Ants, Nortel internal report, 1996.

Read Full Post »