Navigation | May 11, 1997 | $1.50 Sundays |
You may prefer the summary.
[ May 11, 1997, mikeBot press ]
The micro-rover Sojourner will reportatly use navigation technology first demonstrated
in mikeBot, say NASA sources. "mikeBot selects navigation targets based on
distance and need. Soon, though, these formulas will be determined by a Genetic
Algorithm (GA), giving mikeBot optimal target-selection formulas," says Mike.
Also, observations indicate mikeBot will target whatever firecontrol is targeting, unless ammo/health need is paramount. There is no BSP-based navigation yet, although it is in the works. "A directed graph will be made from the BSP-tree leaves. mikeBot will make as many links as he can upon map load, and the rest will be made dynamically as mikeBot goes through the |
level. He will save the graph on exit for use again later," says Mike of the planned
navigation upgrades. The directed graph will enable the use of well-known (and optimal)
shortest-path algorithms to navigate to distant targets. Unreachable targets can be easily
discarded, as well (or, more likely, will be run straight towards in hopes of finding more
directed-graph links).
The newest version of mikeBot can determine what all entities are quickly and easily, using nothing more than a bit test. How this will be incorporated into Sojourner when it is already en route to Mars is a mystery, which Pathfinder insiders were not quick to alleviate...
|
genetic algorithm to be used |
I plan on using a GA (genetic algorithm) to "breed" better target-selection parameters into mikeBot's navigation.I will represent a formula for each different target (health,shells,nails,cells,rockets,armour, and each weapon) by a five-level complete binary tree. (see figure 1) Then, each tree will be encoded into a bit-string. The nodes of the tree can have only four different values (+, -, /, *), so two bits will suffice (+ = 00, - = 01, / = 10, * = 11). Each of the first four levels is composed only of nodes, so these will require 2 + 4 + 8 + 16 = 30 bits to represent them. Each leaf can have the value of one of the targets (health, etc...) or a number. I will use 8 bits for each leaf, which will represent an unsigned integer. If the value is 255, it is actually health, 254 is shells, etc. So, since there are 16 leafs in the bottom level, this will require 16 bytes, or 128 bits. So, i will require a total of 20 bytes of information (with two bits not used, since the nodes only need 30 bits, not 32) for each formula. And, with a formula for each target type, I will need a total of 12 formulas for each genotype. (see the example in figure 2) Using the "packet" storage method (instead of, say, a byte for each node) means every bit is meaningfull (well, except two) so presumably the eveolution will be faster. I may also try using three parents instead of two, so there is more crossover...
To determine fitness, each genotype will be used to control target-selection for ten minutes. Then, the formula frags / numberOfPlayers will be used to determine fitness. So, if one genotype gets 10 frags against 5 players in the ten minutes, it will get a fitness of 2.
The top two genotypes will breed to produce 10 offspring, which will make up the next generation. They will breed by "crossing-over" for each formula: a random bit will be choosen from the 158 bits which make up the gene for each formula, and all bits before that bit will come from one parent, all bits after it will come from the other. There will be no mutation.
Eventually, the theory goes, good target-selection parameters will be achieved. When a binary is released, I will provide a way for people to submit a generation of genes, especially if it is a few generations old...stay tuned.
Figure 1: A complete binary tree
of five levels. A circle is a leaf,
an oval is a node.
Figure 2: The bit-encoded form of the tree on the
left. The first 30 bits are for the nodes, the
last 128 bits (in hex for space...) are for the
leaves. The formula represented is:
health + 20
(the first two bits are 00)
Subsumtion Architecture to be used |
This "Subsumtive Architecture" was first demonstrated by Terry Brooks at the MIT AI lab.This will mean: mikeBot will have simulated forward, left and right bump-sensors. These will be on if a wall or lava is a certain distance in front or to his sides. Then, he will have a number of behaviours to select from:
LAVA-STOP This will stop if imminent lava-dunking is about to occur.
AVOID This will try to avoid projectiles.
AVOID WALL This will turn away from walls. (and lava)
MOVE AT TARGET This will turn toward his nav target.
AVOID LINE-OF-SIGHT This will turn away from mbfire's target's facing.
CIRCLE-STRAFE This will circle around the nav target (if it is a player and range is closeish) The different behaviours will can supress each other, if they are higher in the heiarchy (i.e. since AVOID-WALL is more important than MOVE AT TARGET, it can suppress the output of MOVE AT TARGET) Also, some behaviours will supress themselves depenging of health/ammo levels (i.e. if health is high, avoiding line-of-sight is a waste of time)
mike warren welcomes your
comments and suggestions
Fully-autonomous
![]()
client-side quake botBest experienced with
![]()
Click here to start.Proud member of
![]()
The Bot Author's Guild