[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Dropping marker signals?

[Reading guide to the following email: topics covered, in order,
	1) retransmitter beacon to robot communication
	2) utility of the dropped retransmitter beacons
	3) topic number #1 again.

On Mon, Dec 27, 1999 at 12:16:48PM -0500, Joyce Poon wrote:
> Dropping extra beacons in strategic areas is a novel idea (it's something
> that I believe the milllirobots have to do).  However, I am not sure how
> difficult it will be to build transmitters and to build some sort of
> dropping mechanism. 

Say simple transmitters.  If IR is the simplest form of transmitter,
then IR.

I won't even immediately outlaw something as simple as a directly
wired connection where we simply trail a cord of string wire behind us
that is connected to dropped sensors.

You're the one with the catalogue.  What's the average price of a
cheap IR sensor?  :-)

[yes, I know, the only ones listed have sensor ranges of ~5mm, but
 extrapolate based on that to produce the price for a sensor range
 of ~5m...  ;-) ]

> Secondly, I wonder whether this sort of transmitter will actually make a
> significant difference.  If we have to build sensors with a good enough
> range to pick up our rebroadcast signals, these sensors may be good enough
> to pick up the enemy robot itself (unless we have a lot of rebroadcast

Disagree.  Unless the range of the rebroadcast signals is very short
relative to the range of the rebroadcast transmitters is particularly
short, they should be able to work quite effectively.

I propose that for the purposes of analyzing the efficy of rebroadcast
transmitters, the following model is suitable:
    i)   the playing field can be modelled as an empty box with walls
         only along the edges and with no obstacles.
    ii)  robots can be modelled as travelling in straight lines at
         constant speed, but bouncing off walls in a random direction.
    iii) sensor ranges can be modelled as being equivalent for both 
         robots and rebroadcast transmitters.
    iv)  a single rebroadcast transmitter can be modelled as being placed
         in a random location. 

This model would break down under at least two obvious possibilities:
1) the playing field is so littered with obstacles that it more
resembles a maze than it resembles a field, 2) the rebroadcast
transmitters have significantly smaller ranges (either for
transmission or reception of signals) than those sensors on the 'bots

Evaluate based on the above model: Visualize three dots placed
randomly in a square.  Draw circles of some radius around each dot.
Choose two dots and move them according to the model's rules for robot
movement.  Whenever either the a) the circles around the two moving
dots overlap, or b) the circles around the two moving dots
simultaneously overlap the circle around the stationary dot, then
there is sensory contact between our robot and the enemy robot.

For bonus marks, repeat with an increasing number of stationary
circles to simulate an increasing number of dropped beacons.

Now perform the same test, except without the stationary circle.  Sensory
contact only occurs when the two movings circles overlap.

The term "sensory contact" is a little vague.  A rebroadcast beacon may
only be able to say "I sense the enemy" not "I sense the enemy in this
XY direction".  I don't think that this impairs the usefulness of the
model.  A general direction is all our robot needs and then it can
soon hone the specific direction with its own sensor system.

Now.....I admit that when I visualize this test using the above model,
the rebroadcast idea isn't quite as useful as my original
expectations, but it seems to me that it still increases the number of
incidences of sensory contact enough to be worth serious

One big thing that doesn't show-up under the model: If the enemy has
signifantly greater sensor range than us, it's possible that the
only way we'll ever be able to find them is by artificially extending
our sensor range (since they can otherwise avoid us while remaining
outside or sensor range).

>                 These extra transmitters will only be super-effective if
> we can place them just at the limit of our sensor range (maybe in a grid
> type formation).  But how can we do that?  I don't want the robot to waste
> time trying to position all these extra sensors only be tagged during this
> process.  Moreover, since we move around a lot in the playing field, we
> might have to drop several (3-5? at least) sensors to make full use of
> them.  Will we actually have the luxury of time to do so? 

The idea would __not__ be to take time to specifically place the dropped
sensors in the most optimal position.

Rather, during the course of pursuit, drop them when certain events
occur.  Remember...if the evader has a half-decent evasion algorithm,
we will possibly travel in rouch circles several times before actually
tagging them.  Drop a beacon, for example, when we run into an obstacle
(thus we can always find our way back to the obstacle if we are the
evader and need to hide, or if we want to try going in circles around
the obstacle, or ...), drop a beacon, for example, when we make a
sharp turn (since we may soon find ourselves travelling in circles).

> However, in theory, even dropping 1 beacon will reduce the desired sensor
> range in half (if the beacon is at the right place...).  Hmm... since the

Not quite, I believe, but I'll give you marks for recognizing
that even dropping 1 beacon will reduce the desired sensor range.  :-)
It will only cut the desired sensor range in half under certain
ratios of playing-field size to beacon-sensor size.  Not that I've
done a formal mathematical analysis, of course, so I could theoretically
be wrong...  :-)

> What type of sensor will be on this extra transmitter?  If we are doing a
> really simple type of transmission (ie a "yes, enemy is here" and a "no,
> enemy is not here" message), it just has to be the same as the ones on the

I would really love to use frequency variation of a transmitted pulse
to transfer information.  Obviously the more information we transmit
the more the complexity increases.  Let's finish the evaluation of the
utility of a simple "yes, enemy is here" transmission but keeping in
mind the simple assumption that the more information transmitted by
an actual finalized beacon design, the better.  Later we can consider
methods of gathering and transmitting additional information beyond
the simple "yes, enemy is here".  A simple "yes, enemy is here" can be
transmitted by a binary signal: either the signal is being transmitted
or the signal is not being transmitted.

> What type of transmitter will we need?  Maybe a radio signal?  The beacon
> can emit a radio signal when it sees something.  IR may not work, since
> our robot may not be able to distinguish IR from the beacon on the enemy
> and IR of the transmitter.

Back to my idea of pulsing the IR to help us differentiate different
IR signals.  Obviously it is possible to transmit considerable
information via IR --- your TV remove transmits at least 10 distinct
numbers, and IR keyboards, printers, etc. have far more information to
transmit.  What does your electronics catalogue have to say about IR

Also, see fifth-last paragraph of this email, on complexity: it is not
strictly necessary for our robot to be able to distinguish IR that is
broadcast by a retransmitter beacon from IR that is broadcast by the
beacon ontop of the enemy robot.  Retransmission can be as simple as

Big disadvantage of IR in this area: if we cannot establish a
line-of-sight from our robot to the beacon, we cannot receive its

Nonetheless, the simplicity of IR makes it attractive, imho.

[Sensor design _is_ your area, here, Joyce...make some suggestions...  :-) ]

> Can the beacon be an interference-generator?  Sure.  But, for some strange
> reason, I think a rotating mirror will confuse us as much as the enemy... 

Hehe.  If my scant understanding of statistical probabilities is
correct, a "random walk" would work in our favour provided that we
were the evader.  :)

> Other silly ideas for interference: How monochromatic is IR light?  If we
> can somehow diffract the light emitting from us, we coud mask ourselves
> (stealth!).  Or we could drop a diffraction grating and stand behind it... 
> then there would suddenly be a bunch of IR signals -- that should confuse


> Speaking of things rotating... maybe we can encode our beacon signal if we
> place a sheet of etched rotating glass/plexiglass in front of the emitter. 

Oi.  Why not make the beacons into little helicopters while we adding
the rotating glass/plexiglass...

[ :) ]

> problem).  V=D/T. If our robot runs on a clock (which I think it will),
> then we know the time.  To find distance, I guess we can keep track of the

Yes, a clock is very likely to be necessary.  If one doesn't come
onboard with the boards they give us, then it would probably need to
be added.

> Here's my feedback for now.  I have to think more about map
> construction... Can't a simple map be built just by assuming that our
> starting position is the origin and noting stuff like, "there is nothing
> to the right" "there is something to the left" etc.?  I will think about

I imagine map-building and usage has been quite studied, and when the
time comes, I'll look around the Internet to see what it says.  At the
moment, however, I'm still working myself through the various 6502
docs and development tools available (someone just emailed me the
source for yet another 6502 Commadore 64 compiler, although I'm not
allowed to distribute the source), to see exactly what can and cannot
be done on such a small chip.  For now, suffice it to say that having
known stationary beacons/markers would help to prevent the map from
drifting as small sensor errors accumulate (imagine trying to follow a
map whose directions are written in the form "walk X feet in the Y
direction" if you always accidentally walked only 3/4 the instructed
distance when travelling in the North-South direction -- the
accumulation of systematic errors can be most annoying).

>                                         I think the most effective
> approach is just to maximize the sensor range on our robot.  Dropping
> extra sets of "eyes" around the playing field will definitely complicate
> the design...

I don't believe it needs to complicate the design at all.

If IR reciever/transmitter pairs can be purchased at a couple different
frequences, then it's as simple as designing the retransmitter
beacons and loading the robot with an extra set of sensors (multiple
retransmitter beacons can share a single IR frequency with few
drawbacks at all, assuming we use our simple "yes, enemy is here"
communication...for more complex communications, this may not always
be true).

If we're limited to one IR frequency (ugh!), then in the worst
case multiple lines of communication could be multiplexed over the
single channel using pulsed IR broadcasts at a different prime
frequency for each secondary communication line (tricky to get quite
right, I imagine).  In the more likely and more likeable case (still
considering one available IR channel), the retransmitters could act as
retransmitters in the simplest sense --- just amplify the IR signal from
the beacon ontop of the enemy when they sense it.

Make sense?  I know this was confusing in the past...  Ask questions.  :)

I don't think there's any reason it should complicate the design
significantly at all.

By comparison, I'm not sure that there's much we can do to "just
maximize the sensor range" of our robot.  It seems to me that the
sensor range is a function of which receiver/transmitter IR pair you
happen to be using, more than a function of careful robot design.
Some amount of testing to determine the correct heights and angles for
sensors and transmitters, (remember too that the transmitter will
potentially be placed at a varying height depending on the enemy
robot's constructors), but that would seem to be about all.

PS: Happen to know CBC's TV schedule for Sunday night?  :)

Signature withheld by request of author.