Editing WikiTargeting/Code

Robo Home | Changes | Preferences | AllPages

<B>SCHEMATICS</B>

<pre>
+----------------------------------------------------------------+
| MyRobot ------ Node ------ Leaf ------ Bin                     |
|         \           \           \                              |
|          \           \           ----- Log -----< Observation  |
|           \           \                               |        |
|            \           \                          Situation    |
|             \           \                                      |
|              \           - Splitter ------< Node(recursive)    |
|               \                                                |
|                Recursionlevel                                  |
+----------------------------------------------------------------+
</pre>
(for some reason this schema gets warbled... could a Wiki expert look at it and get it right?) 
* Eh, no expertise needed, just a nice border will do! --(19/1/2006) [[Nfwu]]

<B>PSEUDOCODE</B>

<pre>
Class MyRobot
{
	Node root = new Node();
	RecursionLevel level = new Recursionlevel();

processWave()
	{
		Observation o = new Observation(Situation s, int GuessFactor);
		level.reset();
		root.addObservation(o, level);
	}

getGuessFactor(Situation s)
	{
		level.reset();
		root.getGuessFactor(s, level);
	}
}

Class Node
{
	Leaf leaf = new Leaf();
	Splitter splitter = null;

int getGuessFactor(Situation s, RecursionLevel level, double Distance)
	{
		if(leaf==null)
		{
			return Splitter.getGuessFactor(s, level)	//this node is not a leaf. continue recursion.
		}
		else
		{
			return leaf.getGuessFactor(Distance)
		}
		
	}

addObservation(Observation o, RecursionLevel level)	
	{
		if(leaf==null)
		{
			Splitter.addObservation(o, level)		//this node is not a leaf. continue recursion.
		}
		else
		{
			Leaf.add(o);
			if(leaf.size() >= 40)
			{
				if(splitter == null) splitter = new Splitter();
				if(splitter.split(leaf, level))	//splitter.split returns true if successful
				{
						// this nodes is no longer a leaf node. save memory space by deleting unused objects
					leaf.discard();
					leaf = null;
				}
			}
		}
	}

getPeakFactor()
	{
		return leaf.getPeakFactor();
	}

clear()
	{
		leaf.clear();
	}
}

Class RecursionLevel
{
	int level;
	int min[numDimensions]; //inclusive
	int max[numDimensions]; //exclusive

reset()
	{
		level = o;
		for(i=0;i<numDimensions;i++)
		{
			min[i] = 0;
			max[i] = 127;
		}
	}

getSplitValue(int SplitDimension)
	{
		return (min[SplitDimension] + max[SplitDimension]) / 2.0D;
	}

branchLow (int SplitDimension)
	{
		max[SplitDimension] = getSplitValue(SplitDimension);
	}

branchHigh (int SplitDimension)
	{
		min[SplitDimension] = getSplitValue(SplitDimension);
	}
}

Class Leaf
{
	Log log     = new Log();
	Bin nodeBin = new Bin();
	
	int getGuessFactor(double Distance)
	{
		nodeBin.findBestIndex(Distance);
	}

add(Observation o)
	{
		log.add(o);
		nodeBin.add(o.getGF());
	}

getPeakFactor()
	{
		double Distance = log.getAverageDistance();	//assume the distance is the average distance of all observations
		return nodeBin.getPeakFactor(Distance);
	}

int size()
	{
		return log.size();
	}

discard()
	{
		log = null;	
		nodeBin = null;
	}

clear()
	{
		log.clear();
		nodeBin.clear();
	}
}

Class Splitter
{
	Node LChild = new Node();
	Node HChild = new Node();
	int SplitDimension;

int getGuessFactor(Situation s, Recursionlevel level)	
	{
		if(s.getDimension(SplitDimension) < level.getSplitValue(SplitDimension))
		{
			level.diveLow(SplitDimension);
			LChild.getGuessFactor(s, level);
		}
		else
		{
			level.diveHigh(SplitDimension);
			HChild.getGuessFactor(s, level);
		}
	}

addObservation(Observation o, Recursionlevel level)
	{
		if(o.getDimension(SplitDimension) < level.getSplitValue(SplitDimension))
		{
			level.diveLow(SplitDimension);
			LChild.addObservation(o, level);
		}
		else
		{
			level.diveHigh(SplitDimension);
			HChild.addObservation(o, level);
		}
	}

spawnChildren(List Log, int Dimension, int SplitValue, Node LChild, Node HChild)
	{
		for(j=0;j<Log.size();j++)
		{
			Observation o = Log.get(j);
			if(o.getDimension(i) < SplitValue)
			{
				L.addObservation(o);
			}
			else
			{
				H.addObservation(o);
			}
		}
	}

boolean split(Leaf parent, Recursionlevel level) 			//this function is called by the Node when it has enough Observations to justify splitting the Node up.
	{
		int BestPeakTotal = parent.getPeakFactor(); 			//children need to exceed parent's peak factor
		int BestDim = -1;
		int SplitValue;
		for(i=0; i<numDimensions; i++)					//iterate over all dimensions and remember the most efficient dimension for splitting
		{
			SplitValue = level.getSplitValue(i);
			spawnChildren(parent.Log, i, SplitValue, LChild, HChild);			//temporarily split the parent log into two child nodes
			if((LChild.getPeakFactor() + HChild.getPeakFactor()) > BestPeakTotal)		//check how this split performs
			{
				BestDim = i;
				BestPeakTotal = LChild.getPeakFactor() + HChild.getPeakFactor();
			}
			LChild.clear();
			HChild.clear();
		}
		If(BestDim > -1)									//if a good splitting dimension is found, make it permanent
		{
			SplitDimension = BestDim;
			SplitValue = level.getSplitValue(SplitDimension);
			spawnChildren(parent.Log, SplitDimension, SplitValue, LChild, HChild);		//permanently split the parent log into two child nodes
			return true;
		}
		else
		{
			return false;
		}
	}
}

Class Bin
{
	numBins = 75;

int bin[numBins];

add (int GF)
	{
		bin[GF]++;
	}

clear()
	{
		for(i=0; i<numBins; i++)
		{
			bin[i] = 0;
		}
	}

int calcBotwidth()
	{
		//formula see Locke, botwidth is half the bot's width, expressed in GF indices
	}

getPeakFactor(double Distance)	
	{
			//first find the best index, considering bot width
		int botwidth = calcBotwidth(Distance);
		int index = findBestIndex(botwidth);
			//then, using this index, count the pure visits, considering bot width
		int PeakFactor = 0;
		for(i=(index-botwidth+1);i<(index+botwidth);i++)
		{
			if(i<0) i=0;
			if(i>=numBins) i=numBins;
			PeakFactor += bin[i];
		}
	}

int findBestIndex(double Distance)
	{
		int botwidth = calcBotwidth(Distance);
		int specialbin[numBins];
		for(index=0; index<numBins; index++)	
		{
			int imin = index-botwidth+1;
			if(imin<0) imin=0;
			int imax = index+botwidth;
			if(imax>=numBins) imax=numBins-1;
			for(i=imin;i<imax;i++)
			{
				specialbin[index] += bin[i];
			}
			
		}
		int bestIndex=0;
		int bestValue=0;
		for(index=0; index<numBins; index++)	
		{
			if(bestValue < specialbin[index]) 
			{
				bestIndex = index;
				bestValue = specialbin[index];
			}
		}
		/*
		TO DO: IN CASE OF "PLATEAU" FIND MIDDLE INDEX. SEE LOCKE FOR CODE.
		*/
		return bestIndex;
	}
}

Class Log
{
	List Log = new List();

add(Observation o)
	{
		Log.add(o);
	}

Observation get(int index)
	{
		return (Observation)Log.get(index);
	}

int size()
	{
		return Log.size();
	}

double getAverageDistance()
	{	
		int Total, Counter;
		for(i=0; i<size(); i++)
		{
			COunter++;
			Total += (get(i)).getDimension(x); //x = dimension that represents distance
		}
		return (double)Total / (double)Counter;
	}
}

Class Observation
{
	Situation s;
	int GuessFactor;

getGF()
	{
		return GuessFactor;
	}

getDimension(int d)
	{
		return s.getDimension(d);
	}
}

Class Situation
{
	int Dimensions[numDimensions];

getDimension(int d)
	{
		return Dimensions[d];
	}
}
</pre>

Summary:
Consciousness check: 9 - 3 =
This change is a minor edit. Send email notification that WikiTargeting/Code has been changed.
(Visit Preferences to set your user name.)

View other revisions
Robo Home | WikiTargeting | Changes | Preferences | AllPages