Category: zoology

Shouting at Memory: Where Did My Write Go?

Bat sending out sound waves
Image by 13smok from Pixabay modified by CS4FN

How can computer scientists improve computer memory, ensuring saving things is more secure? If Vasileios Klimis of Queen Mary, University of London’s Theory research group has his way, they will be learning from bats.

Imagine spending hours building the perfect fortress in Minecraft, complete with lava moats and secret passages; or maybe you’re playing Halo, and you’ve just customised your SPARTAN with an epic new helmet. You press ‘Save’, and breathe a sigh of relief. But what happens next? Where does your digital castle or new helmet go to stay safe?

It turns out that when a computer saves something, it’s not as simple as putting a book on a shelf. The computer has lots of different places to put information, and some are much safer than others. Bats are helping us do it better!

The Bat in the Cave

Imagine you’re a bat flying around in a giant, dark cave. You can’t see, so how do you know where the walls are? You let out a loud shout!

SQUEAK!

A moment later, you hear the echo of your squeak bounce back to you. If the echo comes back really, really fast, you know the wall is very close. If it takes a little longer, you know the wall is further away. By listening to the timing of your echoes, you can build a map of the entire cave in your head without ever seeing it. This is called echolocation.

It turns out we can use this exact same idea to “see” inside a computer’s memory!

Fast Desks and Safe Vaults

A computer’s memory is a bit like a giant workshop with different storage areas.

  • There’s a Super-Fast Desk right next to the computer’s brain (the CPU). This is where it keeps information it needs right now. It’s incredibly fast to grab things from this desk, but there’s a catch: if the power goes out, everything on the desk is instantly wiped away and forgotten! If your data is here, it is not safe!
  • Further away, there’s a Big, Safe Vault. It takes a little longer to walk to the vault to store or retrieve things. But anything you put in the vault is safe, even if the power goes out. When you turn the computer back on, the information is still there.

When you press ‘Save’ in your game, you want your information to go from the fast-but-forgetful desk to the slower-but-safe vault. But how can we be sure it got there? We can’t just open up the computer and look!

Shouting and Listening for Echoes

This is where we use our bat’s trick. To check where a piece of information is, a computer scientist can tell the computer to do two things very quickly:

  1. SHOUT! First, it “shouts” by writing a piece of information, like your game score.
  2. LISTEN! Immediately after, it tries to read that same piece of information back. This is like listening for the “echo”.

If the echo comes back almost instantly, we know the information is still on the Super-Fast Desk nearby. But if the echo takes a little longer, it means the information had to travel all the way to the Big, Safe Vault and back!

By measuring the time of that echo, computer scientists can tell exactly where the write went. We can confirm that when you pressed ‘Save’, your information really did make it to the safe place.

The Real Names

In computer science, we have official names for these ideas:

  • The Super-Fast Desk is called the Cache.
  • The Big, Safe Vault is called Non-Volatile Memory (or NVM for short), which is a fancy way of saying it doesn’t forget when the power is off.
  • The whole system of close and far away memory is the Memory Hierarchy.
  • And this cool trick of shouting and listening is what we call Memory Echolocation.

So next time you save a game, you can imagine the computer shouting a tiny piece of information into its own secret cave and listening carefully for the echo to make sure your progress is safe and sound.

– Vasileios Klimis, Queen Mary University of London

More on …

Getting Technical …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

An experiment in buoyancy

Here is a little science experiment anyone can do to help understand the physics of marine animals and their buoyancy. It helps give insight into how animals such as ancient ammonites and now cuttlefish can move up and down at will just by changing the density of internal fluids.* (See Ammonite propulsion of underwater robots). It also shows how marine robots could do the same with a programmed ammonite brain.

First take a beaker of water and a biro pen top. Put a small piece of blu tack over the the top of the pen top (to cover the holes that are there to hopefully stop you suffocating if you were to swallow one – never chew pen tops!). Next, put a larger blob of blu tack round the bottom of the pen top. You will have to use trial and error to get the right amount. Your aim is to make the pen top float vertically upright in the water, with the smaller blu tack just floating above the surface. Try it, by carefully placing the pen top vertically into the water. If it doesn’t float like that, dry the blu tack then add or remove a bit more until it does float correctly.

It now has neutral buoyancy. The force of gravity pulling it down is the same as the buoyancy force (or upthrust) pushing it upwards, caused by the air trapped in the top of the lid… so it stays put, neither sinking nor rising.

Now fill a drink bottle with water all the way to the top. Then add a little more water so the water curves up above the top of the bottle (held in place by surface tension). Carefully, drop in the weighted pen top and screw on the top of the bottle tightly.

The pen top should now just float in the water at some depth. It is acting just like the swim bladder of a fish, with the air in the pen top preventing the weight of the blue tack pulling it down to the bottom.

Now, squeeze the side of the bottle. As you squeeze, the pen top should suddenly sink to the bottom! Let go and it rises back up. What is happening? The force of gravity is still pulling down the same as it was (the mass hasn’t changed), so if it is sinking the buoyancy force pushing up must be less that it was.

What is happening? We are increasing the pressure inside the bottle, so the water is now compressing the air in the pen top, reducing its volume and increasing its density. The more dense your little diving bell is, the less the buoyancy force pushing up, so it sinks.

That is essentially the trick that ammonites evolved, many, many millions of years ago, squeezing the gas inside their shell to suddenly sink to get away quickly when they sensed danger. It is what cuttlefish still do today squeezing the gas in their cuttlebone so the cuttlefish becomes denser.

So, if you were basing a marine robot on an ammonite (with movement also possible by undulating its arms, and by jet propulsion, perhaps) then your programming task for controlling its movement would involve it being able to internally squeeze an air space by just the right amount at the right time!

In fact, several groups of researchers have created marine robots based on ammonites. For example, a group at Utah have been doing so to better understand the real but extinct ammonites themselves, including how they did actually move. For example, the team have been testing different shell shapes to see if some shapes work better than others, and so just how efficient ammonite shell shapes actually were. By programming an ammonite robot brain, you could similarly, for example, better understand how they controlled their movement and how effective it really was in practice (not just in theory).

Science can now be done in a completely different way to the traditional version of just using discovery, observation and experiment. You can now do computer and robotic modelling too, running experiments on your creations. If you want to study marine biology, or even fancy being a Palaeontologist with a difference, understanding long extinct life, you can now do it through robotics and computer science, not just by watching animals or digging up fossils (but understanding some physics is still important to get you started).

– Paul Curzon, Queen Mary University of London

More on …

*Thanks to the Dorset Wildlife Trusts at the Chisel Beach Visitor Centre, Portland where I personally learnt about ammonite and cuttlefish propulsion in a really fun science talk on the physics of marine biology, including demonstrating this experiment.

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Ammonite propulsion of underwater robots

Ammonite statue showing creature inside its shell
Image by M W from Pixabay

Intending to make a marine robot that will operate under the ocean? Time to start learning, not just engineering and computing, but the physics of marine biology! And, it turns out you can learn a lot from ammonites: marine creatures that ruled the ocean for millennia and died out while dinosaurs ruled the earth. Perhaps your robot needs a shell, not for protection, but to help it move efficiently.

If you set yourself the task of building an underwater robot, perhaps to work with divers in exploring wrecks or studying marine life, you immediately have to solve a problem that is different to traditional land-based robotics researchers. Most of the really cool videos of the latest robots tend to show how great they are at balancing on two legs, doing some martial art, perhaps, or even gymnastics. Or maybe they are hyping how good they are running through the forest like a wolf, now on four legs. Once you go underwater all that exciting stuff with legs becomes a bit pointless. Now its all about floating not balancing. So what do you do?

The obvious thing perhaps is to just look at boats, submarines and torpedoes and design a propulsion system with propellers, maybe using an AI to design the most efficient propellor shape, then write some fancy software to control it as efficiently as possible. Alternatively, you could look at what the fish do and copy them!

What do fish do? They don’t have propellors! The most obvious thing is they have tails and fins and wiggle a lot. Perhaps your marine robot could be streamlined like a fish and well, swim, its way through the sea. That involves the fish using its muscles to make waves ripple along its body pushing against the water. In exerting a force on the water, by Newton’s Laws, the water pushes back and the fish moves forward.

Of course, your robot is likely to be heavy so will sink. That raises the other problem. Unlike on land, in water you need to be able to move up (and down) too. Being heavy, moving down is easy. But then that is the same for fish. All that fishy muscle is heavier than water so sinks too. Unless they have evolved a way to solve the problem, fish sink to the bottom and have to actively swim upwards if they want to be anywhere else. Some live on the bottom so that is exactly what they want. Maybe your robot is to crawl about on the sea floor too, so that may be right for it too.

Many, many other fish don’t want to be at the bottom. They float without needing to expend any energy to do so. How? They evolved a swim bladder that uses the physics of buoyancy to make them naturally float, neither rising or sinking. They have what is called neutral buoyancy. Perhaps that would be good for your robot too, not least to preserve its batteries for more important things like moving forwards. How do swim bladders do it? They are basically bags of air that give the fish buoyancy – a bit like you wearing a life jacket. Get the amount of air right and the buoyancy, which provides an upward force, can exactly counteract the force of gravity that is pushing your robot down to the depths. The result is the robot just floats under the water where it is. It now has to actively swim if it wants to move down towards the sea floor. So, if you want your robot to do more than crawl around on the bottom, designing in a swim bladder is a good idea.

Perhaps, you can save more energy and simplify things even more though. Perhaps, your robot could learn from ammonites. These are long extinct, dying out with the dinosaurs and now found only as fossils, fearsome predators that evolved a really neat way to move up and down in the water. Ammonites were once believed to be curled up snakes turned to stone, but they were actually molluscs (like snails) and the distinctive spiral structure preserved in fossils was their shell. They didn’t live deep in the spiral though, just in the last chamber at the mouth of the spiral with their multi-armed octopus like body sticking out the end to catch prey. So what were the rest of the chambers for? Filled with liquid or gas, they would act exactly like a swim bladder providing buoyancy control. However, it is likely that, as with the similar modern day nautilus, the ammonite could squeeze the gas or liquid of its spiral shell into a smaller volume, changing its density. Doing that changes its buoyancy: with increased density the buoyancy is less, so gravity exerts a greater force than the lift the shell’s content is giving and it suddenly sinks. Decrease the density by letting the gas or liquid expand and it rises again.

You can see how it works with this simple experiment.

You don’t needs a shell of course, other creatures have evolved more sophisticated versions. A cuttlebone does the same job. It is an internal organ of the cuttlefish (which are not fish but cephalopods like octopus and squid, so related to ammonites). They are the white elongated disks that you find washed up on the beach (especially along the south and west coasts in the UK). They are really hard on one side but slightly softer on the other. They act like an adjustable swim bladder. The hard upper side prevents gas escaping (whilst also adding a layer of armour). The soft lower side is full of microscopic chambers that the cuttlefish can push gas into or pull gas out of at will with the same effect as that of the ammonites shell.

This whole mechanism is essentially how the buoyancy tanks of a submarine work. First used in the original practical submarine, the Nautilus of 1800, they are flooded and emptied to make a submarine sink and rise.

Build the idea of a cuttlebone or ammonite shell into your robot and it can rise and sink at will with minimal energy wasted. Cuttlefish, though, also have another method of propulsion (aside from undulating their body) that allows it to escape from danger in a hurry: jet propulsion. By ejecting water stored in their mantle through their syphon (a tube), they can suddenly give themselves lots of acceleration just like a jet engine gives a plane. That would normally be a very inefficient form of propulsion, using lots of energy. However, experiments show that when used with negative buoyancy such as provided by the cuttlebone, this jet propulsion is actually much more efficient than it would be. So the cuttlebone saves energy again. And a rare ammonite fossil with the preserved muscles of the actual animal suggests that ammonites had similar jet propulsion too. Given some ammonites grew as large as several metres across, that would have been an amazing sight to see!

To be a great robotics engineer, rather than inventing everything from scratch, you could do well to learn from biological physics. Some of the best solutions are already out there and may even be older than the dinosaurs, You might then find your programming task is to program the equivalent of the brain of an ammonite.

– Paul Curzon, Queen Mary University of London

More on …

Thanks to the Dorset Wildlife Trusts at the Chisel Beach Visitor Centre, Portland where I personally learnt about ammonite and cuttlefish propulsion in a really fun science talk on the physics of marine biology.

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Dr Who? Dr You???

Image by Eduard Solà, CC BY-SA 3.0 https://creativecommons.org/licenses/by-sa/3.0, via Wikimedia Commons

When The Doctor in Dr Who knows their time is up – usually because they’ve been injured so badly that they are dying – like all Time Lords, they can regenerate. They transform into a completely different body. They ends up with a new personality, new looks, a new gender, even new teeth. Could humans one day regenerate too?

Your body is constantly regenerating itself too. New cells are born to replace the ones that die. Your hair, nails and skin are always growing and renewing. Every year, you lose and regain so much that you could make a pile of dead cells that would weigh the same as your body. And yet with all this change, every morning you look in the mirror and you look and feel the same. No new personality, no new teeth. How does the human body keep such incredible control?

Here’s another puzzler. Even though our cells are always being renewed, you can’t regrow your arm if it gets cut off. We know it’s not impossible to regrow body parts: we do it for small things like cells, including whole toe nails and some animals like lizards can regrow tails. Why can we regrow some things but not others?

Creation of the shape

All of those questions are part of a field in biology called morphogenesis. The word is from Greek, and it means ‘creation of the shape’. Scientists who study morphogenesis are interested in how cells come together to create bodies. It might sound a long way from computing, but Alan Turing became interested in morphogenesis towards the end of his life. He was interested in finding out about patterns in nature – and patterns were something he knew a lot about as a mathematician. A paper he wrote in 1951 described a way that Turing thought animals could form patterns like stripes and spots on their bodies and in their fur. The mechanisms he described explain how uniform cells could end up turning into different things so not only different patttens in different places, but different body parts in different places. That work is now the foundation of a whole sub-discipline of biology.

Up for the chop

Turing died before he could do much work on morphogenesis, but lots of other scientists have taken up the mantle. One of them is Alejandro Sánchez Alvarado, who was born in Venezuela but works at the Stowers Institute for Medical Research in Kansas City, in the US. He is trying to get to the bottom of questions like how we regenerate our bodies. He thinks that some of the clues could come from working on flatworms that can regenerate almost any part of their body. A particular flatworm, called Schmidtea mediterranea, can regenerate its head and its reproductive organs. You can chop its body into almost 280 pieces and it will still regenerate.

A genetic mystery

The funny thing is, flatworms and humans aren’t as different as you might think. They have about the same number of genes as us, even though we’re so much bigger and seemingly more complicated. Even their genes and ours are mostly the same. All animals share a lot of the same, ancient genetic material. The difference seems to come from what we do with it. The good news there is that as the genes are mostly the same, if scientists can figure out how flatworm morphogenesis works, there’s a good chance that it will tell us something about humans too.

One gene does it all

Alejandro Sánchez Alvarado did one series of experiments on flatworms where he cut off their heads and watched them regenerate. He found that the process looked pretty similar to watching organs like lungs and kidneys grow in humans as well as other animals. He also found that there was a particular gene that, when knocked out, takes away the flatworm’s ability to regenerate.

What’s more, he tried again in other flatworms that can’t normally regenerate whole body parts – just cells, like us. Knocking out that gene made their organs, well, fall apart. That meant that the organs that fell apart would ordinarily have been kept together by regrowing cells, and that the same gene that allows for cell renewal in some flatworms takes care of regrowing whole bodies, Dr Who-style, in others. Phew. A lot of jobs for one gene.

Who knows, maybe Time Lords and humans share that same gene too. They’re like the lucky, regenerating flatworms and we’re the ones who are only just keeping things together. But if it’s any consolation, at least we know that our bodies are constantly working hard to keep us renewed. We still regenerate, just in a slightly less spectacular way.

– the CS4FN team (updated from the archive)

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

How did the zebra get its stripes?

Head of a fish with a distinctive stripy, spotty pattern
Image by geraldrose from Pixabay

There are many myths and stories about how different animals gained their distinctive patterns. In 1901, Rudyard Kipling wrote a “Just So Story” about how the leopard got its spots, for example. The myths are older than that though, such as a story told by the San people of Namibia (and others) of how the zebra got its stripes – during a fight with a baboon as a result of staggering through the baboon’s fire. These are just stories. It was a legendary computer scientist and mathematician, who was also interested in biology and chemistry, who worked out the actual way it happens.

Alan Turing is one of the most important figures in Computer Science having made monumental contributions to the subject, including what is now called the Turing Machine (giving a model of what a computer might be before they existed) and the Turing Test (kick-starting the field of Artificial Intelligence). Towards the end of his life, in the 1950s, he also made a major contribution to Biology. He came up with a mechanism that he believed could explain the stripy and spotty patterns of animals. He has largely been proved right. As a result those patterns are now called Turing Patterns. It is now the inspiration for a whole area of mathematical biology.

How animals come to have different patterns has long been a mystery. All sorts of animals from fish to butterflies have them though. How do different zebra cells “know” they ultimately need to develop into either black ones or white ones, in a consistent way so that stripes (not spots or no pattern at all) result, whereas leopard cells “know” they must grow into a creature with spots. They both start from similar groups of uniform cells without stripes or spots. How do some that end up in one place “know” to turn black and others ending up in another place “know” to turn white in such a consistent way?

There must be some physical process going on that makes it happen so that as cells multiply, the right ones grow or release pigments in the right places to give the right pattern for that animal. If there was no such process, animals would either have uniform colours or totally random patterns.

Mathematicians have always been interested in patterns. It is what maths is actually all about. And Alan Turing was a mathematician. However, he was a mathematician interested in computation, and he realised the stripy, spotty problem could be thought of as a computational kind of problem. Now we use computers to simulate all sorts or real phenomena, from the weather to how the universe formed, and in doing so we are thinking in the same kind of way. In doing this, we are turning a real, physical process into a virtual, computational one underpinned by maths. If the simulation gets it right then this gives evidence that our understanding of the process is accurate. This way of thinking has given us a whole new way to do science, as well as of thinking more generally (so a new kind of philosophy) and it starts with Alan Turing.

Back to stripes and spots. Turing realised it might all be explained by Chemistry and the processes that resulted from it. Thinking computationally he saw that you would get different patterns from the way chemicals react as they spread out (diffuse). He then worked out the mathematical equations that described those processes and suggested how computers could be used to explore the ideas.

Diffusion is just a way by which chemicals spread out. Imagine dropping some black ink onto some blotting paper. It starts as a drop in the middle, but gradually the black spreads out in an increasing circle until there is not enough to spread further. The expanding circle stops. Now, suppose that instead of just ink we have a chemical (let’s call it BLACK, after its colour), that as it spreads it also creates more of itself. Now, BLACK will gradually uniformly spread out everywhere. So far, so expected. You would not expect spots or stripes to appear!

Next, however, let’s consider what Turing thought about. What happens if that chemical BLACK produces another chemical WHITE as well as more BLACK? Now, starting with a drop of BLACK, as it spreads out, it creates both more BLACK to spread further, but also WHITE chemicals as well. Gradually they both spread. If the chemicals don’t interact then you would end up with BLACK and WHITE mixed everywhere in a uniform way leading to a uniform greyness. Again no spots or stripes. Having patterns appear still seems to be a mystery.

However, suppose instead that the presence of the WHITE chemical actually stops BLACK creating more of itself in that region. Anywhere WHITE becomes concentrated gets to stays WHITE. If WHITE spreads (ie diffuses) faster than BLACK then it spreads to places first that become WHITE with BLACK suppressed there. However, no new BLACK leads to no more new WHITE to spread further. Where there is already BLACK, however, it continue to create more BLACK leading to areas that become solid BLACK. Over time they spread around and beyond the white areas that stopped spreading and also create new WHITE that again spreads faster. The result is a pattern. What kind of pattern depends on the speed of the chemical reactions and how quickly each chemical diffuses, but where those are the same because it is the same chemicals the same kind of pattern will result: zebras will end up with stripes and leopards with spots.

This is now called a Turing pattern and the process is called a reaction-diffusion system. It gives a way that patterns can emerge from uniformity. It doesn’t just apply to chemicals spreading but to cells multiplying and creating different proteins. Detailed studies have shown it is the mechanism in play in a variety of animals that leads to their patterns. It also, as Alan Turing suggested, provides a basis to explain the way the different shapes of animals develop despite starting from identical cells. This is called morphogenesis. Reaction-diffusion systems have also been suggested as the mechanism behind how other things occur in the natural world, such as how fingerprints develop. Despite being ignored for decades, Turing’s theory now provides a foundation for the idea of mathematical biology. It has spawned a whole new discipline within biology, showing how maths and computation can support our understanding of the natural world. Not something that the writers of all those myths and stories ever managed.

– Paul Curzon, Queen Mary University of London

More on …

Magazines …

Front cover of CS4FN issue 29 - Diversity in Computing

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Join the crowd with swarm intelligence

A shoal of fish crammed into a cylindrical tank.
Image by Paul Sloane from Pixabay

Next time you are in a large crowd, look around you: all those people moving together, and mostly not bumping into each other. How does it happen? Flocks of birds and schools of fish are also examples of this ‘swarm intelligence’. Computer Scientists have been inspired by this behaviour to come up with new solutions to really difficult problems.

Swarming behaviour requires the individuals (birds, fish or people) to have a set of rules about how to interact with the individuals nearest to them. These so-called ‘local’ rules are all that’s needed to give rise to the overall or ‘global’ behaviour of the swarm. We adjust our individual behaviour according to our current state but also the current state of those around us. If I want to turn left then I do it slowly so that others in the crowd can be aware of it and also start to turn. I know what I am doing and I know what they are doing. This is how information makes its way from the edges of the crowd to the centre and vice versa.

A swarm is born

The way a crowd or swarm interacts can be explained with simple maths. This maths is a way of approximating the complex psychological behaviour of all the individuals on the basis of local and global rules. Back in 1995 James Kennedy, a research psychologist, and Computer Scientist Russ Eberhart, having been inspired by the study of bird flocking behaviour by biologist Frank Heppner, realised that this swarm intelligence could be used to solve difficult computer problems. The result was a technique called Particle Swarm Optimisation (PSO).

Travel broadens the mind

An optimisation problem is one where you have a range of options to choose from and you want to know the best solution. One of the classic problems is called ‘The travelling salesperson’ problem. You work for a company and have to deliver packages to say 12 towns. You look at the map. There are many different routes to take, but which is the one that will let you visit all 12 towns using the least petrol? Here the choices are the order in which you visit the towns, and the constraint is that you want to do the least driving. You could have a guess, select the towns in a random order and work out how far you’d have to travel to visit them in this order. You then try another route through all 12 and see if it takes less mileage, and so on. Phew! It could take a long time to work out all the possible routes for 12 towns to see which was best. Now imagine your company grows and you have to deliver to 120 towns or 1200 towns. You would spend all your time with the maps trying to come up with the cheapest solutions. There must be a better way? Well actually simple as this problem seems it’s an example of a set of computational problems known as NP-Complete problems and it’s not easy to solve! You need some guidance to help you through and that’s where swarm optimisation come in. It’s an example of a so-called metaheuristic algorithm: a sort of ‘general rule of thumb’ to help solve these types of problem. It won’t always work unless you have infinite time but it’s better than just trying random solutions. So how does swarm optimisation work here?

State space: the final frontier

First we need to turn the problem into something called a state space. You probably use state spaces all the time but just don’t know it. Think about yourself. What are the characteristic you would use to tell people about your current state: age, height, weight and so on. You can identify yourself by a list of say 3 numbers – one for age, one for height, one for weight. It’s not everything about you of course but it does define your state to some extent. Your numbers will be different to other people’s numbers, if you take all the numbers for your friends you would have a state space. It would be a 3-dimensional space with axes: age, height and weight, and each person would be a point in that space at some coordinate (X, Y, Z).

So state spaces are just a way of representing the possible variations in some problem. With the 12 towns problem, however, you couldn’t draw this space: it would be 12 dimensional! It would have one axis for each town, with the position on the axis an indication of where in the route it was. Every point in that space would be a different route through the 12 towns, so each point in the space would have coordinates (x1, x2, x3, … x11, x12). For each point there would also be a mileage associated with the route, and the task is to find the coordinate point (route) with the lowest mileage.

Where no particle has swarmed before

Enter swarm optimisation. We create a set of ‘particles’ that will be like birds or fish, and will fly and swarm through our state space. Each particle starts with a random starting location in the state space and calculates the mileages involved for the coordinates (route) they are at. The particles remember (store) this coordinate and also the value of the mileage at that position. Each particle therefore has it’s own known ‘local’ best value (where the lowest mileage was) but can compare this with other neighbouring particles to see if they have found any even better solutions. The particles then move onwards randomly in a direction that tends to move them towards their own local best and the best value found by their neighbours. The particles ‘fly’ around the state space in a swarm homing in on even better solutions until they all converge on the best they can find: the answer.

It may be that somewhere in a part of the space where no particle has been there is an even better solution, perhaps even the best solution possible. Our swarm will have missed it! That’s why this algorithm is a heuristic, a best guess to a tough problem. We can always add some more particles at the start to fill more of the state space and reduce the chance of missing a good solution, but we cant ever be 100% sure.

Swarm optimisation has been applied to a whole range of tough problems in computing, electronic engineering, medicinal chemistry and economics. All it needs is for you to create an appropriate state space for your problem and let the particles fly and swarm to a good solution.

It’s yet another example of clever computing based on behaviours found in the natural world. So next time you’re in a crowd, look around and appreciate all that collective interacting swarm intelligence…but make sure you remember to watch where you are stepping.

by Peter W. McOwan, Queen Mary University of London. From the archive.

More on …

Related Magazines …

cs4fn issue 4 cover
A hoverfly on a leaf

Our Books …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Gutta-Percha: how a tree launched a global telecom revolution

CS4FN Banner

by Paul Curzon, Queen Mary University of London

(from the archive)

Rubber tree being tapped
Image  from Pixabay

Obscure plants and animals can turn out to be surprisingly useful. The current mass extinction of animal and plant species needs to be stopped for lots of reasons but an obvious one is that we risk losing forever materials that could transform our lives. Gutta-percha is a good example from the 19th century. It provided a new material with uses ranging from electronic engineering to bioengineering. It even transformed the game of golf. Perhaps its greatest claim to fame though is that it kick-started the worldwide telecoms boom of the 19th century that ultimately led to the creation of global networks including the Internet.

Gutta-percha trees are native to South East Asia and Australia. Their sap is similar to rubber. It’s actually a natural polymer: a kind of material made of gigantic molecules built up of smaller structures that are repeated over and over again. Plastics, amber, silk, rubber and wool are all made of polymers. Though very similar to it, unlike rubber, Gutta-percha is biologically inert – it doesn’t react with biological materials – and that was the key to its usefulness. It was discovered by Western explorers in the middle of the 17th century, though local Malay people already knew about it and used it.

Chomping wires

So how did it play a part in creating the first global telecom network? Back in the 19th century, the telegraph was revolutionising the way people communicated. It meant messages could be sent across the country in minutes. The trouble was when the messages got to the coast they ground to a halt. Messages could only travel across an ocean as fast as a boat could take them. They could whiz from one end of America to the other in minutes but would then take several weeks to make it to Europe. The solution was to lay down undersea telegraph cables. However, to carry electricity an undersea cable needs to be protected and no one had succeeded in doing that. Rubber had been tried as an insulating layer for the cables but marine animals and plants just attacked it, and once the cable was open to the sea it became useless for sending signals. Gutta-percha on the other hand is a great insulator too but it doesn’t degrade in sea-water.

As it was the only known material that worked, soon all marine cable used Gutta-percha and as a result the British businessmen who controlled its supply became very rich. Soon telegraph cables were being laid everywhere – the original global telecoms network. To start with the network carried telegraph signals then was upgraded to voice and now is based on fibre-optics – the backbone of the Internet.

Rotting teeth

Gutta-percha has also been used by dentists – just as marine animals don’t attack it, it doesn’t degrade inside the human body either. That together with it being easy to shape makes it perfect for dental work. For example, it is used in root canal operations. The pulp and other tissue deep inside a rotting tooth are removed by the dentist leaving an empty chamber. Gutta-percha turns out to be an ideal material to fill the space, though medical engineers and materials scientists are trying to develop synthetic materials like Gutta-percha, but that have even better properties for use in medicine and dentistry.

Dimpled balls

That just leaves golf! Early golf balls were filled with feathers. In 1848 Robert Adams Paterson came up with the idea of making them out of Gutta-percha since it was much easier to make than the laborious process of sewing balls of feathers. It was quickly realised, if by accident, that after they had been used a few times they would fly further. It turned out this was due to the dimples that were made in the balls each time they were hit. The dimples improved the aerodynamics of the ball. That’s why modern golf balls are intentionally covered in dimples.

So gutta-percha has revolutionised global communications, changed the game of golf and even helped people with rotting teeth. Not bad for a tree.

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded through EPSRC grant EP/W033615/1.

Even the dolphins use pocket switched networks!

(from the archive)

Dolphin leaping in waves off Panama City
Image by Heather Williams from Pixabay

Email, texting, Instant Messaging, Instant response…one of the things about modern telecoms is that they fuel our desire to “talk” to people anytime, anywhere, instantly. The old kind of mail is dismissed as “snail mail”. A slow network is a frustrating network. So why would anyone be remotely interested in doing research into slow networks? Surprisingly, slow networks deserve study. Professor Jon Crowcroft of the University of Cambridge and his team were early researchers of this area, and this kind of network could be the network of the future. The idea is already being used by the dolphins (not so surprising I suppose given according to Douglas Adams’ “The HitchHiker’s Guide to the Galaxy” they are the second most intelligent species on Earth…after the mice).

From node to node

Traditional networks rely on having lots of fixed network “nodes” with lots of fast links between them. These network nodes are just the computers that pass on the messages from one to the other until the messages reach their destinations. If one computer in the network fails, it doesn’t matter too much because there are enough connections for the messages to be sent a different way.

There are some situations where it is impractical to set up a network like this though: in outer space for example. The distances are so far that messages will take a long time – even light can only go so fast! Places like the Arctic Circle are another problem: vast areas with few people. Similarly, it’s a problem under the sea. Signals don’t carry very well through water so messages, if they arrive at all, can be muddled. After major disasters like Hurricane Katrina or a Tsunami there are also likely to be problems.

It is because of situations like these that computer scientists started thinking about “DNTs”. The acronym can mean several similar things: Delay Tolerant Networks (like in space the network needs to cope with everything being slow), Disruption Tolerant Networks (like in the deep sea where the links may come and go) or Disaster tolerant networks (like a Tsunami where lots of the network goes down at once). To design networks that work well in these situations you need to think in a different way. When you also take into account that computers have gone mobile – they no longer just sit on desks but are in our pockets or handbags, this leads to the idea of a “ferrying network” or as Jon Crowcroft calls them: “Pocket Switched Network”. The idea is to use the moving pocket computers to make up a completely new kind of network, where some of the time messages move around because the computers carrying them are moving themselves, not because the message itself is moving. As they move around they pass near other computers and can exchange messages, carrying a message on for someone else until it is near another computer it can jump to.

From Skidoo to you

A skiddo with driver standing next to it
Image by raul olave from Pixabay

How might such networks be useful in reality? Well one was set up for the reindeer farmers in the Arctic Circle. They roam vast icy wastelands on skidoos, following their reindeer. They are very isolated. There are no cell phone masts or internet nodes and for long periods they do not meet other people at all. The area is also too large to set up a traditional network cheaply. How could they communicate with others?

They set up a form of pocket switched network. Each carried a laptop on their skidoo. A series of computers were also set up sitting in tarns spread around the icy landscape. When the reindeer farmers using the network want a service, like delivering a message, the laptop stores the request until they pass within range of one of the other computers perhaps on someone else’s skidoo. The computer then automatically passes the message on. The new laptop takes the message with it and might later pass a tarn, where the message hops again then waits till someone else passes by heading in the right direction. Eventually it makes a hop to a computer that passes within range of a network point connected to the Internet. It may take a while but the mail eventually gets through – and much faster than waiting for the farmer to be back in net contact directly.

Chatting with Dolphins

Even the dolphins got in on the act. US scientists wanted to monitor coastal water quality. They hit on the idea of strapping sensors onto dolphins that measure the quality wherever they go. Only problem is dolphins spend a lot of time in deep ocean where the results can’t easily be sent back. The solution? Give them a normal (well dolphin adapted) cell phone. Their phone stores the results until it is in range of their service provider off the coast. By putting a receiver in the bays the dolphins return to most frequently, they can call home to pass on the data whenever there.

The researchers encountered an unexpected problem though. The dolphin’s memory cards kept inexplicably filling up. Eventually they realised this was because the dolphins kept taking trips across the Atlantic where they came in range of the European cell networks. The European telecom companies, being a friendly bunch, sent lots of text messages welcoming these newly appeared phones to their network. The memory cards were being clogged up with “Hellos”!

The Cambridge team investigated how similar networks might best be set up and used for people on the move, even in busy urban environments. To this end they designed a pocket switched network called Haggle. Using networks like Haggle, it is possible to have peer-to-peer style networks that side-step the commercial networks. If enough people join in then messages can just hop from phone to phone, using bluetooth links say, as they passed near each other. They might eventually get to the destination without using any long distance carriers at all.

The more the merrier

With a normal network, as more people join the network it clogs up as they all try to use the same links to send messages at the same time. Some fundamental theoretical results have shown that with a pocket switched network, the capacity of the network can actually go up as more people join – because of the way the movement of the people constantly make new links.

Pocket switched networks are a bit like gases – the nodes of the network are like gas molecules constantly moving around. A traditional network is like a solid – all the molecules, and so nodes, are stationary. As more people join a gaseous network it becomes more like a liquid, with nodes still moving but bumping into other nodes more often. The Cambridge team explored the benefits of networks that can automatically adapt in this way to fit the circumstances: making phase transitions just like water boiling or freezing.

One of the important things to understand to design such a network is how people pass others during a typical day. Are all people the same when it comes to how many people they meet in a day? Or are there some people that are much more valuable as carriers of messages. If so those are the people the messages need to get to to get to the destination the fastest!

To get some hard data Jon and his students handed out phones. In one study a student handed out adapted phones at random on a Hong Kong street, asking that they be returned a fixed time later. The phones recorded how often they “met” each other before being returned. In another similar experiment the phones were given out to a large number of Cambridge students to track their interactions. This and other research shows that to make a pocket switched network work well, there are some special people you need to get the messages to! Some people meet the same people over and over, and very few others. They are “cliquey” people. Other more “special” people regularly cross between cliques – the ideal people to take messages across groups. Social Anthropology results suggest there are also some unusual people who rather than just networking with a few people, have thousands of contacts. Again those people would become important message carriers.

So the dolphins may have been the “early adopters” of pocket switched networks but humans may follow. If we were to fully adopt them it could completely change the way the telecom industry works…and if we (or the dolphins) ever do decide to head en-mass for the far reaches of the solar system, pocket switched networks like Haggle will really come into their own.

– Paul Curzon, QMUL, based on a talk given by Jon Crowcroft at Queen Mary in Jan 2007.

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded through EPSRC grant EP/W033615/1.

Naked Mole-Rats Go Digital – monitoring colonies remotely (while respecting their privacy)

A naked mole-rat with a privacy bar over its eyes
A naked mole rat. Respecting animals’ privacy can keep them safe too.
Image. © Lorna Ellen Faulkes and Julie Freeman provided by Julie Freeman for the article

Where does a naked mole-rat wear its computing gadgetry? Under its skin….

Naked mole-rats are fascinating creatures. They are highly social, living in colonies. They spend their lives permanently underground in burrows, and that’s why they have no fur just whiskers. They don’t need it. Living underground means they are difficult to study. Normally researchers simply watch animals to study their behaviour, but that’s not possible for naked mole-rats.

Tag ’em

To allow them to be observed, one colony of 28 animals, called Colony Omega, went digital. They all have an implant under their skin. These tags are just smaller versions of ones used by vets to tag pets. Sensors around their burrow detect when the tags are close. This means the naked mole-rats can be watched in real-time as they move around the burrow. It’s allowing the biologists to study patterns in their behaviour such as how different animals take on different roles in the colony.

Interactive rat art

Julie Freeman, an artist and computer scientist at QMUL, used the same data in a different way. She leads a team creating interactive art based on the naked mole-rat data. ‘A Selfless Society‘, for example, is an abstract animation that changes as a result of the live data from the colony. The sculpture ‘This is Nature Now‘ also represents the live data from the colony but using soft robotic techniques (see page 13 of the magazine linked below). It moves based on the movements of the naked mole-rats. We often experience nature through technology, watching it on screens rather than in real-life. ‘This is Nature Now’ explores how physical, non-living objects can convey a sense of life.

Private portraits

Colony Omega also has its own gallery of portrait photos, taken by Lorna Ellen Faulkes. The eyes of the naked mole-rats are blocked out (to protect their identity!) The idea is to make people think about data privacy. Technology raises big issues over our own privacy. We now give away vasts amount of personal information without realising. What about the data privacy of animals?

This may seem silly, but is a very real problem. Tourists posting images of endangered animals and plants on social media from safaris has caused problems. It has led poachers to the animals and plants photographed, putting them in serious danger. The problem arises because modern digital cameras log the place a photo is taken, and this ‘metadata’ is included with the photograph posted for anyone to see who knows where to look.

Find out more about Colony Omega and see the art at rat.systems/colony/

– Paul Curzon, Queen Mary University of London

Related Magazine …

This article was originally published on the CS4FN website and a copy can also be found on page 6 of Issue 25 of CS4FN, “Technology worn out (and about)“, on wearable computing, which can be downloaded as a PDF, along with all our other free material, here: https://cs4fndownloads.wordpress.com/  

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos