Range Search

From Robowiki
Revision as of 14:13, 8 August 2011 by Nat (talk | contribs) (some cleanup; let me know if you don't like it.)
Jump to navigation Jump to search

Range search is a data analysis algorithm, which is very similar to k-NN. The main difference is that k-NN increases area (sphere or hypercube) until it contains required amount of data points, but range search do not do it.

How it works

Record state (aka situation, turn snapshot, etc.) with some set of attributes (velocity, acceleration, x, y, etc.). When you need in data, calculate some hypercube with center in current situation. For example current situation is {velocity = 8, acceleration = 0, x = 200, y = 200}, then hypercube can be described as set if intervals {[6;8], [0;0], [180; 220], [180, 220]}. Then iterate through all data and select these points, which are contained by this hypercube. Then use this data points for targeting, movement or elsewhere

Advantages

The main advantage against knn algorithm is getting only corresponding data. k-NN algorithm can get too many not corresponding data, until gets k data points or get too little corresponding data, if k is much lesser, then data points around current situation

Illustrations

Legend:

  • little black dots - data points
  • big red dots - current situation
  • red areas - area of data points which used for data analysis
K nearest neighbours algorithm Range search algorithm Visit count stats algorithm
k-nearest neighbours algorithm Range search algorithm Visit Count Stats algorithm

See also