Re: Searching strategies

["David Hannaford" <david@davidhannaford.com>]

Peter

Assuming that you are going to follow a strategy that searches from the 
start to the centre and also searches on the way back to the start, then 
when you get back to the start you have 2 scenarios:

1 - You run the flood algorithm and find that you have visited all the cells 
on the flood route, in which case you have found the optimal route and it is 
not worth doing any more searching
2 - You run the flood algorithm and find that you havn't visited all the 
cells on the flood route yet, but you do know how many cells are on the 
route that you took back and you also know how many are on the possible 
flood route that you have just calculated. This last figure will be a best 
possible number of cells (which might not actually be achievable when you 
visit some cells and find extra walls).

If your best actual route so far is not too different from the best possible 
flood distance you have just calculated then there is definitely no point in 
further exploring.

So how much difference do we need before it is worth going out again to 
explore?
Well, an explore run will typically require a run to the centre and back at 
explore speed. If we say this is likely to take 15 seconds each way then the 
full round trip will be 30 seconds which by UK rules means an extra second 
of penalty time.

Now with typical run times to the centre now being sub 10 seconds, then to 
save out extra second penalty time we need to find a new route that is more 
than 10 percent faster to break even.

So with a typical maze route of 70 cells to the centre you need to be sure 
of finding a route that is at least 7 cells shorter to break even.

So, given that the theoretically best route believed to exist at this time 
will not always be able to be achieved, I would be looking to probably get 
double the break even figure. I.e. the calulated best route must be 14 cells 
better than the currently known one  before it is worth going out to explore 
more.

Anyone else think this makes any sense?

Cheers
David Hannaford





----- Original Message ----- 
From: "Peter Harrison" <peter.harrison@helicron.net>
To: <micromouse@cs.rhul.ac.uk>
Sent: Thursday, August 26, 2010 6:10 PM
Subject: Searching strategies


In the UK, as in some other countries, we have a search penalty. A 
proportion of the time taken to search the maze is added to subsequent speed 
runs. That means that a mouse that did a less than optimal speed run early 
might get a better score than a mouse that did the best possible route 
later.

If searching consisted of just a search to the goal followed by a search to 
the start, a route would exist but it may not be the best.

Anyone have a feeling (or data) to suggest whether it is better to search a 
bit more or just go with what you have as soon as possible?

Peter Harrison

<<

Email has been scanned for viruses by Altman Technologies' email management 
service - www.altman.co.uk/emailsystems

 >>
=


--------------------------------------------------------------------------------



No virus found in this incoming message.
Checked by AVG - www.avg.com
Version: 9.0.851 / Virus Database: 271.1.1/3094 - Release Date: 08/25/10 
19:34:00


<<

Email has been scanned for viruses by Altman Technologies' email management service - www.altman.co.uk/emailsystems

 >>