The Ants’ Nest Problem (1)

Some readers of theendtoendblog were surely convinced it would never happen: “He’s been promising us results from this ants’ nest work for an awfully long time and nothing ever comes. Typical!”

Well, sorry to disillusion you, but it’s showtime!

Two posts ago I introduced you to what for me is an intriguing little problem (‘Searching for a model’, 2 March 2021). The situation is as follows: (1) a large number of ants are moving simultaneously across the surface of a nest; (2) their overall movement pattern is presumably systematic (for instance to transport materials from one part of the nest to another), but there are no obvious regularities in the paths taken by the ants individually; (3) the ants manage to avoid colliding with each other. The problem – ‘The Ants’ Nest Problem’ – is to try to understand why and how the ants move as they do. (If you’re thinking you’ve already read a post about something that sounds suspiciously similar, yes you’re right. Check out ‘Models, and walking of course!’, 21 August 2020.)

The first step in addressing a problem like this is of course to come up with ideas about what is going on in the system concerned. Two ideas seem promising in this present case. The first of these is that each ant is continually deciding for itself which path it will take in the immediate future; it is doing this on the basis of information on (1) how it is moving at the time, (2) any preferred movement direction, and (3) its position relative to its neighbours. The second idea is that every one of the ants restricts its movement to its own particular neighbourhood; it never trespasses on adjacent neighbourhoods. (And yes, you are remembering correctly. You did read once before about the meaning and significance of trespass. Check out ‘Trespass!’, 13 January 2018.)

OK, those are the ideas; now to express them in a model. I’m going to deal with this in several posts: first I’ll cover how an ant decides on its path, then I’ll cover how it avoids trespassing.

It’s surely not unreasonable to suggest that any model for the movement of these ants should be a stochastic one. Firstly, the ants are behaving as separate entities; there is no Grand Old Duke of York directing them, nor is there an overall Master Plan that they have to follow. Secondly, the ants are living things; they are not inanimate physical objects. The movement of the ants will be modelled here as a random walk. (Yes, it is indeed déjà vu all over again! Check out ‘Walking at random’, 8 August 2020.)

There are in principle two types of random walk. One type – this is the one I described in that earlier post – has steps that are uncorrelated both in length and in direction. The other has steps that are correlated: the length of a step in a walk is obtained by adding a random increment to the length of the immediately preceding step, the same holds for the step direction. Within each of these types there is effectively unlimited variability. You can choose at will the frequency distributions you want, either for the step length and the step direction (for walks of the first type) or for the step length increment and the step direction increment (for walks of the second type).

An example or two wouldn’t be a bad idea, would it? And then perhaps a program to experiment with. OK, here goes. First the examples.

Random walks with uncorrelated steps: (a) no preferred direction, 10000 steps; (b) preferred direction, low directional continuity, 50 steps; (c) preferred direction, high continuity, 50 steps. Inset (top right) shows direction coordinate system.

Random walks with correlated steps and preferred direction, all for 10000 steps: (d) no bias; (e) no bias; (f) bias away from preferred direction; (g) bias towards preferred direction; (d, f, g) high directional continuity; (e) low continuity

What you’re looking at in each of these seven screenshots is a plot of a 2D random walk that started at the intersection of the purple lines. In each of the plots there is also a histogram of the step directions. The plots come from a program – DRWALK – that I’ll be introducing in the next post and that you can then experiment with. The walks in these plots are clearly different in their character; this is unsurprising because they were deliberately generated using very different frequency distributions. DRWALK controls the form of the distributions in five ways. Firstly, it controls the type of walk: uncorrelated or correlated. Secondly, it controls whether or not the walk is to have a preferred movement direction; this direction, if it is required, is fixed to be west-to-east, i.e., 180° in the coordinate system illustrated in the inset in (c). Thirdly, it controls the directional continuity, i.e., the degree to which the direction taken at any particular step follows either the preferred direction (for uncorrelated walks with a preferred direction) or the direction of the previous step (for correlated walks). Fourthly, it controls the degree to which the direction of a step is biased either towards or away from the preferred direction; this control applies only to correlated walks. Fifthly, it controls the mean and standard deviation of the step lengths or step length increments.

OK with all that? If so, great! If not, come back next time. You can then download DRWALK and play around with it to your heart’s content.

For anyone who’s been wondering…

Strider, Number 149, April 2021

Yes, theendtoendblog is still alive and well! First, there’s a new Strider article; then there’s progress in the matter of the ants. As always, to make the article legible simply click on the photo. If that doesn’t work, here’s the text:

“The immediately preceding articles in this series have dealt with three of the steps necessary in planning any substantial long distance walk: (1) breaking the walk into legs, (2) deciding, at least provisionally, on the routes for the legs, and (3) waypointing the routes. Wait! Don’t get your boots out yet! There’s still work to do! Those routes have first to be checked to see if they’re really what you want; then alternatives have to be prepared for sections for which alternatives are necessary. This work is going to take time – there’s no hiding that fact. It’s nonetheless going to be time well spent. Imagine that the walk you’re planning is one that’s going to take you out into the wild blue yonder, alone, for a month or more, and is not going to come cheap. It’s better to spend a little more time beforehand planning that walk than to spend a lot more time afterwards – either on the walk itself or after you’ve got back home – regretting the fact that you didn’t.

It’s at this point, before you start on this remaining work, that you’re going to have to make a critical decision. Which working methods are you now going to use? Are you going to work with guidebooks and maps on paper, or are you going to work on the computer? Both approaches are capable of giving satisfactory results and in the end it’s your decision. The essential difference between them is of course that a computer-based approach will be very much quicker than a paper-based one. I’m going to make three assumptions here: firstly, that you’ve decided to work on the computer; secondly, that your computer runs under Windows; thirdly, that your principal data formats will be .gpx and .kml.

Let’s see what’s involved in checking a route. For an example – this is an extremely straightforward one – look at the Google Earth image I’ve prepared. It shows part of a waypointed route along the Pembrokeshire Coastal Path, starting at the Copper Mine (the westernmost point of mainland Wales, southwest of St David’s) and finishing at Newgale. The checking process I use has four distinct steps; I’ll run through them in turn for this example.

The first step involves making a .gpx file of the waypoints. The software I use to do this is the GPS Route Planner available on WalkHighlands (https://www.walkhighlands.co.uk) and WalkLakes (https://www.walklakes.co.uk/). This program uses the 1:25K OS maps as its base and readily lets waypoints be inserted in the order of their decreasing importance, exactly as I described in my last article. Once you’ve inserted the waypoints you get estimates of the route length (17.3 km for the Pembrokeshire example) and the total height gain. The length estimate gives you a very rough lower bound for the time you’ll need to cover the route (3:28). You can ignore the height gain estimate because it assumes you’ll always be walking in a straight line from one waypoint to the next. At the end of the step you save your file.

The second step uses the route planning software again, but this time to fill out the route between the waypoints. This involves inserting an intermediate point at every change in route direction that you see on the map, no matter how small, and at every significant change of slope. There will be a lot of these points to insert – the Pembrokeshire route has 663. Don’t worry! With practice you’ll find they go in like a rocket; filling out the Pembrokeshire route took me less than half an hour. At the end of this step you’ll get a fresh estimate for the route length (20.9 km) and at last a usable estimate for the total height gain (797 m). From these two estimates you calculate the Naismith time in the conventional way (5:29). At the end of the step you again save your file. This time you make two versions of it – one in .gpx format and one in .kml format.

The third step is where the fun begins. Start Google Earth and load that .kml file. Now examine your route in detail on Google’s aerial mosaic. Look at it from above; look at it from the side; look at it obliquely; fly along it if you will, using the ‘Play Tour’ control. Some of the points you inserted in the previous step will certainly turn out to be wrongly positioned, either because of errors you made in inserting them or because of changes on the ground since the OS map was made. Reposition these points using the Google Earth path editor. Look for features visible on the Google Earth image that weren’t on the map and that can sensibly be incorporated into your route. Modify the route to incorporate them, again using the path editor. Check the types of ground surface your route will take you over. Will you be mainly on Council-maintained paths, for instance, with occasional climbs up grassy hillsides, or will you be trekking across His Lordship’s grouse moor with now and then some serious scrambling? There’s a mass of ground surface information visible in every Google Earth image, as in every aerial photograph, and you can supplement it if necessary using ground truth photographs, for instance from Geograph (http://www.geograph.org.uk/). This information is especially important because it greatly affects your estimate of the time you’ll need to cover the route. At the end of the step you save your modified route as a new .kml file.

The final step involves first converting this new .kml file to .gpx, for instance using KML2GPX (https://kml2gpx.com/?results). Then you load this file into the route planning program you were using earlier. This gives you length and height gain estimates for your modified route, together with a best estimate of the Naismith time.

Is this modified route satisfactory? Is it really what you want? Good! All that then remains to be done is to prepare any necessary alternatives. I’ll deal with that next time.”

And the ants? I’ve now found what seems to be a very reasonable model for the ants’ nest, which produces some fascinating results. The development and implentation of this model has required the solution of a few not insubstantial problems in geometric computing, so that’s why you haven’t heard much from me recently. Now, however, it’s showtime – well almost! Expect (D.V.) something in the next few days.