Comment puis-je trouver le chemin le plus court entre 100 cibles mobiles? (Démo en direct incluse)

Question

Contexte

Cette image illustre le problème :

Je peux contrôler le cercle rouge. Les cibles sont les triangles bleus. Les flèches noires indiquent la direction que les cibles vont suivre.

Je veux collecter toutes les cibles en un minimum de mouvements.

À chaque tour, je dois faire 1 pas vers la gauche, la droite, vers le haut ou vers le bas.

À chaque tour, les cibles feront également 1 pas selon les directions indiquées sur le tableau.

Démo

J'ai mis en place une démo jouable du problème ici sur Google appengine.

Je serais très intéressé si quelqu'un peut battre le score cible, car cela montrerait que mon algorithme actuel est sous-optimal. (Un message de félicitations devrait s'afficher si vous y parvenez!)

Problème

Mon algorithme actuel a une très mauvaise mise à l'échelle avec le nombre de cibles. Le temps augmente exponentiellement et pour 16 poissons, c'est déjà plusieurs secondes.

J'aimerais calculer la réponse pour des tailles de tableau de 32*32 et avec 100 cibles mobiles.

Question

Quel est un algorithme efficace (idéalement en Javascript) pour calculer le nombre minimal de mouvements pour collecter toutes les cibles?

Ce que j'ai essayé

Mon approche actuelle est basée sur la mémorisation mais elle est très lente et je ne sais pas si elle générera toujours la meilleure solution.

Je résous le sous-problème de "quel est le nombre minimal de mouvements pour collecter un ensemble donné de cibles et arriver à une cible particulière?".

Le sous-problème est résolu de manière récursive en examinant chaque choix pour la cible précédente à avoir visitée. Je suppose qu'il est toujours optimal de collecter le précédent sous-ensemble de cibles le plus rapidement possible puis de vous déplacer de la position où vous vous êtes arrêté à la cible actuelle le plus rapidement possible (bien que je ne sache pas si c'est une hypothèse valide).

Cela entraîne le calcul de n*2^n états, ce qui croît très rapidement.

Le code actuel est affiché ci-dessous :

var DX=[1,0,-1,0];
var DY=[0,1,0,-1]; 

// Retourne l'emplacement du poisson donné au temps t
function getPt(fish,t) {
  var i;
  var x=pts[fish][0];
  var y=pts[fish][1];
  for(i=0;i

`

Ce que j'ai considéré

Quelques options auxquelles j'ai réfléchi sont :

1. Mise en cache des résultats intermédiaires. Le calcul de distance répète beaucoup de simulations et les résultats intermédiaires pourraient être mis en cache.
   Cependant, je ne pense pas que cela empêcherait l'obtention d'une complexité exponentielle.

2. Un algorithme de recherche A* bien qu'il ne soit pas clair pour moi quelle heuristique admissible serait appropriée et à quel point cela serait efficace en pratique.

3. Enquêter sur de bons algorithmes pour le problème du voyageur de commerce et voir s'ils s'appliquent à ce problème.

4. Essayer de prouver que le problème est NP-difficile et donc déraisonnable de chercher une réponse optimale pour lui.

`

Answer 1

Avez-vous cherché dans la littérature? J'ai trouvé ces articles qui semblent analyser votre problème:

• "Suivi des cibles mobiles et le problème du voyageur voyageant non stationnaire": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.9940

• "Le problème du voyageur voyageant avec des cibles mobiles": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.6403

MISE À JOUR 1:

Les deux articles ci-dessus semblent se concentrer sur le mouvement linéaire pour la métrique euclidienne.

Answer 2

Méthode gloutonne

Une approche suggérée dans les commentaires est d'aller d'abord vers la cible la plus proche.

J'ai mis en place une version de la démo qui inclut le coût calculé via cette méthode gloutonne ici.

Le code est :

function greedyMethod(start_x,start_y) {
  var still_to_visit = (1<

``

Pour 10 cibles, la distance est d'environ deux fois supérieure à la distance optimale, mais parfois beaucoup plus (*4) et atteint parfois même l'optimum.

Cette approche est très efficace, donc je peux me permettre quelques cycles pour améliorer la réponse.

Ensuite, je envisage d'utiliser des méthodes de colonies de fourmis pour voir si elles peuvent explorer efficacement l'espace de la solution.

Méthode de colonie de fourmis

Une méthode de colonie de fourmis semble fonctionner remarquablement bien pour ce problème. Le lien dans cette réponse compare maintenant les résultats lors de l'utilisation des méthodes gloutonne et de la colonie de fourmis.

L'idée est que les fourmis choisissent leur itinéraire de manière probabiliste en fonction du niveau actuel de phéromone. Après chaque 10 essais, nous déposons des phéromones supplémentaires le long du chemin le plus court qu'elles ont trouvé.

function antMethod(start_x,start_y) {
  // First establish a baseline based on greedy
  var L = greedyMethod(start_x,start_y);
  var n = pts.length;
  var m = 10; // number of ants
  var numrepeats = 100;
  var alpha = 0.1;
  var q = 0.9;
  var t0 = 1/(n*L);

  pheromone=new Array(n+1); // entry n used for starting position
  for(i=0;i<=n;i++) {
    pheromone[i] = new Array(n);
    for(j=0;jbestc) {
              besti = i;
              bestc = c;
            }
          }
        }
        if (Math.random()>0.9) {
          thresh = totalh*Math.random();
          for(i=0;i

`

Résultats

Cette méthode de colonie de fourmis avec 100 répétitions de 10 fourmis est encore très rapide (37ms pour 16 cibles comparé à 3700ms pour la recherche exhaustive) et semble très précise.

Le tableau ci-dessous montre les résultats de 10 essais en utilisant 16 cibles :

   Gloutonne   Fourmis     Optimal
   46       29      29
   91       38      37
  103       30      30
   86       29      29
   75       26      22
  182       38      36
  120       31      28
  106       38      30
   93       30      30
  129       39      38

La méthode des fourmis semble significativement meilleure que la méthode gloutonne et souvent très proche de l'optimum.

` ``

Answer 3

Le problème peut être représenté en termes de Problème du Voyageur de Commerce Généralisé, puis converti en Problème du Voyageur de Commerce conventionnel. C'est un problème bien étudié. Il est possible que les solutions les plus efficaces au problème de l'OP ne soient pas plus efficaces que les solutions au TSP, mais ce n'est en aucun cas certain (je ne parviens probablement pas à tirer parti de certains aspects de la structure du problème de l'OP qui permettraient une solution plus rapide, comme sa nature cyclique). Dans tous les cas, c'est un bon point de départ.

Provenant de C. Noon & J.Bean, Une transformation efficace du Problème du Voyageur de Commerce Généralisé:

Le Problème du Voyageur de Commerce Généralisé (GTSP) est un modèle utile pour les problèmes impliquant des décisions de sélection et de séquence. La version asymétrique du problème est définie sur un graphe dirigé avec des nœuds N, des arcs de connexion A et un vecteur de coûts d'arc correspondants c. Les nœuds sont pré-groupés en m ensembles de nœuds mutuellement exclusifs et exhaustifs. Les arcs de connexion sont définis uniquement entre les nœuds appartenant à des ensembles différents, c'est-à-dire qu'il n'y a pas d'arcs intra-ensemble. Chaque arc défini a un coût d'arc correspondant non négatif. Le GTSP peut être formulé comme le problème de trouver un cycle d'arcs m de coût minimum qui inclut exactement un nœud de chaque ensemble de nœuds.

Pour le problème de l'OP :

• Chaque membre de N est l'emplacement particulier d'un poisson à un moment particulier. Représentez cela comme (x, y, t), où (x, y) est une coordonnée de grille, et t est le moment auquel le poisson sera à cette coordonnée. Pour le poisson le plus à gauche dans l'exemple de l'OP, les premiers de ceux-ci (basés sur 1) sont : (3, 9, 1), (4, 9, 2), (5, 9, 3) alors que le poisson se déplace vers la droite.
• Pour tout membre de N, laissez fish(n_i) renvoyer l'ID du poisson représenté par le nœud. Pour deux membres quelconques de N, nous pouvons calculer manhattan(n_i, n_j) pour la distance de Manhattan entre les deux nœuds, et time(n_i, n_j) pour le décalage temporel entre les nœuds.
• Le nombre de sous-ensembles disjoints m est égal au nombre de poissons. Le sous-ensemble disjoint S_i ne consistera que des nœuds pour lesquels fish(n) == i.
• Si pour deux nœuds i et j, fish(n_i) != fish(n_j) alors il y a un arc entre i et j.
• Le coût entre le nœud i et le nœud j est time(n_i, n_j), ou indéfini si time(n_i, n_j) < distance(n_i, n_j) (c'est-à-dire que l'emplacement ne peut pas être atteint avant que le poisson n'y arrive, peut-être parce qu'il est en arrière dans le temps). Les arcs de ce dernier type peuvent être supprimés.
• Un nœud supplémentaire devra être ajouté représentant l'emplacement du joueur avec des arcs et des coûts vers tous les autres nœuds.

Résoudre ce problème entraînerait ensuite une seule visite à chaque sous-ensemble de nœuds (c'est-à-dire qu chaque poisson est obtenu une fois) pour un chemin avec un coût minimal (c'est-à-dire un temps minimal pour que tous les poissons soient obtenus).

Le document décrit comment la formulation ci-dessus peut être transformée en un Problème classique du Voyageur de Commerce et résolue ou approximée par des techniques existantes. Je n'ai pas lu les détails mais un autre document qui le fait d'une manière qu'il proclame efficace est celui-ci.

Il y a des problèmes évidents de complexité. En particulier, l'espace des nœuds est infini ! Cela peut être atténué en ne générant que des nœuds jusqu'à un certain horizon temporel. Si t est le nombre de pas de temps pour générer des nœuds et f est le nombre de poissons, alors la taille de l'espace des nœuds sera t * f. Un nœud au temps j aura au plus (f - 1) * (t - j) arcs sortants (car il ne peut pas revenir en arrière dans le temps ou dans son propre sous-ensemble). Le nombre total d'arcs sera de l'ordre de t^2 * f^2 arcs. La structure des arcs peut probablement être nettoyée, pour tirer parti du fait que les trajectoires des poissons sont finalement cycliques. Les poissons répéteront leur configuration une fois tous les plus petits communs multiples de leurs longueurs de cycle, donc peut-être que ce fait peut être utilisé.

Je ne sais pas assez sur le TSP pour dire si c'est réalisable ou non, et je ne pense pas que cela signifie que le problème posé est nécessairement NP-difficile... mais c'est une approche pour trouver une solution optimale ou bornée.

Answer 4

Je pense qu'une autre approche serait :

• calculer le chemin des cibles - prédictif.
• puis utiliser diagrammes de Voronoi

Citation de Wikipedia :

En mathématiques, un diagramme de Voronoi est une manière de diviser l'espace en un certain nombre de régions. Un ensemble de points (appelés grains, sites ou générateurs) est spécifié à l'avance et pour chaque grain il y aura une région correspondante composée de tous les points plus proches de ce grain que de tout autre.

Donc, vous choisissez une cible, suivez son chemin pendant quelques étapes et définissez un point de grain à cet endroit. Faites de même avec toutes les autres cibles et vous obtenez un diagramme de Voronoi. En fonction de la région dans laquelle vous vous trouvez, déplacez-vous vers le point de grain correspondant. Voilà, vous avez attrapé le premier poisson. Répétez maintenant cette étape jusqu'à ce que vous les ayez tous attrapés.