Difference between revisions of "Dynamic Clustering"

From Robowiki
Jump to navigation Jump to search
m (minor cleanup)
m (update math)
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 +
{{Wikipedia|K-nearest neighbor algorithm}}
 +
{{Youtube|eqlPbtO3rQY}}
 
'''Dynamic clustering''' is a technique to find entries in your [[:Category:Log-Based Algorithms|log]] similar to the current situation. Essentially, it is a [[wikipedia:K-nearest neighbor algorithm|K-nearest neighbor algorithm]], and not actually [[wikipedia:Cluster analysis|clustering]] at all. Despite this misnomer, the term "Dynamic Clustering" has stuck with the Robocode community.
 
'''Dynamic clustering''' is a technique to find entries in your [[:Category:Log-Based Algorithms|log]] similar to the current situation. Essentially, it is a [[wikipedia:K-nearest neighbor algorithm|K-nearest neighbor algorithm]], and not actually [[wikipedia:Cluster analysis|clustering]] at all. Despite this misnomer, the term "Dynamic Clustering" has stuck with the Robocode community.
  
The idea is to record a "state" (or termed "situation") for each entry in your log. The state can contain any data that you deem valuable, such as [[lateral velocity]], [[advancing velocity]], or [[enemy distance]]. Save this along with your data. Then to use the data, you find a "distance" between current state and past states. Distance can be [[wikipedia:Euclidean distance|Euclidian]] (<code>sqrt(sqr(dist1 - dist2) + sqr(lat1 - lat2))</code>) or another way, such as [[wikipedia:Manhattan distance|Manhattan distance]]. Find some number of entries with the lowest distance, and use them for targeting, movement, or whatever you like.
+
The idea is to record a "state" (or termed "situation") for each entry in your log. The state can contain any data that you deem valuable, such as [[lateral velocity]], [[advancing velocity]], or [[enemy distance]]. Save this along with your data. Then to use the data, you find a "distance" between current state and past states. Distance can be [[wikipedia:Euclidean distance|Euclidian]] (<math>\sqrt{(dist1 - dist2)^2 + (lat1 - lat2)^2 + \cdots}</math>) or another way, such as [[wikipedia:Manhattan distance|Manhattan distance]] (<math>|dist1 - dist2| + |lat1 - lat2| + \cdots</math>). Find some number of entries with the lowest distance, and use them for targeting, movement, or whatever you like.
  
The earliest method doing this was by iterating through the log and calculating the distance for each log entry.  If you have a large log this is very slow. More recently [[Kd-Tree|Kd-Trees]] have been used. [[User:Corbos|Corbos]] was the first one to mention them on the [[Robowiki]], which caught the interest of [[User:Chase-san|Chase-san]] and [[User:Simonton|Simonton]]. As of now, Simonton's Kd-tree implementation is one of the faster ones.
+
The earliest method doing this was by iterating through the log and calculating the distance for each log entry.  If you have a large log this is very slow. More recently [[kd-tree]]s have been used. [[User:Corbos|Corbos]] was the first one to mention them on the [[RoboWiki]], which caught the interest of [[User:Chase-san|Chase-san]] and [[User:Simonton|Simonton]].
 
   
 
   
 
=== Bot using this technique ===
 
=== Bot using this technique ===
Line 14: Line 16:
  
 
== See Also ==
 
== See Also ==
 +
* [[Dynamic Clustering Tutorial]]
 
* [[Visit Count Stats]]
 
* [[Visit Count Stats]]
* [[Kd-Tree]]
+
* [[kd-tree]]
  
 
[[Category:Log-Based Algorithms]]
 
[[Category:Log-Based Algorithms]]

Revision as of 01:09, 30 August 2009

Wikipedia
Youtube
Youtube has a video of Dynamic Clustering in action: click here to watch

Dynamic clustering is a technique to find entries in your log similar to the current situation. Essentially, it is a K-nearest neighbor algorithm, and not actually clustering at all. Despite this misnomer, the term "Dynamic Clustering" has stuck with the Robocode community.

The idea is to record a "state" (or termed "situation") for each entry in your log. The state can contain any data that you deem valuable, such as lateral velocity, advancing velocity, or enemy distance. Save this along with your data. Then to use the data, you find a "distance" between current state and past states. Distance can be Euclidian (<math>\sqrt{(dist1 - dist2)^2 + (lat1 - lat2)^2 + \cdots}</math>) or another way, such as Manhattan distance (<math>|dist1 - dist2| + |lat1 - lat2| + \cdots</math>). Find some number of entries with the lowest distance, and use them for targeting, movement, or whatever you like.

The earliest method doing this was by iterating through the log and calculating the distance for each log entry. If you have a large log this is very slow. More recently kd-trees have been used. Corbos was the first one to mention them on the RoboWiki, which caught the interest of Chase-san and Simonton.

Bot using this technique

See Also