Skip navigation

Category Archives: Computing

What do bacteria, snowflakes and robots have in common?

Whoa… been a while since I dropped some words on this thing!

So a few exciting things have happened recently in nerd land for me: The research I conducted for my honours thesis last year was adapted into a short paper and accepted for the PPSN conference in Italy this September. Also, some text books and software I developed for Monash Uni were recently released – more on that another time.

So if you’re into robots, and also cool natural phenomenon like swarms of insects and the way in which snowflakes are formed, read on…

 

Photo courtesy http://www.flickr.com/photos/yellowcloud

 

Essentially we produced a navigation system for robot swarms that allows a dispersed group of agents in an unknown environment to find their way back to a charging station (or any other pre-determined point of interest for that matter). It does so without the agents needing to know the topography of their environment, removing the need for complex mapping / GPS equipment.

When one of our little computerised friends decides it’s time to hit the nest for some R&R, its buddies form a structure of beacons resembling a snowflake, with the charging station at the centre. The robot then traverses the structure towards the charging station, at which point the rest of the swarm can get back to work.

The collective navigation strategy uses only simple audio signals and basic behaviours based on the foraging behaviour of bacteria, meaning that the individual agents can be made on the cheap. Cost is important when it comes time to manufacture a bucket load of them. .If you’re interested, you should definitely check out this website, which summarises the end product of our research. There’s a cool video which shows it in action too.

 

Swarm Robots - Photograph by Peter Essick

 

Does the thought of a robot swarm scare you? If so, you’re not alone. I’m sometimes asked what I think about the prospect of robots taking over the world, and if I feel I’ve contributed to our inevitable demise.

The answer is no.

People tend to project their fear of other humans onto the humble robot. Let’s not forget that a robot is just a computer – a stupid machine incapable of thought, opinion or prejudice. It might have some wheels and something that resembles appendage, but it’s a stupid machine nonetheless.

People aren’t really afraid of the robot – they’re afraid of which human gets to control the robot.

Sounds like a good reason to learn computer programming, don’t ya think? :-)

Your spelling it wrong

For a bit of a laugh, I made a Twitter bot today. Not just any old bot, it’s a crime fighting bot bringing your criminals to justice.

What’s a your criminal? You know, people who don’t know when to use “you’re” instead of “your”.

The idea was inspired by the athiest bot, which cracked me up when I first saw it. I made this one using the python-twitter wrapper, and it’s surprisingly easy to get a simple little automated Twitter thingy happening.

Basically, it searches for people misspelling “you’re”, then retweets their crime with a friendly suggestion of how they should spell it. Here’s some of the tweets it generated before the account was suspended for unsolicited tweeting :P

Maze makin’ cat

The software I’m currently working on is a mod for the very popular animation-creating tool called Scratch, developed by MIT. Our mod, tentatively named Cellular, extends the capabilities of Scratch by allowing the sprites to not just interact with each other, but also the environment beneath them.

The environment (known as the stage in Scratch), is divided up into cells that can have attributes assigned to them, which can then be read from and written to by the sprites as they move about.

Here’s an example of what can be achieved with Cellular…

Maze Cat

So what’s happening here? Well, the cat is creating a maze using a well known algorithm based on a depth-first search. In brief, the algorithm goes:

  • Mark all cells as unvisited, and place the cat in a random cell, which will be the exit.
  • Get a list of neighbour cells, and for each neighbour, starting with a randomly selected one:
    • Move to the chosen cell and remove the wall separating the two
    • Recurse the algorithm, using the new as the current cell
    • Move back to the previous cell

The cat will eventually fill all available space on the stage with paths, and an entry to the maze can be chosen at will (obviously a good choice of entry will be suitably far from the exit).

There’s guaranteed to be only one correct path out of the maze, as the algorithm will neven create any loops or circuits.

What I find particularly cool about maze generation algorithms is that they expose students to the concept of recursion in a fun and practical way. Also, maze generators are typically just modified search algorithms, which form part of the fundamentals of Computer Science education.