Vous travaillez tout l’été ou l’heure des vacances n’est pas encore au rendez-vous ? Pas de panique, vous trouverez dans cet article de quoi vous détendre. Que diriez-vous tout d’abord de tester une méthode infaillible pour retrouver Charlie ? Découvrez vite ci dessous les analyses spatiales du scientifique Randal Oslon et ses algorithmes.
Where is Charlie ?
Source : Google Image
Vous avez dit, Charlie ?
Certains le connaissent aussi sous le nom de Wally ou Waldo… Charlie est un personnage issu de la série de livre-jeux britannique, créée par Martin Handford. Vêtu d’un bonnet et d’un sweat short à rayures blanches, l’objectif est, dans chacune des illustrations des livres, de retrouver le personnage caché.
Source : Google Image
Chaque illustration s’étend sur une double-page, dans laquelle un décor massif permet à Charlie de se fondre dans la masse et de se dissimuler derrière de nombreux détails. Que diriez-vous de vous mettre à l’épreuve et de tenter, grâce à la méthode suivante proposée, de confirmer ou non la méthode infaillible de recherche trouvée par Randal Olson ?
Docteur Randal Olson est un spécialiste en intelligence artificielle, en apprentissage automatique et en data visualisation. Directeur Data-Scientist chez Life Epigenetics, Inc (Portland, Oregan, USA), il tient un blog en parallèle de son activité professionnelle.
Ce blog présente un ensemble de projets qu’il réalise, pour son propre plaisir et pour la science. Ses projets relèvent des champs de la data visualisation et du machine learning. L’objectif de cette plateforme est de promouvoir l’échange entre les scientifiques du domaine et de donner des clés aux prochaines générations de chercheurs
Du machine learning à la « géographie-informatique »
Un des articles du Docteur Randal est notamment une proposition pour rechercher Charlie dans l’ensemble des illustrations des livres, grâce à l’usage de l’apprentissage automatique.
Le machine learning est un champ d’étude de l’intelligence artificielle qui a pour ambition de permettre à une machine de résoudre des tâches difficiles ou problématiques, que l’homme ne pourrait résoudre seul. L’apprentissage automatique doit conduire la machine à concevoir, analyser et développer des méthodes pour trouver des solutions par des moyens algorithmiques, grâce à l’utilisation et le traitement de données statistiques. Dans cette mesure, l’apprentissage automatique repose sur un processus systématique qui permet de gagner en efficacité et en temps.
Pour s’amuser, Randal Oslon s’est interrogé sur l’usage du machine learning dans la recherche d’une méthode pour trouver Charlie le plus rapidement possible. A travers l’étude des différentes localisations de Charlie, l’algorithme utilisé devait permettre de proposer une méthode optimisant le temps de recherche sur chaque illustration. Le but est d’étudier les tendances de Charlie dans le choix de ses cachettes.
Randy Olson a choisi d’approcher le problème comme un vendeur commercial qui voudrait optimiser ses tournées. Ainsi, l’enjeu était de déterminer un trajet entre les différentes positions de Charlie pour établir un chemin guidant le regard à travers les probables localisation du personnage.
- Collecte des données
Dans un premier temps, Olson a commencé par récupérer l’ensemble des coordonnées géographiques de Charlie. Parmi les sept livres, Charlie s’est caché 68 fois. De manière générale, une illustration s’étend sur une double page. Chaque position de Charlie est ainsi définie par 4 variables : numéro du livre, de page, coordonnée X, coordonnée Y.
Source : Randal S. Olson – Jupyter Notebook Viewer – Computing the optimal path for finding Waldo
Le graphique suivant rend compte des 68 positions de Charlie, toutes éditions confondues. A chaque point correspond une position. Cette représentation spatiale des positions de Charlie doit permettre de procéder à des analyses statistiques étudiant les distances entre chaque point et les tendances à la répartition dans l’espace.
Source : Randal S. Olson – Jupyter Notebook Viewer – Computing the optimal path for finding Waldo
- Analyse statistique
Il a ensuite utilisé la méthode statistique de Parzen-Rosenblatt, également connue sous le nom de méthode d’estimation par noyau de densité. Cette méthode d’analyse statistique permet d’obtenir une représentation graphique des probables zones de cachette sur la double page. A partir d’un nuage de points, où chaque point est la représentation de la localisation de Charlie, il s’agit de constater les zones où Charlie est présent le plus de fois dans l’ensemble des livres.
Source : Randal S. Olson – Jupyter Notebook Viewer – Computing the optimal path for finding Waldo
A partir des graphiques obtenus, Olson a ainsi pu identifier trois tendances dans la localisation de Charlie.
- Charlie ne se trouve jamais dans le coin en haut à gauche de l’illustration
- Il se trouve rarement sur les bordures de l’illustration
- Le personnage ne se trouve jamais en bas de la page de droite
Source : Randal S. Olson (Computing the optimal path for finding Waldo – Jupyter Notebook Viewer) – montage : Serin
A partir de ces premiers résultats, l’objectif était alors de proposer une méthode guidant le regard dans la double page vers les zones les plus probables de localisation. Cela signifie que les prochaines recherches devaient permettre à Olson d’établir un itinéraire. Cet itinéraire, par l’étude des distances entre chaque position possible, devait aboutir à un trajet qui couvrirait les différentes zones de la page. Il devait particulièrement éviter les retours en arrière, considérant qu’ils seraient une perte de rentabilité dans la recherche.
Plus précisément, le chemin serait donc déterminé par l’agencement idéal des 68 points recensés. Cet agencement permet le passage d’un point à un autre en maximisant la distance parcourue et minimisant le temps de recherche.
- L’algorithme génétique pour les problèmes d’optimisation
Cependant, les mesures statistiques permettent d’identifier environ 2,48×10^96 possibilités de cheminement… ce qui, à l’échelle de la vie humaine, serait impossible à étudier, même si tous les cerveaux étaient rassemblés sur la tâche. C’est pourquoi Randal Olson a opté pour l’utilisation d’un algorithme génétique. Celui-ci permet d’obtenir une solution approchée à un problème d’optimisation en un temps raisonnable, notamment lorsqu’il n’y a pas de méthode exacte ou que la solution est inconnue. Utilisé avec le langage Python, l’algorithme est paramétré de manière à ce qu’il remanie constamment une solution en ne gardant que le meilleur de celle-ci. Ainsi, chaque possibilité est étudiée par l’algorithme et n’est conservée que si elle est meilleure que la précédente obtenue.
Le chemin est cependant trop complexe pour être mémorisé. Alors, Olson a également tenté de tirer des leçons de son algorithme, de la même manière qu’il avait tiré des conclusions des représentations graphiques obtenues précédemment.
- Le bas de la page de gauche est un endroit idéal pour commencer
- Le quart supérieur de la page de droite est un endroit clé
- Il faut ensuite chercher Charlie dans la partie inférieure de la moitié de la page de droite. D’abord sur le quart de droite, puis sur le quart de gauche
Source : Randal S. Olson – Jupyter Notebook Viewer – Computing a optimal path for finding Waldo
Si Charlie n’a toujours pas été trouvé, cela signifie que vous êtes tombés sur une image dite « atypique ». Charlie se trouve alors très probablement au milieu de la double page ou sur les coins supérieurs à gauche et à droite de la double page.
Résultats
Randal Olson a testé le chemin sur l’ensemble des illustrations du premier livre de la série. Seules quatre positions de Charlie n’ont pas été trouvées en moins de 10 secondes.
Ces quatre exceptions s’expliquent par des illustrations « atypiques ». Cela signifie qu’elles différent du modèle général d’illustration. Le chemin ne s’applique donc pas pour les exceptions. Olson constate d’ailleurs qu’il est encore plus déconcertant que de ne pas trouver Charlie à la fin du chemin que de faire demi-tour et de tenter de faire le chemin à l’envers.
Vous voulez peut-être tester vous-même la méthode proposée par Randal ? Fouillez vos bibliothèques ou courez vite dans votre librairie la plus proche… Charlie ne demande qu’à être trouvé ! Vous pourriez non seulement vérifier les résultats et le chemin du Docteur Olson, mais également vous plonger dans le code de l’algorithme, que Randal a gentiment laissé accessible sur son site… les plus ardents chercheurs pourrez d’ailleurs s’amuser à adapter le code pour d’autres problèmes similaires…
Et pour cause ! Quelques semaines plus tard, Randal Olson, à partir de son code pour retrouver Charlie, en a proposé une nouvelle utilisation. Cette fois-ci, l’optimisation est au service de la planification d’un road trip.
Des localisations. Des chemins. Et des distances. Optimiser un road trip
Les temps de vacances vous donnent des envies de voyage ? Rester plongés dans les livres-jeux de Charlie, à siroter une orangeade et à prendre le soleil… Cela ne vous ressemble pas ? Vous aimez partir à l’aventure, découvrir de nouveaux lieux et organiser vos vacances ? Cet article est aussi pour vous, rassurez-vous.
Cette fois, ce n’est pas la position de Charlie qui nous intéresse, mais celle des différents lieux à visiter d’une zone géographique. Vous pouvez récupérer des listes préétablies des 50 merveilles à voir aux Etats-Unis, des 24 villes européennes à ne pas manquer, ou établir votre propre liste.
Le road trip à travers les USA pour Randal Olson
Randal a constitué par exemple une liste de 50 lieux (réserves naturelles, parcs nationaux, sites historiques et monuments nationaux) à visiter aux Etats-Unis. L’objectif était donc de déterminer un chemin permettant de minimiser le temps de transport et maximiserait les temps de visites.
D’un point de vue méthodologique, la récupération des coordonnées géographiques est liée à l’utilisation du service cartographique en ligne Google Maps. Créé par Google, il possède différentes fonctionnalités, notamment celle de représentation cartographique des lieux, mais propose aussi la création d’itinéraires. Google Maps API, une interface de programmation fournie par Google Maps, permet l’interaction des programmes les uns avec les autres. Elle rend notamment possible la personnalisation d’une carte grâce à l’utilisation d’un programme algorithmique.
Pour répondre à sa problématique d’optimisation de trajet, Randal Oslon a donc dû écrire un petit script calculant la distance parcourue à travers les différentes positions choisies. Avec une liste de 50 lieux, cela conduisait cependant à obtenir 2 450 possibilités de directions. Manuellement,la tâche serait un peu longue à effectuer. C’est la raison pour laquelle, comme pour la recherche de Charlie, Randal a à nouveau choisi l’approche d’un vendeur commercial. Cette fois, l’organisation de la liste des lieux à visiter devait conduire à établir un trajet permettant de passer par tous les lieux, suivant un ordre, sans revenir en arrière, et ayant la plus petite distance totale parcourue.
Au total, 3×10^64 possibilités sont comptabilisées. L’utilisation d’un algorithme génétique a permis de créer un itinéraire de 13 699 miles (soit 22 046 km). Sans trafic, Google Maps calcule un temps de transport de 224 heures (environ 9.33 jours). Il faudrait compter environ 3 mois pour réaliser le parcours en temps réel, avec les aléas du trafic et les temps de visites et de repos.
Et si vous aussi, vous pouviez planifier votre trajet ?
Grâce à la mise en ligne de son algorithme, vous pourriez donc tout à fait reproduire l’exercice. Ainsi vous pourrez planifier votre propre voyage.
Vous devez vous munir de la bibliothèque Python. Installez les packs pandas et google maps grâce à la fonction pip.
Chacune des localisations que vous choisissez doit avoir une adresse. Celles-ci doivent être conformes aux adresses Googles Maps. Si les adresses ne sont pas connues par Google Maps, vous vous exposez à des risques d’erreurs. L’algorithme pourrait même être incapable de répondre à votre demande. En effet, l’analyse se fonde sur l’utilisation des services de Google. Ainsi, les adresses doivent être formatées pour être reconnues par le service Google Maps. Vous devez également vous munir d’une clé API, permettant d’enregistrer le script dans l’API Google Maps.
Pour pouvoir mettre en marche la matrice des distances de Google Maps API, il faut également définir les paramètres. Ils doivent permettre à Google Maps de recherche les plus petites distances possibles entre chaque point. Cela implique d’avoir défini préalablement le moyen de transport utilisé, pour que Google Maps puisse déterminer les routes à emprunter. L’important est de déterminer un point de départ, d’arrivée, un mode de transport et qualifier les unités de mesures.
Source : Randal S. Olson – Jupyter Notebook Viewer – Computing the optimal road trip across the U.S
Pour visualiser le raod trip, Randal Oslon propose d’utiliser la bibliothèque JavaScript proposée par Google Maps. Celle de Python est moins adaptée.
Source : Randal S. Olson – Jupyter Notebook Viewer – Computing the optimal road trip across the U.S
Face au résultat, ne tardez pas. Vous pouvez reprendre le code et y inscrire vos propres paramètres. Partez vite à l’aventure !
Bibliographie
Randal S. Olson, « Here’s Waldo : Computing the optimal search strategy for finding Waldo », 03/02/2015 [En ligne] : http://www.randalolson.com/2015/02/03/heres-waldo-computing-the-optimal-search-strategy-for-finding-waldo
Randal S. Olson, « Computing the optimal road trip accross Europe », 10/03/2015 [En ligne] : http://www.randalolson.com/2015/03/10/computing-the-optimal-road-trip-across-europe/
Randal S. Olson, « Computing the optimal road trip accross Europe », 08/03/2015 [En ligne] : http://www.randalolson.com/2015/03/08/computing-the-optimal-road-trip-across-the-u-s/
Thibault Prévost, « Voici le road trip optimal pour découvrir l’Europe », Konibi, février 2015 [En ligne] : http://www.konbini.com/fr/tendances-2/road-trip-optimal-decouvrir-europe/
Script en ligne de l’algorithme Computing the optimal road trip accross the U.S : https://github.com/rhiever/Data-Analysis-and-Machine-Learning-Projects/blob/master/optimal-road-trip/Computing%20the%20optimal%20road%20trip%20across%20the%20U.S..ipynb
Script en ligne de l’algorithme Computing the optimal path for finding Waldo : http://nbviewer.jupyter.org/github/rhiever/Data-Analysis-and-Machine-Learning-Projects/blob/master/wheres-waldo-path-optimization/Where%27s%20Waldo%20path%20optimization.ipynb
Goldberg, D.E. & Holland, J.H. Machine Learning (1988) 3: 95. https://doi.org/10.1023/A:102260201918