Se déplacer avec des contraintes sur l'accélération Il s'agit en fait du projet de fin de module AlgoMob, à réaliser de préférence en binôme (mais c'est flexible). Ce projet comptera pour la moitié de la note de CC.
Travail à rendre
- Une ou plusieurs versions de la classe
Drone(une pour chaque algorithme que vous proposez). - Un rapport entre 2 et 5 pages, rédigé de préférence (mais ce n'est pas obligé) en LaTeX, expliquant comment fonctionne votre algorithme (ou vos algorithmes) et les choix conceptuels que vous avez fait.
Quand : vendredi 16 décembre à minuit (date décalée).
Barême (indicatif) : 10 points pour le score brut de votre algorithme (voir détail tout en bas), 6 points pour le rapport, et 4 points pour la beauté de votre algorithme (indépendamment de ses performances, les idées originales ou innovantes seront récompensées).
Meilleurs scores
Voici les meilleurs scores jusqu'à présent.
Jeu de cerise 1 (voir méthode distributeNodes1 ci-dessous)
| Score | Noms | Technique |
| ? | ? | ? |
Jeu de cerise 2 (voir méthode distributeNodes2 ci-dessous)
| Score | Noms | Technique |
| ? | ? | ? |
Jeu de cerise 3 (voir méthode distributeNodes3 ci-dessous)
| Score | Noms | Technique |
| ? | ? | ? |
Principe général
Les entités mobiles (drones, robots, etc.) ne peuvent échapper à une certaine inertie dans leurs mouvements. Il existe un modèle simple pour représenter ce type de contraintes, issu du jeu Vector Racer (qui se joue sur papier quadrillé). Dans ce jeu, une entité se déplace à chaque étape selon un certain vecteur. Par exemple, le vecteur (3,2) correspond à un déplacement de 3 cases vers la droite et 2 cases vers le haut. L'inertie est alors représentée par le fait que le vecteur ne peut changer que légèrement entre deux déplacements consécutifs (précisément, que d'une unité pour chaque dimension). Ainsi, il est impossible d'accélérer, freiner ou tourner brutalement.
Version continue
On peut généraliser ce principe aux espaces continus comme suit. À chaque étape, l'entité se déplace selon un vecteur (à valeurs réelles, cette fois). Entre deux déplacement, l'entité peut modifier son vecteur, mais à condition que le point cible du second déplacement soit proche de ce qu'il serait si le vecteur ne changeait pas. Ce principe est illustré dans la figure ci-dessous, où un drone cherche à rejoindre une destination $\large \times$ mais il a déjà un certain élan. Il pourra donc modifier sa trajectoire en ralentissant progressivement tout en commençant à tourner à droite, puis en réaccélérant vers la destination. Les positions autorisées à chaque étape sont représentées par des cercles (ici seules les bordures sont utilisées, mais l'intérieur du cercle est aussi valide, bien sûr).
Figure 1: Gestion de trajectoire avec contraintes d'accélération
Objectif du projet
Un certain nombre de cerises doivent être récupérées. On met à votre disposition un drone spécialisé dans la cueillette de cerise, initialement placé au centre de la zone. Ce drone est conçu pour respecter les contraintes d'accélération expliquées ci-dessus (les détails techniques seront donnés plus bas). Votre mission est de terminer la cueillette le plus rapidement possible, c'est à dire en utilisant le moins possible d'étapes. Un algorithme basique est fourni par défaut, mais il est très naïf et l'objectif est donc de l'améliorer. Son exécution est montrée dans la vidéo ci-dessous.
Vidéo 1: Cueillette de cerise avec contraintes d'accélération (algorithme basique à améliorer)
Matériel fourni
L'ensemble des classes fournies est opérationnel, il peut être exécuté tel quel en produisant un résultat similaire à la vidéo 1 ci-dessus. Les quatre classes sont :
- Classe
Cherry: un type de noeud très basique pour représenter les cerises. - Classe
VectorNode: un type de noeud qui implémente les contraintes d'accélération. - Classe
Drone: la classe de noeud qu'il faut modifier, elle hérite de VectorNode. - Classe
Competition: construction de la simulation (méthode main, etc.).
Le code de toutes ces classes est fourni ci-dessous. C'est dans la classe Drone que vous devez implémenter votre algorithme, qui consiste essentiellement à choisir, de manière répétée, le prochain mouvement à effectuer. Pour ce faire, la classe VectorNode (dont hérite votre drone) met à votre disposition une méthode TravelTo, qui garantit que les contraintes d'accélération sont respectées.
La méthode TravelTo
Tout mouvement doit se faire par l'intermédiaire de cette méthode. Vous n'avez pas besoin d'en comprendre le fonctionnement détaillé. En résumé, cette méthode mémorise le précédent mouvement (ou vecteur) et effectue le mouvement demandé si ce dernier est conforme aux contraintes d'accélération (figure de gauche ci-dessous). Si le point demandé n'est pas conforme (figure de droite), un mouvement est quand même effectué, mais il est généralement très sous-optimal pour atteindre le point demandé. Il est donc préférable de calculer vous même les points que vous souhaitez atteindre à chaque mouvement. Une fois le mouvement terminé, le callback onPointReached() est appelé et vous déterminez alors le mouvement suivant en rappelant travelTo(). L'exécution est donc une alternance de travelTo, onPointReached, travelTo, etc.
Figure 2: Comportement de la méthode `travelTo()`. Si le point demandé est autorisé (*c.à.d.* dans le cercle), alors le drone s'y rendra (Fig. de gauche). Sinon, il se rendra au point autorisé le plus proche du point demandé (Fig. de droite).
L'algorithme par défaut
La classe Drone fournie (code ci-dessous) propose un algorithme très basique pour récolter les cerises puis rentrer à son point de départ. Concernant l'ordre de visite des cerises, l'algorithme se contente de choisir la cerise suivante de manière arbitraire (getTopology().getNodes().get(0)) à chaque fois qu'une cerise est atteinte (nextCherry = null dans la méthode SensingIn()). Concernant l'optimisation des mouvements, il n'y en a pas non plus, l'algorithme se contente de se rapprocher le plus possible de la prochaine cerise à chaque mouvement, jusqu'à ce qu'elle soit atteinte (ce qui est une très mauvaise stratégie).
La classe Cherry
Voici le code de la classe Cherry. Cette classe n'est pas à modifier.
import io.jbotsim.core.Node;
import io.jbotsim.ui.icons.Icons;
public class Cherry extends Node {
@Override
public void onStart() {
disableWireless();
setIcon(Icons.CHERRY);
}
}La classe VectorNode
Voici le code de la classe VectorNode, qui implémente les contraintes d'accélération et dont la classe Drone hérite. Cette classe n'est pas à modifier. Notez que la constante DEVIATION représente le rayon du cercle de modification autorisée dans la trajectoire (cercles représentés sur les figures ci-dessus). Une grande valeur permettrait de modifier sa trajectoire avec très peu d'inertie. La visibilité de cette variable est public pour que vous puissiez la prendre en compte dans vos calculs de trajectoire (si besoin).
import io.jbotsim.core.Node;
import io.jbotsim.core.Point;
public abstract class VectorNode extends Node {
public static final double DEVIATION = 20.0;
public Point vector = new Point(0, 0);
private Point nextPoint;
private double speed;
public void travelTo(Point requestedTarget) {
Point projection = add(getLocation(), vector);
Point requestedChange = sub(requestedTarget, projection);
if (len(requestedChange) < DEVIATION) {
nextPoint = requestedTarget;
}else{
Point allowedChange = mul(requestedChange, DEVIATION / len(requestedChange));
nextPoint = add(projection, allowedChange);
}
setDirection(nextPoint);
vector = sub(nextPoint, getLocation());
speed = len(vector)/10.0; // move split into 10 rounds (smooth rendering)
}
@Override
public void onClock() {
if (nextPoint != null){
if (distance(nextPoint) > speed) {
move(speed);
}else{
setLocation(nextPoint);
nextPoint = null;
onPointReached(getLocation());
}
}
}
/* Called when the next point is reached (to be overridden) */
public abstract void onPointReached(Point point);
/* Vector operations */
private static double len(Point p) {
return (new Point(0,0)).distance(p);
}
private static Point mul(Point p, double a) {
return (new Point(p.getX()*a, p.getY()*a));
}
private static Point sub(Point p1, Point p2) {
return (new Point(p1.getX()-p2.getX(), p1.getY()-p2.getY()));
}
private static Point add(Point p1, Point p2) {
return (new Point(p1.getX()+p2.getX(), p1.getY()+p2.getY()));
}
}La classe Drone
Voici le code de la classe Drone. Toutes les modifications que vous devez faire sont dans cette classe.
import io.jbotsim.core.Node;
import io.jbotsim.core.Point;
import io.jbotsim.ui.icons.Icons;
public class Drone extends VectorNode {
Point nextCherry;
@Override
public void onStart() {
super.onStart();
setSensingRange(20);
setIcon(Icons.DRONE);
setIconSize(14);
onPointReached(getLocation());
}
@Override
public void onPointReached(Point point) {
if (nextCherry == null)
if (getTopology().getNodes().size() > 1)
nextCherry = getTopology().getNodes().get(0).getLocation();
else
nextCherry = new Point(500, 400);
travelTo(nextCherry);
}
@Override
public void onSensingIn(Node node) {
if (node instanceof Cherry) {
getTopology().removeNode(node);
nextCherry = null;
}
}
}La classe Competition
Voici le code de la classe Competition qui contient la méthode main(). Cette classe n'est pas à modifier.
import io.jbotsim.core.Node;
import io.jbotsim.core.Point;
import io.jbotsim.core.Topology;
import io.jbotsim.core.event.ClockListener;
import io.jbotsim.ui.JViewer;
import io.jbotsim.ui.painting.BackgroundPainter;
import io.jbotsim.ui.painting.UIComponent;
import java.awt.Graphics2D;
public class Competition implements ClockListener, BackgroundPainter{
Topology tp;
Integer score;
Point startPoint = new Point(500, 400);
public Competition() {
tp = new Topology(1000, 800);
tp.pause();
distributeNodes(tp);
tp.addClockListener(this);
JViewer jv = new JViewer(tp);
jv.getJTopology().addBackgroundPainter(this);
tp.start();
}
public void distributeNodes(Topology tp){
for (int i=0; i<20; i++) {
double x = Math.random() * 800 + 100;
double y = Math.random() * 600 + 100;
tp.addNode(x, y, new Cherry());
}
tp.addNode(500, 400, new Drone());
}
public boolean hasReturned(Drone drone){
if (drone.getLocation().equals(startPoint) &&
drone.vector.distance(new Point(0,0))<VectorNode.DEVIATION) {
return true;
}else
return false;
}
@Override
public void onClock() {
if (tp.getNodes().size() == 1) {
Drone drone = (Drone) tp.getNodes().get(0);
if (hasReturned(drone)) {
score = (int) Math.ceil(tp.getTime() / 10.0);
tp.pause();
}
}
}
@Override
public void paintBackground(UIComponent c, Topology tp) {
if (score != null) {
Node drone = tp.getNodes().get(0);
String s = "Score: " + score;
Graphics2D g2d = (Graphics2D) c.getComponent();
g2d.drawString(s, (int) drone.getX() + 30, (int) drone.getY() + 30);
}
}
public static void main(String[] args) {
new Competition();
}
}Évaluation de votre algorithme
L'évaluation de votre algorithme sera faite sur 10 distributions différentes de 20 cerises, dont 7 seront aléatoires (comme dans le code donné par défaut dans la classe Competition) et 3 sont données ci-dessous. Le score retenu sera la moyenne des scores sur ces 10 exécutions. Le score d'une exécution correspond au nombre d'appels que vous faites à TravelTo jusqu'à ce que vous ayez terminé votre mission (à savoir récolter toutes les cerises puis rentrer à la base).
Trois ensembles de cerise fixés
import io.jbotsim.core.Topology;
public class NodeDistributions {
static public void distributeNodes1(Topology tp){
tp.addNode(559.0, 638.0, new Cherry());
tp.addNode(166.0, 569.0, new Cherry());
tp.addNode(538.0, 455.0, new Cherry());
tp.addNode(887.0, 544.0, new Cherry());
tp.addNode(500.0, 605.0, new Cherry());
tp.addNode(565.0, 527.0, new Cherry());
tp.addNode(533.0, 206.0, new Cherry());
tp.addNode(824.0, 421.0, new Cherry());
tp.addNode(127.0, 189.0, new Cherry());
tp.addNode(889.0, 394.0, new Cherry());
tp.addNode(240.0, 518.0, new Cherry());
tp.addNode(618.0, 290.0, new Cherry());
tp.addNode(754.0, 128.0, new Cherry());
tp.addNode(105.0, 113.0, new Cherry());
tp.addNode(595.0, 576.0, new Cherry());
tp.addNode(818.0, 576.0, new Cherry());
tp.addNode(736.0, 593.0, new Cherry());
tp.addNode(223.0, 227.0, new Cherry());
tp.addNode(380.0, 370.0, new Cherry());
tp.addNode(407.0, 556.0, new Cherry());
}
static public void distributeNodes2(Topology tp){
tp.addNode(154.0, 284.0, new Cherry());
tp.addNode(534.0, 321.0, new Cherry());
tp.addNode(456.0, 556.0, new Cherry());
tp.addNode(589.0, 487.0, new Cherry());
tp.addNode(144.0, 404.0, new Cherry());
tp.addNode(471.0, 651.0, new Cherry());
tp.addNode(344.0, 328.0, new Cherry());
tp.addNode(898.0, 126.0, new Cherry());
tp.addNode(670.0, 686.0, new Cherry());
tp.addNode(133.0, 187.0, new Cherry());
tp.addNode(831.0, 386.0, new Cherry());
tp.addNode(753.0, 201.0, new Cherry());
tp.addNode(580.0, 637.0, new Cherry());
tp.addNode(708.0, 558.0, new Cherry());
tp.addNode(245.0, 248.0, new Cherry());
tp.addNode(411.0, 516.0, new Cherry());
tp.addNode(627.0, 380.0, new Cherry());
tp.addNode(158.0, 574.0, new Cherry());
tp.addNode(176.0, 442.0, new Cherry());
tp.addNode(430.0, 296.0, new Cherry());
}
static public void distributeNodes3(Topology tp){
tp.addNode(104.0, 523.0, new Cherry());
tp.addNode(842.0, 577.0, new Cherry());
tp.addNode(108.0, 120.0, new Cherry());
tp.addNode(443.0, 551.0, new Cherry());
tp.addNode(356.0, 289.0, new Cherry());
tp.addNode(629.0, 661.0, new Cherry());
tp.addNode(429.0, 115.0, new Cherry());
tp.addNode(668.0, 399.0, new Cherry());
tp.addNode(368.0, 579.0, new Cherry());
tp.addNode(862.0, 267.0, new Cherry());
tp.addNode(529.0, 656.0, new Cherry());
tp.addNode(646.0, 423.0, new Cherry());
tp.addNode(241.0, 619.0, new Cherry());
tp.addNode(661.0, 176.0, new Cherry());
tp.addNode(116.0, 442.0, new Cherry());
tp.addNode(476.0, 350.0, new Cherry());
tp.addNode(448.0, 130.0, new Cherry());
tp.addNode(437.0, 444.0, new Cherry());
tp.addNode(736.0, 420.0, new Cherry());
tp.addNode(638.0, 575.0, new Cherry());
}
}Remerciements: à David Renault et Vincent Klein pour les discussions enrichissantes autour de ce problème; David m'a également aidé à développer une première version de la classe VectorNode.