Intelligence Subsys

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

I should proofread the "Suggestions" section more closely than I have.
It was written last and relatively quickly.

4 Intelligence Subsystem

4.1 Assessment of the Problem

	A tag robot can be made to function at the simplest level
of moving towards a beacon or moving away from a beacon --- persue
and evade, respectively.  However, as any human who has ever played
tag knows, choosing the optimal path in which to run, in both the
persue and evade cases, is an extraordinarily complex problem.
The requirements for the intelligence subsystem were that it be
able to control the motors and read that sensors, Zeta's feet and
eyes, but also that it be imbued with the minimal intelligence to
persue and evade a beacon, and almost as importantly, the ability
to have this intelligence expanded and improved in future versions
or prototypes.
	Interacting with Zeta's feet and eyes, the motors and
sensors, was the simpler of the software's two tasks.  Reading the
impact sensors required only the ability to do simple input.
Reading the IR (XXX acronym) sensors was a multistep process the
steps of which are listed in table XXX.  This process, and that of
controlling the motors with PWM using feedback from the opto-encoders,
required the use of some type of timing mechanism.  In addition
to the timing mechanism, algorithms to turn input from the
opto-encoders into information useful for higher-level
intelligence needed to be developed.
	To give Zeta the potential for higher-level intelligence,
it was required that Zeta be able to track its location relative
to a starting location.  Routines to combine information from
multiple sensors to produce decisions that took into account the
context of concurrent and previous sensor input needed to be
written.  This was the harder of the software's two tasks.
	A major implicit requirement of the problem, as described
above, is that while the software must develop the potential for
higher-level intelligence, the software must not become so
complex that it would be difficult to integrate or impossible to
complete.

4.2 Solution

4.2.1 Introduction

	The solution to the problem is a software project
referred to as Qubit.  Qubit was designed to be easily extendible
towards higher levels of intelligence without requiring these
higher levels of intelligence to operate.  This was accomplished
by breaking the software into five separate modules.  Each module
was responsible for some aspect of Zeta's intelligence.  The
moduels that implemented the basic sensory and control
intelligence needed to be implemented completely.  The modules
that implemented higher-level intelligence could be implemented
as testing on Zeta continued and as confidence in the existing
code and existing robot increased.
	The five modules and a brief description of the purpose
of each are listed in table XXX.  In addition to this, every
significant function in the program along with a brief
description for the function is listed in table XXX, sorted by
module.  All of the source code has been included in the appendix
(XXX).  The flow of information is shown in figure XXX.  Each
module was called and prompted to perform any actions it needed
to perform from an infinite loop inside the main() function.
	The writing of the modules themselves was affected by the
choice of computer board and development tools.  In particular,
multiplication on the computer board chosen was a slow process
requiring about 1 millisecond to multiply two numbers.  If a
multiplication operation were placed inside a double-nested loop,
the loop could easily require greater than 1 second to execute, a
large enough amount of time that many of functions such as PWM
motor control would be disrupted.

4.2.2 Choice of development platform

	The 6502-based board offered as part of the aer201s
course was chosen for its low price.  To ease and speed
development, the board was programmed using a C compiler mixed
with some assembler.  Other development tools were considered and
they are compared in table XXX.

4.2.3 Clock module

	The clock module provided all timing services needed by
other modules.  Interrupts were set for 2ms intervals with an
interrupt handler that incremented a basic clock count.  When the
clock module was entered from the main() function, the basic
clock count would be examined and this module would then adjust
clocks for all other modules at the appropriate rate of time.

4.2.4 Sensor module

4.2.4.1 Introduction

	The sensor module was responsible for reading and
interpreting the impact sensors, the opto-encoders, and the IR
sensors.  Separate submodules were written to handle each of
these.

4.2.4.2 Impact Sensors

	The sensor module needed to notify other
modules when a collision occurred and of the relative angle of the
impeding obstacle.  This job required debouncing the impact sensors.
After one impact sensor fired, the module ignored all impact
sensors for 2 seconds.  The relative angle of the sensor that
fired was then looked-up in a table and reported to other
modules.

4.2.4.3 Opto-Encoders

	The sensor module needed to identify Zeta's speed and any
directional changes.  The distance travelled by each wheel was
reported by the opto-encoders.  The direction in which the wheels
were turning was reported by the tactical module.  These two data
were used together to determine speed and directional changes.
The calculations necessary to determine directional changes are
shown in figure XXX.  The theta = f(y) (XXX) function was compiled
into a table lookup that gave the correct results for y>0 and y<0
as shown in figure XXX.

4.2.4.4 IR sensors

	The sensor module needed to read and control the IR
sensors and report the direction of any opposition robot to the
strategy module.  To read the IR sensors, the motors were turned
off to eliminate noise and each of the sensors was checked
following the process shown in table XXX.  If more than one
sensor returned a positive signal, the angles of all sensors
returning positive were averaged to determine a single angle.  To
prevent this routine from being computationally expensive, true
averaging was not performed, but rather the algorithm shown in
figure XXX and demonstrated in table XXX was performed.  Testing
showed that the IR beacon would usually set off three sensors.
As demonstrated in table XXX, this resulted in only a small
amount of error.

4.2.5 Strategy Module

4.2.5.1 Introduction

	The strategy module was responsible for analysing information
sent from the sensor module about the relative direction of the
opposing robot and the relative location of obstacles.

4.2.5.2 Response to striking an obstacle

	Zeta was outfitted with 8 bumpers centred at
evenly-spaced angles.  Figure XXX shows the centre of each
bumper.  No bumpers were centred at 0 degrees or at 180 degrees;
this ensured that it would always appear to the software as if
Zeta struck obstacles at some indirect angle.  The strategy
module responded to collisions by reflecting Zeta off of the
obstacle as light reflects off of a mirror.  Zeta drove in the
reflected direction for a distance of 1 metre before resuming her
normal operation.
	The method of reflecting Zeta off of obstacles was intended
to improve her persue and evade abilities when the opposition was
within sensor range.  Figure XXX shows the expected behaviour
when Zeta is persued into a corner.  Figure XXX shows the
expected behaviour when Zeta is persued directly into a wall.  In
the latter case, whether Zeta proceeds along the course shown in frame
B or the course shown in frame C depends on which of the two front
bumpers is set-off first.  In all cases, the persuer has had to
slow its speed in order to adjust its direction as Zeta bounced off the walls.
Figure XXX shows Zeta persueing a stationary evader that was hidden behind
an obstacle through which IR could pass.  Zeta's behaviour when
striking obstacles ensured that it could maneuver past the
obstacle.  In frame D, Zeta may strike the obstacle a second
time, but Zeta's behaviour guarantees that the obstacle will not
be struck a third time.

4.2.5.3 Response to detecting the opposing robot

	Zeta responded to detection of the opposing robot by
either driving directly towards the opposing robot or directly
away from the opposing robot, depending on the current input from
the mode select PERSUE/EVADE switch.

4.2.6 Tactical Module

	The tactical module was responsible for driving in
certain motions and in certain directions.  The strategy module
used the targetpl() function to request that a certain
direction be taken.  The tactical module then compared this with
the current direction in which Zeta was travelling and turned
the robot clockwise or counterclockwise as needed, or fully
reversed the motors if a direction reversal was considered more
efficient than turning.  The potential to cause Zeta to oscillate
in a never-ending attempt to fine-tune her direction was avoided
by writing this module to accept any direction within 28
degrees of the targetted heading to be as good as the targetted
heading.  Once an acceptable direction heading was reached, the
module attempted to equalize the speed of the left and right wheels.
While driving normally, the PWM of the motors was adjusted once
every 160 milliseconds by this module.
	In addition to providing directional control, the
tactical module was responsible for moderating the speed at a
chosen maximum value, ideally 3 ft/s.  Due to physical reasons,
this maximum speed was only achieved under unrealistic testing
conditions and speed modulation of Zeta was essentially unused in
the final robot.
	When it was necessary to reverse Zeta's direction, this
module followed the steps listed in table XXX.  These careful
steps were necessary so that the sensor module would be notified
at the correct time that each wheel had switched direction.

3.1.5 Motor Control Module

	The motor control module produced a PWM signal to control
the two motors.  A constant OFF cycle of 40ms was used with an ON
cycle that could vary from 2ms to 512ms depending on the duty
cycle requested by the tactical module.

3.2 Suggestions for improvements

	There is tremendous room for improvement in this
subsystem.  If more testing of the real robot could be performed,
there may be bugs in the existing code revealed.  In addition to
debugging the existing code, there are many higher-level
intelligence functions that can be written.
	There are two known changes to the existing code that should
be made.  The first is that directional changes are registered by
the sensor module as being of approximately twice the magnitude of
the actual change.  For the code as written, this is irrelevant
since it is impossible to distinguish a world that rotates around
Zeta from an opposition robot that is rotating around Zeta.  Nor
did this bug prevent the tactical module from driving Zeta in a
straight line: testing showed that Zeta was able to drive in straight
lines even on highly uneven surfaces that forced directional
corrections.  However, if code to track Zeta's x,y position were
added, then this bug would need to be fixed.
	The second change to the existing code would be to the
debouncing of the impact sensors in the sensor module.  After a
collision occurs, the impact sensors are ignored for a set period
of time.  It would be better if they were instead ignored until
Zeta had travelled a known distance.  This change would mean that
the set period of time would not need to be adjusted whenever an
improvement to Zeta's drive system resulting in higher acceleration
was made.
	Some parts of the strategy module have been written to
take advantage of Zeta's x,y location, if it is known.  In
particular, the software tries to turn and avoid collisions with
locations where a wall is believed to be, but this code is only
enabled if Zeta's x,y location is known.  However, the code
to track Zeta's x,y location was never written.  Zeta's x,y
location could be tracked by looking-up displacement travelled
and angle of travel in a two-dimensional array to find delta x
and delta y values.  This code was not written because of the
extensive testing it would have required.  However, adding this
code, if it could be made to function accurately, would allow
Zeta to avoid walls after hitting them; a significant improvement
in Zeta's ability to evade a persueing robot.
	Once a method of accurately tracking Zeta's x,y position
were implemented, it would also be possible for Zeta to remember
the location of obstacles other than walls.  In part because of
the computational limitations of the 6502 board and in part due
to the nature of things, collision avoidance algorithms for
obstacles are more difficult than those for walls.  Developing
the necessary algorithms and making them fast enough to run on
the 6502 board would be a challenge, but the resulting tag
playing improvement may be large enough to make the effort
worthwhile.


table XXX Steps taken by tactical module when reversing direction

1) Turn off motors
2) Briefly pause to prevent damaging the relay switch by switching
it while current was still flowing to the motors.
3) Toggle both directional relay switches on the motor control
circuit board.
4) Briefly pause to allow the relay to switch.
5) Turn the motors on with a large duty cycle.
6) Wait for each wheel to slow down and then speed up again. 
When the wheel slowed down to nearly a stop, the opto-encoder
section of the sensor module was notified that the particular
wheel had switched direction.
7) Once both wheels had switched direction, resume normal control
of the robot.

Table XXX Sample Averaging of Multiple IR Sensor Positives

If IR sensors at angles 0, 32, and 64 degrees are returning
positive, then the averaging procedure will be:

	- test sensor at 0 degrees
	- sensor is returning positive: set angle to be 0 degrees

	- test sensor at 32 degrees
	- sensor is returning positive: add 32 to 0 and divide
	  total by 2.  New angle is 16 degrees.

	- test sensor at 64 degrees
	- sensor is returning positive: add 64 to 16 and divide
	  total by 2.  New angle is 40 degrees.

In this case the most probable angle of the opposition was 32
degrees and the averaging algorithm returned 40 degrees.  This is
considered acceptable error.


Table XXX Name, location, and purpose of functions

All non-empty routines and routines not specifically used to
record errors (that is, all routines in trouble.c) are listed in
this table.

Functions not belonging to any particular module:

main() - main.c

	Entry point into the program.  Performs necessary board
initialization and then enters an infinite loop calling the entry
point to each module.

status() - main.c

	Used during simulation to output the values of important
program variables.

pretend() - main.c

	Used during simulation to produce false opto-encoder
sensor inputs based on false motors and to produce false IR
sensor inputs.

Functions belonging to the clock module:

clock() - main.c

	Entry point into the clock module.  Examines an internal
counter that is incremented by inthandler() and updates the
clocks for all other modules.

inthandler() - main.c

	Executes every 2 milliseconds and increments a counter.

nointhandler() - main.c

	The interrupt handler used while the PAUSE (or ON/OFF)
input is low.  The nointhandler() is the same as inthandler()
except that no counter is incremented.

pint() - main.c

	Used during simulation to produce false interrupts.

Functions belonging to the motor control module:

delta_lmtr_down() - mcontrol.c

	Decreased the duty cycle of the left motor

delta_lmtr_up() - mcontrol.c

	Increased the duty cycle of the left motor.

delta_mtr_down() - mcontrol.c

	Decreased the duty cycle of both motors.

delta_mtr_up() - mcontrol.c

	Increased the duty cycle of both motors.

delta_rmtr_down() - mcontrol.c

	Decreased the duty cycle of the right motor.

delta_rmtr_up() - mcontrol.c

	Increased the duty cycle of the right motor.

mcontrol() - mcontrol.c

	Entry point into the motor control module.  This was used
to send PWM output to the motors.

set_mtrspd() - mcontrol.c

	Set the duty cycle of to some specific value.


Functions belonging to the sensor module:

atan() - math.c

	The lookup table for the f() function shown in figure XXX
that was used to determine changes in Zeta's direction.

backwheel() - sensor.c

	Read and interpreted input from the opto-encoders.

sense() - sensor.c

	Read, interpreted, and controlled the IR sensors.

sensor() - sensor.c

	Entry point into the sensor module.  Called entry points
into the submodules for handling the opto-encoders, the impact
sensors, and the IR sensors.

touch() - sensor.c

	Read and interpreted input from the impact sensors.


Functions belonging to the strategy module:

explore() - tactics.c

	Travelled forward.

hide() - tactics.c

	Travelled in small circles.

mp_sense() - map.c

	Used to alert the strategy module when the IR sensors
have detected the opposition robot.

roam() - tactics.c

	Travelled forward.

strategy() - map.c

	Entry point into the strategy module.  Chooses a
direction and displacement in which to travel depending upon when
the opposition was last seen and where.

tc_touchnotify() - tactics.c

	Used by the sensor module to report collisions to the
strategy module.  When a collision was reported, this function
would cause Zeta to stop chasing or evading an opposition robot
(if Zeta was doing so) and instead respond to the collision as
described in section 4.2.5.2.

Functions belonging to the tactical module:

tactic() - tactics.c

	Entry point into the tactical module.  Handled performing
direction reversals, direction changes, and speed control.

targetpl() - tactics.c

	Set the target direction to some value.

tc_move() - tactics.c

	Used to report small displacements to the tactical
module.


Table XXX Name and purpose of every module

clock module		Updates clocks inside all other modules.

motor control module	Handles PWM control of the motors.

sensor module		Reads impact sensors, IR sensors, and
			opto-encoders, interpreting their output
			into a form useful for other modules.

strategy module		Analyzes and remembers information
			produced by the sensor module to choose a
			displacement and direction in which to travel.

tactical module		Responsible for driving Zeta in the
			direction chosen by the strategy module.

[XXX the description of the tactical module breaks parallelism:
should begin with a verb.]


table XXX

Steps required to read an IR sensor

1.  Select the sensor to read and output a control signal
specifying this sensor.
2.  Wait a period of time no less than an amount to be determined
while the sensor circuitry adjusts to the current sensor.  The
period of time required for the sensor circuitry to adjust to the
new sensor was determined using the find_tau.c program included
in the appendix (XXX).
3.  Sample the sensor input line.


---------------------------APPENDIX ENTRIES---------------------------

appendix XXX: More extensive comparison of different development
              tools available for 6502 boards

Five different tools were examined to compare suitability for
6502 development.  Two tools were free C or near-C compilers,
Quetzalcoatl and cc65.  Two tools were old unsupported
assemblers, DASM and TASM.  The remaining tool was a hybrid
assembler and compiler, M5.

The Quetzalcoatl pseudo-C compiler was clearly not mature.  The
author and its homepage (http://www.kdef.com/geek/vic/quetz.html) stated
as much outright.  The source code for Quetzalcoatl was obtained
and examined for useful spare parts.  None were found.  As the main
software creation tool, it will not be examined further.

Matthew Dillon's DASM was (is) a very popular assembler whose author
is also FreeBSD committer and whose coding ability is exceptional.
However, it has not been actively maintained for what appears to
be more than 10 years.  Although this was a credit to the quality
of the initial code, it also meant that support for DASM would be
hard to find.  DASM appears to offer an assembler that is about as
flexible as the one in cc65.  The latter has the obvious advantage
of being supported.

TASM only runs under dos.  TASM was examined only briefly and did
not appear to offer any significant advantages.  It was not considered
further.

The M5 language had the advantage of integrated floating point math
librarys (something none of the other options had), but no need for
floating point was expected.  M5 also offered an impressive
process-handling library, although that library was certainly
overkill for anything Zeta might have used it for.  One very nice
advantage to M5 was the extra debugging facility it provided
through the associated simulator.  Disadvantages of M5 were its
relatively poor documentation and the fact that it had very few
users, which meant that a greater potential for bugs existed.  The
source code for M5 was not available which aggravated the poor
documentation and lack of support.

The cc65 C compiler came with an assembler that appeared to be
about as powerful as DASM (ie. far more powerful than tasm).  The
runtime library was written in assembler.  The linker linked only
the necessary parts of the library.  The cc65 compiler was able to
produce fairly small code, provided reasonable C coding style was
used.  One major advantage to cc65 was that of all the options, it
was the only one (if M5 is considered to be a macro-assembler) that
allowed the developer to casually switch between a complete high-level
language and assembler.  The loop controls of M5 were a minor
convenience only, in comparison.  The major disadvantage is that
some work was necessary to make cc65 operate nicely with the
simulator and its extra debugging facilities.  The extra work to
make cc65 work on the aer6502 boards was not considered very
significant.  The extra work required to integrate cc65 with the
6502 monitor program was significant, however this work yielded
dividends above and beyond simply using the monitor with M5.  The
greater familiarity with the monitor source meant less probability
of stepping on its toes with the developer's own code.  The single
largest advantage of cc65 over other alternatives was development
speed.  Even to take advantage of the more limited higher-level
facilities in M5, it would have been necessary to learn the M5
high-level language, a language which is somewhat lacking in
documentation.

appendix XXX: Naming conventions for Zeta

[XXX I really really want to include this in the appendix.  Just
make sure it goes at the end of the appendix.]

Robot name: Zeta

	Zeta is the sixth Greek letter, nestled between Epsilon and Eta.
	Moreover, Zeta is an acronym with the following expansion and
	meaning:

	Zero Energy Thermonuclear Assembly:  A British fusion device in
	which scientists observed fusion neutrons in 1958.  They were
	erroneously considered to be thermonuclear (coming from particles
	with a Maxwellian velocity distribution) and were a cause for
	the initial optimism that fusion energy would be easy.  They
	were actually due to electromagnetic acceleration during a plasma
	instability, an effect which cannot be scaled up to produce
	useful energy.

	reference: http://www.pppl.gov/~rfheeter/fusion-faq/glossary/z.html

	sample usage: "Is Zeta finished yet?"

	pronounciation: Zay-ta.

Subsystem name - Interface: Gluon

	: a hypothetical neutral massless particle held to bind
	  together quarks to form hadrons

	reference: http://www.m-w.com/dictionary.htm

	sample usage: "I'll just read-in the appropriate signal from
	               the Gluon."

Subsubsystem name - Sensors: Neutrinos

	: an uncharged elementary particle that is believed to be
	  massless or to have a very small mass, that has any of three
	  forms, and that interacts only rarely with other particles

	reference: http://www.m-w.com/dictionary.htm

	sample usage: "The neutrinos have located the enemy!"

Subsubsystem name - emittor beacon: W+

	Responsible for weak (ie. non-nuclear), long-distance interactions.

	reference: http://math.ucr.edu/home/baez/physics/particle_zoo.html

	sample usage: "The W+ doesn't appear to be functioning correctly."

	pronounciation: open to interpretation?

Subsubsystem name - impact sensors: Theta-Ps

	Theta Pinch:  A fast-pulsed pinch device in which the external
	current imposed goes in the azimuthal/circumferential direction
	(generally in a solenoid) around a cylindrical plasma.  Use of
	a fast-rising solenoidal current causes a rapidly increasing
	axial magnetic field, which compresses and heats the plasma.
	MHD theory of the Theta Pinch is given in reference 6.

	reference: http://www.pppl.gov/~rfheeter/fusion-faq/glossary/t.html

	sample usage: "The Theta-Ps will notify us of collisions."

	pronounciation: Theta-Pee

Subsubsystem name - motor control circuit: Tachyon Controller

	tachyon: a hypothetical particle held to travel only faster than light

	reference: http://www.m-w.com/dictionary.htm

	sample usage: "Cap'n, I need more power for the tachyon controller."

Subsystem name - electro-mech: Baryon

	: any of a group of elementary particles (as nucleons)
	  that are subject to the strong force and are held to be a
	  combination of three quarks

	reference: http://www.m-w.com/dictionary.htm

	The baryon is what composes most of the matter that we see and
	feel.

	sample usage: "Don't worry, Joyce.  The baryon will hold
	               everything together."

Subsubsystem name - the Lexan base floor: Hadron

	Etymology: International Scientific Vocabulary hadr-
	           thick, heavy (from Greek hadros thick) + 2-on

	: any of the subatomic particles that are made up of quarks and are
	  subject to the strong force

	reference: http://www.m-w.com/dictionary.htm

	sample usage: "The motors are resting quietly on the Hadron."

Subsubsystem name - all electrical wiring: Muon

	: an unstable lepton that is common in the cosmic radiation near
	  the earth's surface, has a mass about 207 times the mass of
	  the electron, and exists in negative and positive forms

	reference: http://www.m-w.com/dictionary.htm

	sample usage: "Shnikeys!  It was working a minute ago...There must
	               be another breach in the Muon somewhere."

Subsubsystem name - the control program: Qubit

	[...] the quantum information content of any quantum system can
	be meaningfully measured as the minimum number of two-state
	systems, now called quantum bits or qubits, which would be needed
	to store or transmit the system's state with high accuracy.

	reference: http://www.qubit.org/intros/compSteane/qcintro.html

	sample usage: "WTF was the Qubit thinking when it did that!?!"


-- 
Signature withheld by request of author.