Menu
▾
▴
[Jason-developers] SF.net SVN: jason: [1276] trunk/applications/jason-team/src/java
|
From: <jom...@us...> - 2008-04-28 17:39:03
|
Revision: 1276
http://jason.svn.sourceforge.net/jason/?rev=1276&view=rev
Author: jomifred
Date: 2008-04-28 10:38:52 -0700 (Mon, 28 Apr 2008)
Log Message:
-----------
jason team: new cluster alg
Modified Paths:
--------------
trunk/applications/jason-team/src/java/jia/Vec.java
trunk/applications/jason-team/src/java/jia/herd_position.java
trunk/applications/jason-team/src/java/test/TestBasicHerding.java
Modified: trunk/applications/jason-team/src/java/jia/Vec.java
===================================================================
--- trunk/applications/jason-team/src/java/jia/Vec.java 2008-04-27 18:25:28 UTC (rev 1275)
+++ trunk/applications/jason-team/src/java/jia/Vec.java 2008-04-28 17:38:52 UTC (rev 1276)
@@ -8,7 +8,7 @@
import arch.LocalWorldModel;
-public final class Vec implements Cloneable {
+public final class Vec implements Cloneable, Comparable<Vec> {
// immutable fields (for a immutable object)
public final double x,y;
@@ -67,22 +67,7 @@
public Vec newMagnitude(double r) {
return new Vec(r*Math.cos(t), r*Math.sin(t));
}
- @Override
- public boolean equals(Object o) {
- if (o == null) return false;
- if (o == this) return true;
- if (o instanceof Vec) {
- Vec v = (Vec)o;
- return (getX() == v.getX()) && (getY() == v.getY());
- }
- return false;
- }
-
- public Object clone() {
- return this; // it is an immutable object, no need to create a new one
- }
-
/**
* Provides info on which octant (0-7) the vector lies in.
* 0 indicates 0 radians +- PI/8 1-7 continue CCW.
@@ -106,7 +91,34 @@
return ((int)(temp/(Math.PI/2))%4);
}
+
+ @Override
+ public boolean equals(Object o) {
+ if (o == null) return false;
+ if (o == this) return true;
+ if (o instanceof Vec) {
+ Vec v = (Vec)o;
+ return (getX() == v.getX()) && (getY() == v.getY());
+ }
+ return false;
+ }
+
+ public int compareTo(Vec o) {
+ if (r > o.r) return 1;
+ if (r < o.r) return -1;
+ return 0;
+ }
+ public Object clone() {
+ return this; // it is an immutable object, no need to create a new one
+ }
+
+
+ @Override
+ public String toString() {
+ return getX() + "," + getY();
+ }
+
//
// Useful static methods for list of vecs
//
@@ -128,6 +140,7 @@
return r;
}
+ /*
public static List<Vec> cluster(List<Vec> vs, int maxstddev) {
vs = new ArrayList<Vec>(vs); // result vectors in the cluster
Vec mean = Vec.mean(vs);
@@ -142,6 +155,7 @@
}
return vs;
}
+ */
public static Vec mean(List<Vec> vs) {
if (vs.isEmpty())
@@ -168,9 +182,4 @@
return new Vec( Math.sqrt(x), Math.sqrt(y));
}
-
- @Override
- public String toString() {
- return getX() + "," + getY();
- }
}
Modified: trunk/applications/jason-team/src/java/jia/herd_position.java
===================================================================
--- trunk/applications/jason-team/src/java/jia/herd_position.java 2008-04-27 18:25:28 UTC (rev 1275)
+++ trunk/applications/jason-team/src/java/jia/herd_position.java 2008-04-28 17:38:52 UTC (rev 1276)
@@ -12,6 +12,8 @@
import jason.environment.grid.Location;
import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Iterator;
import java.util.List;
import java.util.logging.Level;
@@ -34,7 +36,7 @@
public static final double maxStdDev = 3;
public static final int agDistanceInFormation = 4;
-
+
public enum Formation {
one { int[] getDistances() { return new int[] { 0 }; } },
two { int[] getDistances() { return new int[] { sd, -sd }; } },
@@ -47,14 +49,20 @@
private static final int sd = agDistanceInFormation/2;
};
+ LocalWorldModel model;
+
+ public void setModel(LocalWorldModel model) {
+ this.model = model;
+ }
+
@Override
public Object execute(TransitionSystem ts, Unifier un, Term[] args) throws Exception {
try {
CowboyArch arch = (CowboyArch)ts.getUserAgArch();
- LocalWorldModel model = arch.getModel();
+ model = arch.getModel();
if (model == null)
return false;
- Location agLoc = model.getAgPos(arch.getMyId());
+ Location agLoc = model.getAgPos(arch.getMyId());
// identify the formation id
Formation formation = Formation.six;
@@ -67,20 +75,20 @@
// update GUI
if (arch.hasGUI())
- setFormationLoc(model, formation);
+ setFormationLoc(formation);
// if the return is a location for one agent
if (args.length == 3) {
- Location agTarget = getAgTarget(model, formation, agLoc);
+ Location agTarget = getAgTarget(formation, agLoc);
if (agTarget != null) {
return un.unifies(args[1], new NumberTermImpl(agTarget.x)) &&
un.unifies(args[2], new NumberTermImpl(agTarget.y));
} else {
- ts.getLogger().info("No target! I am at "+agLoc+" places are "+formationPlaces(model, formation));
+ ts.getLogger().info("No target! I am at "+agLoc+" places are "+formationPlaces(formation));
}
} else {
// return all the locations for the formation
- List<Location> locs = formationPlaces(model, formation);
+ List<Location> locs = formationPlaces(formation);
if (locs != null) {
ListTerm r = new ListTermImpl();
ListTerm tail = r;
@@ -91,7 +99,7 @@
}
return un.unifies(args[1], r);
} else {
- ts.getLogger().info("No formation possible! I am at "+agLoc+" places are "+formationPlaces(model, formation));
+ ts.getLogger().info("No formation possible! I am at "+agLoc+" places are "+formationPlaces(formation));
}
}
} catch (Throwable e) {
@@ -100,9 +108,9 @@
return false;
}
- public Location getAgTarget(LocalWorldModel model, Formation formation, Location ag) throws Exception {
+ public Location getAgTarget(Formation formation, Location ag) throws Exception {
Location r = null;
- List<Location> locs = formationPlaces(model, formation);
+ List<Location> locs = formationPlaces(formation);
if (locs != null) {
for (Location l : locs) {
if (ag.equals(l) || // I am there
@@ -118,9 +126,9 @@
return r;
}
- public void setFormationLoc(LocalWorldModel model, Formation formation) throws Exception {
+ public void setFormationLoc(Formation formation) throws Exception {
model.removeAll(WorldModel.FORPLACE);
- List<Location> locs = formationPlaces(model, formation);
+ List<Location> locs = formationPlaces(formation);
if (locs != null) {
for (Location l : locs) {
if (model.inGrid(l)) {
@@ -130,7 +138,7 @@
}
}
- private List<Location> formationPlaces(LocalWorldModel model, Formation formation) throws Exception {
+ private List<Location> formationPlaces(Formation formation) throws Exception {
List<Vec> cows = new ArrayList<Vec>();
for (Location c: model.getCows()) {
cows.add(new Vec(model, c));
@@ -138,8 +146,14 @@
if (cows.isEmpty())
return null;
- cows = Vec.cluster(cows, 2); // find center/clusterise
+ //cows = Vec.cluster(cows, 2); // find center/clusterise
+ cows = cluster(cows, WorldModel.cowPerceptionRatio);
+ List<Location> clusterLocs = new ArrayList<Location>();
+ for (Vec v: cows) {
+ clusterLocs.add(v.getLocation(model));
+ }
+
Vec mean = Vec.mean(cows);
int stepsFromCenter = (int)Math.round(Vec.max(cows).sub(mean).magnitude())+1;
//Vec max = Vec.max(cows);
@@ -167,7 +181,7 @@
Location l = findFirstFreeLocTowardsTarget(agTarget, mean.add(agsTarget), initAgTS, dist, model);
//System.out.println(" = "+dist+" result "+l);
if (l != null)
- r.add(pathToNearCow(model, l));
+ r.add(pathToNearCow(l, clusterLocs));
/*
Location lastloc = null;
@@ -207,9 +221,9 @@
return l; //ref.getLocation(model); //target.add(ref).getLocation(model);
}
- private Location pathToNearCow(LocalWorldModel model, Location t) {
+ private Location pathToNearCow(Location t, List<Location> cluster) {
Location near = null;
- for (Location c: model.getCows()) {
+ for (Location c: cluster) {
if (near == null || t.maxBorder(c) < t.maxBorder(near))
near = c;
}
@@ -226,6 +240,59 @@
return t;
}
+ public static List<Vec> cluster(List<Vec> cows, int maxDist) {
+ /*
+ Vs = set of all seen cows (sorted by distance to the centre of cluster)
+ Cs = { the cow near to the center of Vs }
+
+ add = true
+ while (add)
+ add = false
+ for all v in Vs
+ if (some cow in Cs sees v)
+ move v from Vs to Cs
+ add = true
+ */
+ Vec mean = Vec.mean(cows);
+ List<Vec> vs = new ArrayList<Vec>();
+ // place all cows in ref to mean
+ for (Vec v: cows)
+ vs.add(v.sub(mean));
+
+ Collections.sort(vs);
+
+ List<Vec> cs = new ArrayList<Vec>();
+ if (!vs.isEmpty())
+ cs.add(vs.remove(0));
+
+ boolean add = true;
+ while (add) {
+ add = false;
+ Iterator<Vec> i = vs.iterator();
+ while (i.hasNext()) {
+ Vec v = i.next();
+
+ Iterator<Vec> j = cs.iterator();
+ while (j.hasNext()) {
+ Vec c = j.next();
+ if (c.sub(v).magnitude() < maxDist) {
+ cs.add(v);
+ i.remove();
+ add = true;
+ break;
+ }
+ }
+ }
+ }
+
+ List<Vec> r = new ArrayList<Vec>();
+ // place all cows in ref to 0,0
+ for (Vec v: cs)
+ r.add(v.add(mean));
+ return r;
+ }
+
+
/*
public Location nearFreeForAg(LocalWorldModel model, Location ag, Location t) throws Exception {
// run A* to get the path from ag to t
Modified: trunk/applications/jason-team/src/java/test/TestBasicHerding.java
===================================================================
--- trunk/applications/jason-team/src/java/test/TestBasicHerding.java 2008-04-27 18:25:28 UTC (rev 1275)
+++ trunk/applications/jason-team/src/java/test/TestBasicHerding.java 2008-04-28 17:38:52 UTC (rev 1276)
@@ -1,10 +1,10 @@
package test;
import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
import jason.environment.grid.Location;
import java.util.ArrayList;
+import java.util.Collections;
import java.util.List;
import jia.Search;
@@ -70,7 +70,7 @@
}
@Test
- public void testVect() {
+ public void testVec() {
scenario1();
//assertEquals(new Vec(6,7), cow.add(cowboy));
//assertEquals(new Location(6,42), cow.add(cowboy).getLocation(model));
@@ -80,6 +80,22 @@
Vec v = new Vec(3,2);
assertEquals(v, v.newAngle(v.angle()));
}
+
+ @Test
+ public void testVecSort() {
+ scenario1();
+
+ List<Vec> cowsl = new ArrayList<Vec>();
+ for (int i=0; i<cows.length; i++) {
+ cowsl.add(cows[i]);
+ }
+ Collections.sort(cowsl);
+ assertEquals(new Vec(0,1), cowsl.get(0));
+ assertEquals(new Vec(4,8), cowsl.get(1));
+ assertEquals(new Vec(6,7), cowsl.get(2));
+ assertEquals(new Vec(5,10), cowsl.get(3));
+ assertEquals(new Vec(5,30), cowsl.get(4));
+ }
@Test
public void testCowsRepMat() throws Exception {
@@ -136,9 +152,9 @@
}
// find center/clusterise
- cowsl = Vec.cluster(cowsl, 2);
- Vec stddev = Vec.stddev(cowsl, Vec.mean(cowsl));
- assertTrue(stddev.magnitude() < 3);
+ cowsl = herd_position.cluster(cowsl, WorldModel.cowPerceptionRatio);
+ //Vec stddev = Vec.stddev(cowsl, Vec.mean(cowsl));
+ assertEquals(3, cowsl.size());
Vec mean = Vec.mean(cowsl);
assertEquals(new Vec(5,8), mean);
@@ -149,30 +165,33 @@
int stepsFromCenter = (int)Math.round(Vec.max(cowsl).sub(mean).magnitude())+1;
assertEquals(3, stepsFromCenter);
- Location byIA = new herd_position().getAgTarget(model, Formation.one, cowboy.getLocation(model));
+ herd_position hp = new herd_position();
+ hp.setModel(model);
+
+ Location byIA = hp.getAgTarget(Formation.one, cowboy.getLocation(model));
assertEquals(new Location(6,38), byIA);
- byIA = new herd_position().getAgTarget(model, Formation.six, cowboy.getLocation(model));
+ byIA = hp.getAgTarget(Formation.six, cowboy.getLocation(model));
assertEquals(new Location(6,39), byIA);
// add an agent in 6,39
model.add(WorldModel.AGENT, 6,39);
- byIA = new herd_position().getAgTarget(model, Formation.six, cowboy.getLocation(model));
+ byIA = hp.getAgTarget(Formation.six, cowboy.getLocation(model));
assertEquals(new Location(5,38), byIA);
// add an agent in 5,38
model.add(WorldModel.AGENT, 5,38);
- byIA = new herd_position().getAgTarget(model, Formation.six,cowboy.getLocation(model));
+ byIA = hp.getAgTarget(Formation.six,cowboy.getLocation(model));
assertEquals(new Location(7,42), byIA);
// add an agent in 7,42
model.add(WorldModel.AGENT, 7,42);
- byIA = new herd_position().getAgTarget(model, Formation.six,cowboy.getLocation(model));
+ byIA = hp.getAgTarget(Formation.six,cowboy.getLocation(model));
assertEquals(new Location(4,38), byIA);
// add an agent in 4,38
model.add(WorldModel.AGENT, 4,38);
- byIA = new herd_position().getAgTarget(model, Formation.six,cowboy.getLocation(model));
+ byIA = hp.getAgTarget(Formation.six,cowboy.getLocation(model));
assertEquals(null, byIA);
// add an agent in 5,37
@@ -185,7 +204,19 @@
public void moveCows3() throws Exception {
scenario2();
model.add(WorldModel.ENEMY, 11,48);
- Location byIA = new herd_position().getAgTarget(model, Formation.one, cowboy.getLocation(model));
+
+ List<Vec> cowsl = new ArrayList<Vec>();
+ for (int i=0; i<cows.length; i++) {
+ cowsl.add(cows[i]);
+ }
+
+ cowsl = herd_position.cluster(cowsl, WorldModel.cowPerceptionRatio);
+ assertEquals(9, cowsl.size());
+
+ herd_position hp = new herd_position();
+ hp.setModel(model);
+
+ Location byIA = hp.getAgTarget(Formation.one, cowboy.getLocation(model));
assertEquals(new Location(11,49), byIA);
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
