Minos 2009

The weekend followed its customary pattern with the Saturday consisting of a number of presentations from members of the community and Sunday giving an opportunity for folk to compete in the friendly, but earnest, competition session. The rest of this post has a summary of each speaker’s session and a link to the slides and other media where available.

The Saturday programme looked like this:

 

David Otten	Inertial Navigation, Timing systems and half-size mice
Duncan Louttit	Weightless Communications
Derek Hall	Maze solving without numbers
Martin Barret	Infra Red sensors
Martyn Pittuck	Adaptive Control
David Hannaford	Flooding Algorithms
Pete Harrison	Fast Flooding and solving for diagonals
Garry Bulmer	Spreading the Word
Ken Hewitt	The Parallax Propeller
Alan Dibley	Solving diagonals with ternary arithmetic
Rob Probin Alan Henness	Vision guided mouse update

 

David Otten: Inertial Navigation, Timing systems and half-size mice

David Otten’s most recent mouse – MITEE 11 – has two accelerometers and a gyroscope mounted on it to permit better control of the mouse during both rectilinear and rotational movement. It turns out these are not so simple to make use of. Noise, drift and unforeseen coupling effects make using the information these sensors provide quite complex. Davit has previously reported on his efforts to use the accelerometers for the control of straight acceleration and deceleration. Some progress has been made in this area. There are a couple of interesting side-effect however. The first, seen in in the video linked below, is a tendency for the mouse to rock in place when commanded to stand still. the exact cause of this behaviour is not clear. By contrast, the rotational control is very stiff. In the video, you can see the result of trying to make the mouse rotate. The result is that the mouse will allow the tyres to slip and the mouse to slide sideways rather than permit any rotation.

Following his visit to the 2008 All-Japan competition, David also showed some video taken from the three main events. The line follower contest clearly had a route that rather exceeded the expectations of the audience if the gasps are any guide. While very fast, it looks like there is still some way to go before these robots are at the limits of their performance. the half-size maze contest also had a surprise in store for those like me who had not paid attention to the rules. It seems that the maze is nor 32×32 cells and the goal can be in any cell. the contestants put in remarkably good performances. The difficulty in building a narrow enough mouse means there are not too many diagonal runners. It doesn’t look like we will see any six wheel mice at this scale either. The full-size contest was full of the usual tension with Ng Beng Kiat regaining his title after slipping a little last year.

With so many more mice performing very well and close to the limits of what might be possible, David decided it was time to add electronic scoring to the APEC contest that he runs in the US. After considering the alternatives, David decided to go with a radio-linked timing gate with the electronics buried in one of the walls. Reflective sensors look out through the end of the wall and the attached post. Completely self-contained, these gates can be placed anywhere in the maze and the battery is good for 4-5 hours continuous use.

The receiver unit is self-contained and records all the timing information on-board. This approach means it can act independently of any attached PC. The receiver is also capable of driving a video display.

Media:
  Slides
Inertial Control
Line follower contest
Half size micromouse
Full size micromouse

 

Duncan Louttit: Weightless Communications

Watching your mouse wander around the maze can be a tense time. Onlookers frequently ask what it is doing or why it did this or that. The poor owner looks on bemused. They should know right? But it is never that easy and the response is likely to be a shrug of the shoulders and a wistful ‘if only I knew…’.

One help for this dilemma is telemetry. Have your mouse continually update a PC with information about what it is up to. Not many mice do this. Generally that is because it is perceived as complex and/or cumbersome. After all, you don’t want to weigh down your mouse with extra circuitry and transmitters.

Duncan has come up with a typically innovative solution to the problem. Most mice already have quite good transmitters on board – the emitters for the wall sensors. These are usually high-powered IR or visible light LEDs pointing at a diffuse white surface. Furthermore, they are not being used most of the time. Any given emitter is likely to be turned on for only a few microseconds every millisecond or so. Well, why not use that period to send serial data modulated on the LEDs?

After explaining why conventional detectors like TV remote control detectors were not suited to the task, Duncan described a soft UART generating FSK data on a 160kHz carrier. The transmitter side is quite straightforward. The receiver is a little more challenging and is effectively a software FSK demodulator built using an AVR processor which sends on its data as standard RS232 signals to a data logger or PC for display.

The system adds telemetry to your mouse or small robot without adding any more components by using what is already there.

Media:
Slides

 

Derek Hall: Maze solving without numbers

Almost universally, maze solving for micromouse is done by flooding the maze. You can see this process described a little further down in the talks by David Hannaford and Pete Harrison.

Derek hall uses a fundamentally different approach. His early mice made good use of the limited resources available on an 8051 derived processor. These have very little RAM but very good bit manipulation instructions. Consequently, Derek derived a much simplified form of the standard flood. In this technique, rather than put a number in each cell to indicate how far it is from the goal, a single bit is used.

When the mouse needs to know where to move to next the solver is run. The map starts off with all the cells filled with zeros and a single bit is set in the target cell(s). Next, the algorithm runs through the maze and, on each pass, marks with a one the cells that are next to a cell that already has a one. The filled cells spread out from the target until there is a marked cell adjacent to the mouse position. At this point, the mouse moves to that square and the process is repeated. The technique works because, at any given time, this mouse merely needs to know which cell to visit next.

The method has its limitations. In particular, it is not very convenient for identifying whether the maze is solved or for generating a path for the mouse to follow when the maze is solved.  The next version of Derek’s solver uses a couple of bits per cell to store one of four directions. These directions can be thought of as arrows pointing to the next cell to take on the way to the target. With this technique, a single flood of the maze can furnish information the mouse can use from any position to find it way to the current target. Following the arrows will generate a shortest route for the mouse to follow.

Unless your mouse can run diagonals, the best route may not be the shortest one but the straightest. A small enhancement to the direct field method makes sure that, when directions are added to the map, preference is given to directions that will allow the mouse to carry on in a straight line.

 

Martin Barratt: Infra Red Reflective Sensors.

Martin treated us to a review of some of the relevant and critical features of IR reflective sensors. His observations are equally valid for visible light reflective sensors. This type of sensor is now almost universally used on maze solvers. Their chief advantage is that they permit much higher performance as the mass and rotational inertia are greatly reduced.

While the mode of operation of typical reflective sensors is well enough understood, the specifics of choosing components and component values in the circuits used are often overlooked. Martin gave good advice about selecting pulse lengths and duty cycles along with current limiting resistors and reservoir capacitors in the emitter circuit. Careful consideration was given to the need to avoid noise in the supply lines and the effect of emitter induced noise on the results from the detector was also examined.

The detector circuit, although superficially straightforward, also needs some care in its design if maximum signal-to-noise and sensitivity are to be achieved.

Careful examination of the information in these slides should be compulsory for anyone designing reflective sensors not only for a micromouse but also for any similar application.

Media:
slides

 

Martyn Pittuck: Adaptive Control

Martin has made micromouse the core of his studies into control systems. His current mouse is a multi-processor device with some very fancy control techniques. A high-performance mouse is constantly on the edge of losing control – chiefly by losing traction. Martyn has been looking at the possibility of detecting any skid/slide and compensating for it in the dynamics of his controller.

When turning, mice generally follow a circular path. Transitioning from straight to circular can be complicated. It is not safe, for example, to simply change the wheel speeds instantaneously. To do so puts large forces through the tyres and loss of traction is almost inevitable.

Rather than use a circular path, Martyn has chosen to have his mouse follow a Bezier curve. Such a curve can satisfy all the requirements of an arbitrary turn and has the great advantage that it is controlled by a small number of parameters – four coordinate pairs are sufficient although a single value, lambda, can be used for symmetrical turns. The parameters control the entry and exit points as well as the radius of curvature at any point around the turn. Once your have the basic parameters, the characteristics of a turn can be adjusted according to how well the mouse is doing. Thus, a mouse might speed up and tighten its turns until slip is detected and then back off a little for a safety margin. Constant monitoring would allow the optimum values to be changes on the fly.

Calculating the various profiles is nit simple and involves some moderately serious maths but the rewards are potentially worth the effort.

Media:

 

David Hannaford: Flooding algorithms

Solving a micromouse maze is an example of a whole class of problems with similar solutions. Essentially the same technique can, for example, be used to route printed circuit boards, guide a vacuum cleaner robot around your house or send autonomous enemy units after you in a computer game.

David presented the essentials of the methods most commonly used by typical micromouse robots. Here the maze map is stored as an array with a number for each location. The locations corresponding to the goal are given a value zero and the algorithm works through the map in a series of passes. On each pass, cells adjacent to already flooded cells are given a value that is one more than their neighbour. In this way, the map is gradually filled with numbers representing, for each cell, the distance from it to the goal.

Once the map has been flooded, the mouse can find its way from any cell to the goal by creating a path that follows the numbers ‘downhill’. That is, in any given cell, the mouse, or the pathfinder, simply looks for the smallest connected neighbour and adds that cell to the path.

The basic method is quite slow and exhaustive if applied frequently so a number of improvements can be made. David’s mouse uses one of these improved methods, described in the next session, with a PIC 18F252 and achieves very good solving speeds.

Media:
  Slides

 

Peter Harrison: Fast maze flooding techniques

The basic maze flood is quite a simple task. However, a naive application of the algorithm can result in a lot of wasted processor time. While it is not, by any means necessary to flood the maze at every cell or even at every junction, it may be beneficial to do so. With the mouse moving, any time taken in solving the maze means it is important not to overshoot critical decision points. That means either solving the maze more quickly or moving more slowly. Slower means a lower score so faster solving is a good thing.

With a simple implementation, the map is processed in a number of passes. On each pass, the frontier of the flooded area gradually moves out from the goal. It can take many passes (250 or so in the worst case) to fully flood the maze and each pass means processing all 256 cells in the map.

A much better technique is to only process those cell that are on the frontier and to ensure that each cell is processed only once. To do this we start with the cells adjacent to the goal and place them in a queue. Flooding the map is then a question of processing the queue. Cells at the head are these awaiting processing. Each such cell has its distance calculated and its neighbours are added to the tail. Care is taken to ensure that no cell is added twice. Every cell is processed once only. The performance improvements are marked. With this technique a typical maze (Japan 2007) can be solved in under two milliseconds using only 61 words or program memory on a dsPIC30f4011 at 8Mips.

Media:
  Slides

 

Garry Bulmer: Spreading the word

Garry has been working recently to help out local schools with the uptake of electronics, robotics and microcontrollers. His weapon of choice on the microcontroller side is the Arduino, an open source device based upon the AVR processor. The arduino really shows us all how a simple to use but very capable controller should be put together.

Media:

 

Ken Hewitt: the Parallax Propeller

Some time ago, I saw an article describing the Parallax Propeller chip. I read through the whole thing with a growing sense of astonishment. This thing was brilliant! Then I noticed that the cover date for the magazine was April and decided I had been taken in by a great April Fool’s article. Well, It turned out I was the fool after all. The propeller is real and it is amazing.

Ken gave us a presentation outlining the key features of this wondrous machine and giving a guide to some of its more interesting applications – like multiple high-speed quadrature decoding in software on just one of its cores (or gogs) while leaving seven more to deal with other tasks like motor control, sensor handling, pathfinding and even simultaneous VGA image generation if you wanted it.

This really is an interesting device. Ken showed a demo board with a couple of motors connected to it for the encoder feeds. the board was plugged into a VGA port and up comes a VGA display – software generated – of the absolute and incremental values from the encoders on the motors. All this took an hour or so to put together. Apart from having to learn a whole new way to program stuff, it seems the only thing these chips lack is on-board ADC peripherals. These may be put on the forthcoming next version of the chip.

I look forward to the first propeller driven micromouse.

Media:
  Slides

 

Alan Dibley: Solving Diagonals with ternary arithmetic

Once you have your mouse running around in the maze in a satisfactory fashion, it is not long before ambition turns to making it run a diagonal path. That is, to cut corners and avoid the need to perform excruciating series of slow, error prone left-right-left sequences of turns. Most mouse builders are looking to replace these staircase sections with a shorter diagonal run. The thing is, turning a path from a set of right angle turns into a diagonal is not as easy as it  looks. There are several approaches to this task. Mostly they involve examining sequences of moves in an orthogonal path, looking for patterns that can be substituted for different kinds of turns.

Alan was faced with the need to do this on his mouse but felt there just had to be a better way or, at least, a way he could understand. After a bit of head scratching and some cheap cake from Cheddar market, he came up with a technique based on counting in base three, taking path elements in groups of three. there are no slides for this session. Instead, follow the link for  a separate entry describing his technique.

Media:
Description

 

Rob Probin and Alan Henness: Vision guided mouse

Last year, Rob and Alan described their plans for a vision guided mouse – 1Vision. This year, they have it able to run in a maze and they described some more aspects of its design and construction.

The mouse uses an ARM chip – he LPC2106 – for its controller. These are cheap and very capable devices. There are a large number of open-source tools available for all platforms and the devices themselves are available from a good variety of vendors. Like the 8051 and its derivatives, the ARM part of the design is the processor core and each manufacturer is able to add their own specific set of peripherals. Thus, compilers are good for almost any ARM based device and only peripheral configuration needs to be changed from one platform to another. There are other small differences but nothing compared to moving from, say and AVR to a PIC. Being multi-sourced, the ARM chips also means your design and product is not resting on the fate of a single supplier.

To design the PCBs, Rob and Alan turned to another open source product – KiCAD. This is a comprehensive schematic and PCB package that is capable of generating industry standard files and artwork which can be given to almost any manufacturer for the production of your PCBs.

Media:
Slides