Recommandation opportuniste de trajectoires pour l’accomplissement de tâches dans les systèmes crowdsourcing

André Sales Fonteles; Sylvain Bouveret; Jérôme Gensel

Document numérique 2016/1 Vol. 19

Article de revue

Recommandation opportuniste de trajectoires pour l’accomplissement de tâches dans les systèmes crowdsourcing

Pages 103 à 126

Algorithmes

Tableau

Document avec texte en français, incluant "Problème de Recommandation de Trajectoires Utiles [PRTU]" et une description technique.

Tableau

Table avec titre "TSP". Contient une entrée et une question sur un ensemble et une fonction de distance.

Algorithme 1

\begin{array} { l } { { \mathrm { E a r c e ~ i f i e ~ i m e n c t ~ i m e n c t ~ i n e n t i c e } } } \\ { { \mathrm { g a r c i m e s ~ i m e ~ i m e ~ i s ~ a n d ~ i m e n t ~ o r ~ } } } \\ { { \mathrm { t a r ~ s i m e ~ s ~ a r ~ i m e ~ } } } \\ { { \mathrm { a ~ g a r ~ s ~ a r ~ a ~ c ~ c o r ~ } } } \\ { { \mathrm { a ~ f ~ c r ~ a ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ a l o r ~ } } } \\ { { \mathrm { a ~ f ~ c r ~ a ~ c ~ c ~ c ~ c ~ c ~ c ~ a l o r ~ } } } \\ { { \mathrm { a ~ f ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ a l o r ~ } } } \\ { { \mathrm { a ~ b ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ c ~ ~ c ~ c ~ c ~ ~ c ~ ~ c ~ c ~ ~ c ~ ~ c ~ ~ c ~ ~ ~ c ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Algorithme proposé

Algorithme 2

Code de fonction en français avec des commentaires et des conditions logiques.

<div> <body> <div class="page"> <ul> <li>1 Fonction expand(T, s, tachesCand, u, position, T, la, Td, *meilleureT, 9)</li> </ul> <pre> <code>/+ le temps d'arrivé en s ne peut pas étre plus tot que Ti */ T = max((T + G.distance(position, l9)), T); 2 dTacheDestination = g.distance(l°, la); 3 /* vérifie si l'exécutant peut accomplir s et arrivera sadestinationfinaleavant l'échéance */ si T + 8*+ dTacheDestination ≤ Ta alors 4 /vérifie si l'exécutant peut arriver en s avant la fin de la fenetre de temps ￥ siT≤T2alors 5 /+ la trajectoire reste valide et s peut etre ajoutée. / position = 1; 6 T.ajouter(s, T); 7 8 T=T+; tachesCand = tachesCand.clonerO; 9 tachesCand = tachesCand -{s}; 10 11 peutEtendre = faux; /*essaied'étendreTrécursivementen ajoutant d' autres taches / 12 pour s' E tachesCand faire peutEtendre = peutEtendre OU expand(T.clonerO, s', 13 tachesCand, u, position, T, ld, Td, *meilleureT, G); 14 fin 15 si NON peutEtendre alors 16 si *meilleureT =null OU u(T) > u(*meilleureT) alors 17 *meilleureT = T; 18 fin 19 fin 20 retournervrai; 21 fin 22 sinon tachesCand = tachesCand -{s}; 23 24 fin 25 retournerfaux; 26 fin</code> </pre> </div> </body> </div>

Fonction expand

Figure 1

Description de l'image par IA : Graphe de tâches avec durées et fenêtres temporelles, incluant une table avec tâches, intervalles horaires, durées et utilités.

L'image montre un diagramme de tâches avec des nœuds et des arêtes numérotées. Les nœuds sont étiquetés A, B, C, Io et Id. Les arêtes entre les nœuds sont numérotées de 3 à 8, indiquant des relations ou des durées entre les tâches. Sous le diagramme, il y a un tableau avec quatre colonnes : Tâche, Fenêtre de temps, Durée et Utilité. Le tableau liste les tâches A, B et C avec leurs fenêtres de temps respectives, leurs durées et leurs utilités. Par exemple, la tâche A a une fenêtre de temps de 1:00 PM à 1:50 PM, une durée de 5 minutes et une utilité de 5. La tâche B a une fenêtre de temps de 1:00 PM à 2:10 PM, une durée de 15 minutes et une utilité de 5. La tâche C a une fenêtre de temps de 1:30 PM à 2:40 PM, une durée de 10 minutes et une utilité de 6.

Configuration de tâches dans un exemple d’instance de PRTU

Figure 2

Description de l'image par IA : Arbre avec des cercles reliés par des flèches, certains cercles sont grisés.

L'image représente un diagramme en forme d'arbre avec des nœuds et des branches. Au sommet de l'arbre, il y a un nœud unique étiqueté "I". Ce nœud principal se divise en trois branches principales, chacune menant à un nœud étiqueté "A", "B", et "C". Chaque nœud principal ("A", "B", "C") se divise à nouveau en deux branches. Par exemple, le nœud "A" se divise en deux nœuds étiquetés "B" et "C". Le nœud "B" se divise en deux nœuds étiquetés "C" et "B". Le nœud "C" se divise en deux nœuds étiquetés "A" et "B". Les nœuds "B" et "C" se divisent également de manière similaire, créant une structure hiérarchique plus complexe. Certains nœuds à la fin des branches sont remplis de gris, indiquant peut-être une condition ou un état particulier. Par exemple, un nœud étiqueté "A" à la fin de la branche sous "C" est rempli de gris. L'image semble illustrer un espace de recherche de trajectoires, avec différentes branches représentant des chemins ou des itinéraires possibles.

Espace de recherche de trajectoires

Algorithme 3

Description de l'image par IA : début tableau 1re rangée B majuscule en normal a en normal t en normal r en normal i en normal c en normal t en normal h en normal a en normal c en normal i en normal n en normal t en normal a en normal n en normal e en normal t en normal e en normal d en normal e en normal P majuscule en normal r en normal e en normal T majuscule en normal U majuscule en normal 2e rangée S majuscule en normal o en normal t en normal i en normal c en normal opérateur point L majuscule en normal a en normal m en normal e en normal i en normal n en normal t en normal a en normal n en normal t en normal e en normal t en normal a en normal t en normal e en normal s en normal négatif c en normal r en normal e en normal t en normal i en normal n en normal e en normal t en normal r en normal o en normal u en normal v en normal e en normal 3e rangée t en normal a en normal t en normal i en normal c en normal t en normal a en normal s en normal i en normal n en normal e en normal c en normal t en normal a en normal t en normal e en normal t en normal r en normal a en normal n en normal t en normal e en normal égale c en normal r en normal e en normal s en normal t en normal a en normal t en normal e en normal t en normal e en normal parenthèse gauche suscrire G majuscule avec macron parenthèse droite point virgule 4e rangée 4 T majuscule en normal a en normal p en normal e en normal s en normal t en normal a en normal t en normal e en normal s en normal t en normal a en normal t en normal e en normal t en normal a en normal t en normal e en normal t en normal a en normal t en normal e en normal parenthèse gauche suscrire G majuscule avec macron parenthèse droite point virgule 5e rangée 4 T majuscule en normal a en normal p en normal e en normal t en normal a en normal t en normal a en normal t en normal e en normal t en normal a en normal t en normal e en normal t en normal a en normal t en normal a en normal t en normal e en normal parenthèse gauche suscrire G majuscule avec macron parenthèse droite point virgule 6e rangée 4 p en normal o en normal p en normal e en normal t en normal a en normal t en normal e en normal t en normal a en normal t en normal a en normal t en normal e en normal t en normal a en normal t en normal a en normal t en normal e en normal parenthèse gauche suscrire G majuscule avec macron parenthèse droite point virgule 7e rangée s en normal p en normal o en normal r en normal s appartient à suscrire epsilon avec macron parenthèse gauche suscrire epsilon avec macron parenthèse droite parenthèse gauche suscrire epsilon avec macron parenthèse droite suscrire epsilon avec macron c suscrire epsilon avec macron c suscrire epsilon avec macron 8e rangée s en normal barre verticale début tableau 1re rangée s en normal p en normal p en normal e en normal n en normal d en normal parenthèse gauche r en normal e en normal t en normal a en normal t en normal a en normal t en normal i en normal o en normal n en normal e en normal virgule s parenthèse droite point virgule 2e rangée 4 3e rangée 4 4e rangée suscrire epsilon avec macron 5e rangée suscrire epsilon avec macron 6e rangée suscrire epsilon avec macron 7e rangée suscrire epsilon avec macron 8e rangée suscrire epsilon avec macron 9e rangée suscrire epsilon avec macron 10e rangée suscrire epsilon avec macron fin tableau fin tableau

\begin{array} { l } { { \mathrm { B a t r i c ~ } \mathrm { t h a c i n t a n e ~ t e ~ d e ~ P r e ~ T U } } } \\ { { \mathrm { S o t i c ~ } \cdot \mathrm { L a ~ m e i n t a n t e ~ t a t e s ~ - c r e t i n e ~ t r o u v e } } } \\ { { \mathrm { t a t i c ~ t a s i n e c t a t e t r a n t e } = \mathrm { c r e s t a t e t e ~ } ( \bar { G } ) ; } } \\ { { \mathrm { 4 ~ T a p e s t a t e s t a t e t a t e t a t e ~ } ( \bar { G } ) ; } } \\ { { \mathrm { 4 ~ T a p e t a t a t e t a t e t a t a t e ~ } ( \bar { G } ) ; } } \\ { { \mathrm { 4 ~ p o p e t a t e t a t a t e t a t a t e ~ } ( \bar { G } ) ; } } \\ { { \mathrm { s p o r ~ } s \in \bar { \epsilon } ( \bar { \epsilon } ) ( \bar { \epsilon } ) \bar { \epsilon } c \bar { \epsilon } c \bar { \epsilon } } } \\ { { \mathrm { s ~ } \left| \begin{array} { l } { { \mathrm { s p p e n d ( r e t a t a t i o n e }, ~ s ) ; } } \\ { { \mathrm { 4 ~ } } } \\ { { \mathrm { 4 ~ } } } \\ { { \bar { \epsilon } } } \\ { { \bar { \epsilon } } } \\ { { \bar { \epsilon } } } \\ { { \bar { \epsilon } } } \\ { { \bar { \epsilon } } } \\ { { \bar { \epsilon } } } \\ { { \bar { \epsilon } } } \\ \end{array} \right. } } \\ \end{array}

Algorithme de l’heuristique gloutonne avec fenêtre de temps (GFT)

Algorithme 4

Description de l'image par IA : Code d'algorithme avec des instructions en français pour une heuristique de plus proche.

L'image montre un algorithme intitulé "Algorithme de l’heuristique au plus proche (PP)". Il s'agit d'un algorithme en pseudo-code utilisé dans le contexte de la Programmation par Recuit Simulé (PRTU). L'algorithme commence par initialiser un ensemble de positions et une trajectoire vide. Il définit ensuite une position de départ et un temps d'entrée. La boucle principale de l'algorithme itère sur les positions de l'ensemble, calculant un nouveau temps d'entrée basé sur la distance et la température actuelle. Si ce nouveau temps est inférieur au temps d'entrée actuel, la position est ajoutée à la trajectoire et mise à jour. Après la boucle, l'algorithme vérifie si la trajectoire est différente de la position de départ. Si c'est le cas, il met à jour le temps d'entrée et la position, puis ajoute la position à l'ensemble. L'algorithme se termine en retournant la trajectoire.

Algorithme de l’heuristique au plus proche (PP)

Figure 3

Description de l'image par IA : Diagram montrant une architecture de recommandation avec gestionnaire de contexte et algorithme PRTU.

L'image représente une architecture de référence pour l’emploi de la recommandation dans un système de gestion des données. Elle est divisée en plusieurs composants principaux : 1. **Base de Données** : Un composant en forme de cylindre bleu en haut de l'image, qui semble stocker des informations et des données. 2. **Gestionnaire de RTU (Recommandations de Trajectoires Utilisateurs)** : Un rectangle vert situé au centre droit de l'image. Ce gestionnaire reçoit des données de la base de données et interagit avec l'algorithme PRTU (Processus de Recommandation de Trajectoires Utilisateurs). 3. **Algorithme PRTU** : Un composant représenté par un rectangle vert en dessous du gestionnaire de RTU. Cet algorithme traite les données pour fournir des recommandations de trajectoires. 4. **Gestionnaire de Contexte** : Un rectangle blanc à gauche de l'image. Il interagit avec le gestionnaire de RTU en fournissant des notifications et des contextes. 5. **Exécutant** : Une icône de silhouette humaine en bas de l'image, qui reçoit des recommandations de trajectoires du gestionnaire de RTU. Les flèches montrent les interactions entre ces composants : - La base de données envoie des données de requêtes et des données de traces au gestionnaire de RTU. - Le gestionnaire de RTU reçoit des notifications du gestionnaire de contexte. - Le gestionnaire de RTU fournit des recommandations de trajectoires à l'exécutant. - Le gestionnaire de contexte envoie des contextes au gestionnaire de RTU. L'ensemble de l'architecture est encadré dans un cadre noir étiqueté "CMS" (système de gestion de contenu).

Architecture de référence pour l’emploi de la recommandation

Figure 4

Description de l'image par IA : Graphique comparant deux méthodes (exacte et brute) en fonction du nombre de tâches et du temps en millisecondes.

Comparaison entre notre approche et la force brute

Figure 5

Description de l'image par IA : Courbe montrant le temps d’exécution en millisecondes selon le nombre de tâches.

L'image représente un graphique en ligne montrant la relation entre le nombre de tâches et le temps d'exécution en millisecondes. L'axe des x est étiqueté "Nombre de tâches" et varie de 10 à 100. L'axe des y est étiqueté "Temps en millisecondes" et varie de 0 à 90. Le graphique montre une courbe exponentielle croissante, indiquant que le temps d'exécution augmente de manière significative à mesure que le nombre de tâches augmente. Les points de données sont marqués par des diamants bleus, et la courbe semble lisser les valeurs entre ces points. Pour un nombre de tâches inférieur à 50, le temps d'exécution reste relativement bas, mais au-delà de 50 tâches, le temps d'exécution commence à augmenter de manière plus rapide et plus prononcée, atteignant environ 80 millisecondes pour 100 tâches.

Temps d’exécution de notre algorithme

Figure 6

Description de l'image par IA : Graphique comparant les temps d’exécution en millisecondes de différents algorithmes selon le nombre de tâches.

L'image est un graphique comparant les temps d’exécution entre un algorithme exact et des heuristiques. L'axe des x est intitulé "Nombre de Tâches" et varie de 10 à 40. L'axe des y est intitulé "Temps en millisecondes" et va jusqu'à 1200 millisecondes. Trois séries de données sont représentées : 1. Une série bleue intitulée "Algorithme exact" montre une augmentation significative des temps d’exécution à mesure que le nombre de tâches augmente, atteignant environ 1200 millisecondes pour 40 tâches. 2. Une série rouge intitulée "GFT, EP, GU" reste relativement stable avec des temps d’exécution très bas, autour de 0 millisecondes, indépendamment du nombre de tâches. 3. Une série verte intitulée "PP, PV" suit également une tendance stable avec des temps d’exécution très bas, autour de 0 millisecondes, indépendamment du nombre de tâches. Les points de données pour les séries rouges et vertes sont très proches les uns des autres, indiquant des performances similaires et constantes.

Comparaison des temps d’exécution entre l’algorithme exact et les heuristiques (en utilisant [τo, τd] = 2 heures)

Figure 7

Description de l'image par IA : Graphique montrant les temps d’exécution en millisecondes pour différentes tâches, comparant deux séries de données.

L'image représente un graphique en ligne comparant les temps d'exécution de deux ensembles de tâches différentes. L'axe des x est intitulé "Nombre de Tâches" et varie de 10 à 40. L'axe des y est intitulé "Temps en millisecondes" et varie de 0 à 0,07. Deux séries de données sont présentées : 1. Une série en bleu, marquée par des losanges, représentant les heuristiques GFT, EP, GU. 2. Une série en rouge, marquée par des carrés, représentant les heuristiques PP, PV. La série bleue montre une augmentation progressive des temps d'exécution à mesure que le nombre de tâches augmente, passant d'environ 0,04 millisecondes à 0,06 millisecondes. La série rouge, en revanche, reste relativement stable autour de 0,03 millisecondes tout au long de l'augmentation du nombre de tâches. Les deux séries de données sont clairement distinctes, avec la série bleue toujours au-dessus de la série rouge sur l'ensemble de l'intervalle de tâches.

Temps d’exécution des heuristiques (en utilisant [τo, τd] = 2 heures)

Figure 8

Description de l'image par IA : Graphique comparant l'utilité moyenne de différentes heuristiques à l'utilité optimale selon le nombre de tâches.

L'image est un graphique comparant l'utilité moyenne fournie par différentes heuristiques à l'utilité optimale. L'axe des x représente le nombre de tâches, allant de 10 à 170. L'axe des y montre la comparaison en pourcentage de l'utilité optimale, allant de 0,00% à 120,00%. Six courbes distinctes sont tracées sur le graphique, chacune représentant une heuristique différente : 1. Exact (bleu) 2. GU (vert) 3. pp (orange) 4. PV (jaune) 5. EP (rouge) 6. GFT (violet) La courbe Exact reste constamment à 100,00%, indiquant une performance optimale. Les autres courbes montrent une diminution de l'utilité à mesure que le nombre de tâches augmente, avec des variations entre elles. La courbe GU commence autour de 80,00% et diminue progressivement. La courbe pp commence autour de 60,00% et suit une tendance similaire. La courbe PV commence autour de 50,00% et diminue également. Les courbes EP et GFT commencent autour de 40,00% et diminuent plus fortement que les autres. Les points de données sur chaque courbe sont marqués avec des symboles différents, indiquant les points spécifiques de mesure. Les erreurs ou écarts-types sont représentés par des barres d'erreur sur chaque point de données.

Comparaison entre l’utilité moyenne fournie par les heuristiques et l’utilité optimale

Compte personnel

Recommandation opportuniste de trajectoires pour l’accomplissement de tâches dans les systèmes crowdsourcing

Accès institutions

Toutes les institutions

Recommandation opportuniste de trajectoires pour l’accomplissement de tâches dans les systèmes crowdsourcing

Citer cet article

Accès institutions

Toutes les institutions