Tag-playing strategies [was: Re: Preparation for Proposal?]

[Tim Vanderhoek <vanderh@ecf.utoronto.ca>]

On Fri, Nov 19, 1999 at 06:38:01PM -0500, Joyce Poon wrote:
> I agree.  Let's see him at 9am sharp. Maybe we should all be there at 8:30
> so that if other groups get there b/w 8:30 and 9, then we will be able to
> go first more legitimately.

Just so long as at least one person is there before 8:30, too.  :)


> On another note, I think we have spent enough time discussing the
> electromech part.  To get our project approved, we should have sufficient
> info on sensors and strategy before we see him.

In summary, this is what Malone says he is interested in:

  1) list of what is REQUIRED for a tag playing robot
  2) concept sketch that meets requirements
    -> mobility methods
    -> tag-playing strategies

Of these two, we've already gone through #1 last time, and started the
concept sketch with him.  I don't think we need "info on sensors" so
much as we need to think about tag-playing strategies.

I don't think tag-playing strategies requires too much thought for
the immediate moment...we sense the enemy and we move towards the
enemy.  We don't sense the enemy and we move in increasingly large
circles until we do sense the enemy.  We run into a baracade and we
make one attempt to go past it (by backing-up and turning x number of
degrees (0 < x < 15) and then continueing forward).  If that fails,
we choose a new direction to travel in and ignore any beacon-sensor
input temporarily.

[Why do we use this algorithm to handle baracades?  Well, when we run
 into a baracade, that baracade may be as simple as a piece of glass
 or as an upturned garbage can.  Alternatively, that baracade may be
 the edge of the playing field (in which case we _can't_ go around it).
 Also, when we run into the barracade, either we are currently sensing
 the enemy robot (presumably we're sensing him in the direction of the
 baracade, otherwise we wouldn't have run into the barracade!), or we
 are not currently sensing the enemy robot.  That's a total of four
 cases.  The proposed simple algorithm handles each case reasonably
 well:

 case 1: baracade is a wall, enemy in sensor range,

         Oh-uh.  We're sensing an enemy robot that appears outside
         of the playing field.  This means we must be sensing either
         noise from some source, or we are picking-up a reflected
         signal.  All we can do is go away from this bad location and
         hope that when we start accepting sensor-input again, we will
         be detecting the real robot.

case 2: baracade is a wall, enemy not in sensor range,

         Obviously we're looking to try and find the robot.  Okay, well,
         we're not going to find him this direction...  Head somewhere
         else.

case 3: baracade is small, enemy in sensor range

         We'll hopefully be able to get past the barrier and continue
         in pursuit of the enemy.

case 4: baracade is small, enemy not in sensor range

         Well, maybe the enemy is hiding behind this barrier, so we will
         make at least one attempt to get past the barrier so that we
         can see for sure.

When backing-up after striking a barrier, we should choose a
pseudo-random distance to go backwards.  We should also choose a
pseudo-random number of degrees to turn.

I know that at least Joyce is screaming when she reads this.  :)  Why!
The random element exists to ensure that cases such as "barrier is
large and looks like a wall but is not the edge of the playing field".
The randomness means that most of the time you will back-up a short
distance and will turn a short number of degrees, but if you keep on
running into the same wall, eventually you will back-up a large
distance and turn a large number of degrees and will be able to get
past this wall.

For simple cases where you keep on running into the same wall, it is
not hard to detect (from the computer) what is happening.  For more
complex cases, you may be bouncing off of different walls due to some
wierd reflections occuring in the beacon's signal.  This is very hard
(perhaps even theoretically impossible) to detect for the computer.
Randomness is a fairly standard way of avoiding problems in
algorithms.  For example, the Internet uses randomness in its routing
algorithms to prevent packet jams.

A lot of reasoning behind an essentially very simple algorithm.  Those
are usually the best and most effective type of algorithms!!!

[I'm tempted to say "almost without exception always the best and most
effective type of algorithms"].

It is not hard to imagine improvements on the simple algorithm
proposed.  For now, we should only be considering the most simple and
basic things we need.  At some time, after the proposal is approved
and after we are past this hell they call "Week #XX of Engsci", we
should meet and (extensively) discuss "wishlist" ideas.

I talked a little about sensors with two fourth years who did the
robot project.  I didn't feel obligated to ply them for too much
information since one lives on my floor and he could prove useful
later (ie. I don't want to use-up my quota of questions to early in
the game :).  However, I'll hopefully send another email tonight
outlining a couple of things they said that are relevent to what we
discussed this (Friday) morning.

Comments requested, as usual.


-- 
Signature withheld by request of author.