Brevet FR3117242A1 — publié le 20220610

TITRE : Procédé et dispositif d’allocation de tâches entre agents L’invention concerne un procédé d’allocation de tâches entre agents pour exécution de chaque tâche par un agent d’un ensemble d’agents formé de A agents, A étant un entier strictement positif, les tâches appartenant à un ensemble de tâches formé de T tâches à exécuter par au moins une partie des agents, T étant un entier strictement positif, le procédé étant mis en œuvre par au moins une unité de calcul d’un processeur. Ce procédé comporte, pour au moins une solution d’allocation des tâches à exécuter entre au moins une partie desdits agents, dite solution évaluée, l’obtention (50, 52) d’une liste de T indices d’agents définissant la solution évaluée, chaque indice d’agent correspondant à l’agent alloué pour effectuer la tâche dont l’indice est fourni par le rang dans ladite liste d’agents ; le calcul (54), à partir de la liste de T indices d’agents, d’un ou plusieurs pétales de tâches à effectuer des agents distincts; pour chaque pétale de tâches, le calcul (62) d’un coût d’exécution de la solution évaluée en fonction des coûts d’exécution des pétales et d’une politique d’agrégation de coûts donnée. Figure pour l'abrégé : Figure 4 Procédé et dispositif d’allocation de tâches entre agents La présente invention concerne un procédé d’allocation de tâches entre agents pour exécution de chaque tâche par un agent d’un ensemble d’agents formé de A agents, A étant un entier strictement positif, les tâches appartenant à un ensemble de tâches formé de T tâches à exécuter par au moins un sous-ensemble de l’ensemble d’agents, T étant un entier strictement positif. L’invention concerne également un dispositif d’allocation de tâches entre agents associé et un produit programme d’ordinateur associé. L’invention se situe dans le domaine de l’allocation de tâches à effectuer par plusieurs agents, et trouve des applications pratiques dans de nombreux domaines. Par exemple, l’invention s’applique pour l’allocation de tâches coopératives à effectuer par des agents qui sont des aéronefs sans pilote à bord (drones), les tâches étant par exemple des tâches de prise de vue de terrain, de détection de présence d’éléments particuliers, et plus généralement toute tâche de mission de ce type d’aéronef, dans les domaines civil ou militaire. L’invention s’applique pour un ensemble d’agents quelconque, qu’il s’agisse d’agents de même type (ensemble homogène) ou des agents de différents types (agents hétérogènes). Une tâche est exécutée par un agent et un seul, mais un même agent peut exécuter plusieurs tâches. L’ensemble de solutions d’allocations de tâches consiste à considérer toutes les allocations possibles de tâches à un ou plusieurs agents de l’ensemble d’agents. Le problème de l’allocation de tâches entre agents est un problème connu, qui a fait l’objet de recherches, notamment dans le cas particulier où le nombre T des tâches est supérieur au nombre A d’agents. L’article « Multi-task allocation and path planning for cooperating UAVS » de J. Bellingham et al, publié dans Cooperative Control Systems, vol.1, pages 23-41, Springer, Boston en 2003 formule le problème d’allocation de tâches entre agents comme un problème MMKP (« Multi-dimensional Multiple-choice Knapsack Problem »), connu dans le domaine de la recherche opérationnelle et propose une résolution via un solveur générique de type MILP (« Mixed Integer Linear Programming ») ou bien via un algorithme heuristique n’explorant pas l’intégralité des solutions d’allocation, et ne pouvant donc garantir l’optimalité de la solution trouvée. La première résolution présente l’inconvénient d’être lente et non prédictible en temps. La seconde résolution présente l’inconvénient de ne pas être optimale. L’invention a pour objet de remédier aux inconvénients de l’état de la technique, en proposant une méthode rapide car massivement parallélisable, prédictible en temps et avec une garantie d’optimalité. A cet effet, l’invention propose, selon un aspect, un procédé d’allocation de tâches entre agents pour exécution de chaque tâche par un agent d’un ensemble d’agents formé de A agents, A étant un entier strictement positif, les tâches appartenant à un ensemble de tâches formé de T tâches à exécuter par au moins une partie des agents, T étant un entier strictement positif, le procédé étant mis en œuvre par au moins une unité de calcul d’un processeur. Ce procédé comporte des étapes consistant à : pour au moins une solution d’allocation des tâches à exécuter entre au moins une partie desdits agents, dite solution évaluée, obtenir une liste de T indices d’agents définissant la solution évaluée, chaque indice d’agent correspondant à l’agent alloué pour effectuer la tâche dont l’indice est fourni par le rang dans ladite liste d’agents ; calculer, à partir de la liste de T indices d’agents, un ou plusieurs pétales de tâches à effectuer par des agents distincts, chaque pétale de tâches étant associé à un agent identifié par un indice distinct de la liste de T indices d’agents, un pétale de tâches étant une liste de L tâches, identifiées par leur indice dans l’ordre croissant, L étant un nombre compris entre 1 et T ; pour chaque pétale de tâches, calculer un indice de pétale associé, et accéder à une structure de mémorisation pour extraire, en fonction dudit indice de pétale, au moins un coût d’exécution des tâches du pétale par l’agent associé, calculer un coût d’exécution de la solution évaluée en fonction des coûts d’exécution extraits pour chaque pétale et d’une politique d’agrégation de coûts donnée. Avantageusement, le procédé d’allocation de tâches de l’invention est massivement parallélisable et la taille mémoire nécessaire est réduite. Avantageusement, tout calcul de coût peut être utilisé pour caractériser les solutions d’allocation, et le procédé est applicable pour des agents hétérogènes. Le procédé d’allocation de tâches entre agents selon l’invention peut également présenter une ou plusieurs des caractéristiques ci-dessous, prises indépendamment ou selon toutes les combinaisons techniquement envisageables : Le procédé comporte l’évaluation d’une pluralité de solutions, et une détermination d’une solution de coût d’exécution optimal selon un critère d’optimalité donné en fonction des coûts d’exécution calculés pour chaque solution évaluée. Le procédé est mis en œuvre par une pluralité d’unités de calcul d’un ou plusieurs processeurs, lesdites unités de calcul étant adaptées à fonctionner en parallèle, et comporte en outre une attribution à chaque unité de calcul d’un sous-ensemble de solutions à évaluer. Chaque solution dudit sous-ensemble de solutions à évaluer est définie par un indice de solution, et le procédé comporte un calcul, pour chaque indice de solution évaluée, de la liste de T indices d’agents formant ladite solution par décomposition en base A de l’indice de solution. Le procédé comporte, pour chaque unité de calcul, une détermination d’un coût d’exécution optimal associé au sous-ensemble de solutions évaluées par ladite unité de calcul, et un indice de solution associé, et une détermination d’une solution optimale par comparaison des coûts optimaux d’exécution associés aux sous-ensembles des solutions évaluées par chaque unité de calcul. Chaque unité de calcul met en œuvre, pour chaque solution évaluée, le calcul d’un coût d’exécution de ladite solution, puis une comparaison dudit coût d’exécution à un coût d’exécution optimal de référence associé au sous-ensemble de solutions évaluées par ladite unité de calcul, et si le coût d’exécution est meilleur que le coût d’exécution optimal de référence selon ledit critère d’optimalité, un remplacement dudit coût d’exécution optimal de référence par ledit coût d’exécution et une mémorisation de l’indice de ladite solution. Le procédé comporte une étape préalable de calcul des coûts d’exécution des pétales de tâches par les agents de l’ensemble d’agents, et de mémorisation des coûts calculés dans ladite structure de mémorisation. Le calcul des coûts d’exécution des pétales de tâches comporte un ordonnancement des pétales de tâches selon un ordre de rangement par tailles croissantes, pour les pétales de tâches de même taille, par un ordonnancement lexicographique des indices des tâches des pétales. Pour un pétale de tâches donné, le calcul de l’indice de pétale est effectué en fonction du nombre de tâches dans ledit pétale de tâches et des indices de tâches dudit pétale de tâches. La structure de mémorisation est une table de coûts, indexée dans l’ordre croissant des indices de pétales de tâches selon ledit ordonnancement des pétales de tâches et des indices d’agents de l’ensemble des agents. La politique d’agrégation de coûts consiste à calculer le coût d’exécution de la solution par application d’une fonction sur les coûts d’exécution extraits pour chaque pétale. Ladite fonction calcule la moyenne, ou la somme, ou le minimum ou le maximum des coûts d’exécution extraits pour chaque pétale. Selon un autre aspect, l’invention concerne un dispositif d’allocation de tâches entre agents d’allocation de tâches entre agents pour exécution de chaque tâche par un agent d’un ensemble d’agents formé de A agents, A étant un entier strictement positif, les tâches appartenant à un ensemble de tâches formé de T tâches à exécuter par au moins une partie des agents, T étant un entier strictement positif, comportant au moins une unité de calcul d’un processeur configuré pour mettre en œuvre : pour au moins une solution d’allocation des tâches à exécuter entre au moins une partie desdits agents, dite solution évaluée, un module d’obtention d’une liste de T indices d’agents définissant la solution évaluée, chaque indice d’agent correspondant à l’agent alloué pour effectuer la tâche dont l’indice est fourni par le rang dans ladite liste d’agents ; un module de calcul, à partir de la liste de T indices d’agents, d’un ou plusieurs pétales de tâches à effectuer par des agents distincts, chaque pétale de tâches étant associé à un agent identifié par un indice distinct de la liste de T indices d’agents, un pétale de tâches étant une liste de L tâches, identifiées par leur indice dans l’ordre croissant, L étant un nombre compris entre 1 et T ; configuré pour calculer, pour chaque pétale de tâches, un indice de pétale associé, et accéder à une structure de mémorisation pour extraire, en fonction dudit indice de pétale, au moins un coût d’exécution des tâches du pétale par l’agent associé, un module de calcul pour calculer un coût d’exécution de la solution évaluée en fonction des coûts d’exécution extraits pour chaque pétale et d’une politique d’agrégation de coûts donnée. Selon un aspect, ce dispositif comporte une pluralité d’unités de calcul d’un ou plusieurs processeurs, lesdites unités de calcul étant adaptées à fonctionner en parallèle, configuré pour attribuer à chaque unité de calcul d’un sous-ensemble de solutions à évaluer. Selon un autre aspect, l’invention concerne un programme d’ordinateur comportant des instructions logicielles qui, lorsqu’elles sont mises en œuvre par un dispositif électronique programmable, mettent en œuvre un procédé d’allocation de tâches entre agents tel que brièvement décrit ci-dessus. D’autres caractéristiques et avantages de l’invention ressortiront de la description qui en est donnée ci-dessous, à titre indicatif et nullement limitatif, en référence aux figures annexées, parmi lesquelles : la est un synoptique d’un dispositif électronique programmable configuré pour mettre en œuvre un procédé d’allocation de tâches selon un mode de réalisation ; la est un logigramme des principales étapes d’une première phase d’un procédé d’allocation de tâches ; la est un exemple schématique de table de coûts ; la est un logigramme des principales étapes d’une deuxième phase d’un procédé d’allocation de tâches ; la est un logigramme des principales étapes d’une mise en œuvre parallèle d’évaluation de coûts d’exécution de sous-ensembles de solutions ; la est un logigramme d’un mode de réalisation du calcul d’un coût d’exécution optimal associé à un sous-ensemble de tâches à exécuter selon un mode de réalisation. L’invention trouve de nombreuses applications, notamment dans le domaine de l’allocation de tâches à effectuer à une flotte d’aéronefs sans pilotes à bord. On considère un ensemble de T tâches à effectuer, T étant un entier strictement positif, par exemple compris entre 12 et 15, à effectuer par des agents d’un ensemble de A agents, A étant un entier strictement positif, par exemple compris entre 2 et 5. Par exemple, dans un cas d’application pratique, T est égal à 15 et A est égal à 4. Selon une modélisation, l’ensemble de tâches est constitué de tâches numérotées par des indices de tâches associés, allant de 0 à T-1. De même, l’ensemble d’agents est constitué d’agents identifiés par des indices d’agent, allant de 0 à A-1. Une solution d’allocation consiste à allouer ou attribuer chaque tâche t i à exécuter à un agent a j . Si le nombre d’agents est inférieur au nombre de tâches, un agent au moins devra exécuter plusieurs tâches. Selon une écriture choisie, une solution S k est formée d’une liste de T indices d’agents, chaque indice d’agent correspondant à l’agent alloué pour effectuer la tâche dont l’indice est fonction du rang dans ladite liste d’indices d’agents : où la tâche d’indice j est effectuée par l’agent d’indice dans la solution S k . A titre d’exemple, pour T=4 et A=3, selon cette écriture, la solution S=[0,0,0,0] implique que les tâches t 0 , t 1 , t 2 , t 3 sont toutes effectuées par l’agent a 0 et la solution S=[0,2,2,0] implique que les tâches t 0 et t 3 sont réalisées par l’agent a 0 , les tâches t 1 et t 2 par l’agent a 2 . On comprend que l’espace des solutions comprend A T solutions. Dans un mode de réalisation, le procédé est mis en œuvre par un dispositif électronique programmable comportant un ou plusieurs processeur(s) de calcul, chaque processeur comportant une ou plusieurs unités de calcul. Dans ce mode de réalisation, avantageusement, l’allocation de tâches entre agents est parallélisée ce qui réduit de manière significative le temps de calcul global. Dans une variante, le procédé d’allocation de tâches entre agents est mis en œuvre par un seul dispositif électronique programmable, par exemple un ordinateur, ou un système informatique composé d’une pluralité de dispositifs de calcul fonctionnant en réseau. La est un synoptique d’un dispositif électronique programmable 2 configuré pour mettre en œuvre un procédé d’allocation de tâches entre agents selon un mode de réalisation. Le dispositif électronique programmable 2 est par exemple un ordinateur comportant dans l’exemple un processeur 4 qui est un processeur multi-cœurs. En d’autres termes, le processeur 4 comporte plusieurs unités de calcul 8A, 8B, 8C, qui sont susceptibles d’exécuter des calculs en parallèle. Le dispositif électronique programmable 2 comprend également des unités de mémoire électronique 10, 12. Les éléments du dispositif électronique programmable 2 sont adaptés à communiquer via un bus de communication 14. Ce dispositif électronique programmable 2 est configuré pour mettre en œuvre l’invention. Le processeur 4, via les unités de calcul 8A, 8B, 8C, est configuré pour mettre en œuvre, lorsque le dispositif électronique programmable 2 est mis sous tension, un module 16 de calcul et mémorisation d’une structure 18 de mémorisation, par chacun des agents, de coûts d’exécution de sous-ensembles de tâches appelés « pétales de tâches », dont la définition sera détaillée ci-dessous. Dans un mode de réalisation, la structure 18 de mémorisation de coûts comporte une ou plusieurs table(s) de coûts, stockant les coûts associés aux « pétales de tâches » de chacun des agents. Le processeur 4 est également configuré pour mettre en œuvre un module 20 d’allocation de tâches entre agents, en se basant sur les coûts de la structure 18 de mémorisation de coûts préalablement calculée et enregistrée. Dans un mode de réalisation, les modules 16, 20 sont réalisés sous forme d’instructions logicielles formant un programme d’ordinateur, qui, lorsqu’il est exécuté par un ordinateur, met en œuvre un procédé d’allocation de tâches entre agents. Dans un mode réalisation alternatif, chaque module 16, 20 est réalisé sous forme d’un programme d’ordinateur distinct. En variante non représentée, les modules 16, 20 sont réalisés chacun sous forme de composants logiques programmables, tels que des FPGA (de l’anglais Field Programmable Gate Array ), des microprocesseurs, des composants GPGPU (de l’anglais General-purpose processing on graphics processing ), ou encore de circuits intégrés dédiés, tels que des ASIC (de l’anglais Application Specific Integrated Circuit ). Le programme d’ordinateur comportant des instructions logicielles est en outre apte à être enregistré sur un support, non représenté, lisible par ordinateur. Le support lisible par ordinateur est par exemple, un médium apte à mémoriser les instructions électroniques et à être couplé à un bus d’un système informatique. A titre d’exemple, le support lisible est un disque optique, un disque magnéto-optique, une mémoire ROM, une mémoire RAM, tout type de mémoire non-volatile (par exemple EPROM, EEPROM, FLASH, NVRAM), une carte magnétique ou une carte optique. Le procédé d’allocation de tâches entre agents comporte deux phases, une première phase préalable de calcul et mémorisation d’une structure de mémorisation de coûts d’exécution de pétales de tâches par les agents, et une phase d’allocation effective des tâches entre agents, en fonction de la structure de mémorisation de coûts préalablement calculée. La est un logigramme des principales étapes de la première phase préalable de calcul et mémorisation d’une structure de mémorisation de coûts d’exécution de pétales de tâches par des agents, dans un mode de réalisation. Comme indiqué ci-dessus, le procédé a pour but l’allocation de T tâches entre A agents, selon un critère d’optimalité donné. Les tâches et les agents sont définis selon l’application du procédé. Formellement, les tâches sont identifiées par des indices, l’ensemble de tâches à exécuter est noté : . Les agents sont également identifiés par des indices, l’ensemble d’agents est noté : Une solution pour l’allocation des tâches entre agents consiste à désigner, pour chaque tâche, un agent qui doit exécuter cette tâche. Un même agent est susceptible d’exécuter plusieurs tâches, voire la totalité des tâches. Tous les agents ne sont pas nécessairement impliqués dans une solution. Ainsi, dans le cas général, un même agent est susceptible d’exécuter zéro, une ou plusieurs tâches, i.e. un nombre L de tâches allant de 0 à T. On définit des pétales de tâches, un pétale de tâches étant une liste de L tâches, identifiées par leur indice, dans l’ordre croissant, L étant compris entre 1 et T. Un pétale de tâches de taille L s’exprime mathématiquement de la manière suivante : Où chaque valeur est un indice de tâche, , tous les indices de tâches formant un pétale de tâches étant distincts, les indices de tâches formant un pétale étant ordonnés dans un ordre croissant : si et seulement si Pour un nombre T de tâches, le nombre total G(T) de pétales de tâches est donné par la formule : Où est la factorielle de X. Le procédé comporte une étape 30 d’ordonnancement des pétales de tâches pour un ensemble de T tâches à exécuter. L’étape 30 consiste à ordonner les G(T) pétales de tâches dans un ordre choisi, qui est l’ordre de rangement par tailles, i.e. l’ordre croissant des tailles de pétales de tâches, pour les pétales de tâches d’une taille L donnée, dans l’ordre lexicographique croissant des indices de tâches. En d’autres termes, si on considère 2 pétales de tâches de longueur L, respectivement et , on note k le premier indice pour lequel . Alors l’ordre des pétales est le suivant : si A titre d’exemple numérique, pour L=4, si et , alors , car ces deux pétales diffèrent à partir de l’indice k=1, et 2 L’ordonnancement des pétales de tâches consiste à associer un indice de pétale à chaque pétale, les indices étant croissants selon l’ordre lexicographique explicité ci-dessus. Les pétales de tâches sont parcourus dans cet ordre, et pour chaque pétale, un coût d’exécution de ce pétale (i.e. d’exécution des tâches définies par le pétale) par chaque agent de l’ensemble des agents est calculé à l’étape de calcul 32 et mémorisé à l’étape de mémorisation 34 dans une structure de mémorisation. Dans un mode de réalisation, la structure de mémorisation est une table de coûts, dont un exemple schématique est illustré à la . Avantageusement, grâce à l’ordonnancement des pétales selon l’ordre lexicographique, il n’est pas nécessaire de mémoriser la liste des indices de tâches définissant chaque pétale. En effet, il est possible de calculer l’indice de pétale dans l’ordre lexicographique choisi en fonction de la longueur de pétale et des indices de tâches formant le pétale, comme expliqué plus en détail ci-après en référence à la . Le coût d’exécution de chaque pétale de tâches est effectué selon un critère choisi, par exemple un critère de distance, temps, énergie consommée, dangerosité etc. Dans un mode de réalisation, plusieurs tables de coûts sont calculées, pour plusieurs critères choisis, ce qui revient à calculer et mémoriser une table par critère et par agent. En variante, plusieurs coûts d’exécution selon des critères choisis différents sont associés à chaque pétale et à chaque agent, dans une même table de coûts. Selon une autre variante, les coûts d’exécution selon plusieurs critères différents sont combinés et mémorisés, par exemple par une combinaison linéaire pondérée. Toute autre structure de mémorisation de coûts peut être utilisée. Il est prévu d’associer un coût spécifique (coût non valide), par exemple la valeur « -1 », à chaque pétale considéré non valide ou non exécutable par un agent. Par exemple, un pétale peut contenir une ou plusieurs tâches qui ne peuvent pas être exécutées par un agent donné, pour des raisons de capacité matérielle et/ou d’autorisation. En complément, il est possible d’invalider certains pétales pour éviter la surcharge de certains agents au détriment des autres agents : par exemple, on peut associer un coût spécifique afin d’empêcher qu’un seul agent se charge des T tâches à exécuter, ou qu’un agent exécute plus d’un pourcentage Q des tâches à exécuter, par exemple plus de Q=80%. La illustre schématiquement une table de coûts 40, pour T tâches et A agents, chaque ligne de cette table correspondant à un pétale, les pétales étant ordonnés dans l’ordre croissant. Ainsi, lorsqu’on accède à la ligne d’indice k et à la colonne d’indice j de la table 40 on obtient le coût d’exécution du pétale d’indice k dans l’ordonnancement des pétales selon l’ordre croissant, par l’agent aj. La est un logigramme des principales étapes de l’évaluation du coût d’une solution. Le procédé comprend une étape 50 d’obtention d’un indice J de solution à évaluer, suivie d’une étape 52 de calcul de la liste des indices d’agents formant la solution S J . Le calcul mis en œuvre à l’étape 52 consiste à décomposer l’indice J de la solution à évaluer en base A, A étant le nombre d’agents. L’indice J se décompose en base A sous la forme : Alors la solution S J s’écrit sous la forme : En d’autres termes, dans la solution S J , la tâche t 0 est attribuée à l’agent d’indice r 0 , la tâche t 1 à l’agent d’indice r 1 et ainsi de suite. La solution S J peut contenir plusieurs fois le même indice d’agent, ce qui indique que ledit agent est chargé d’effectuer plusieurs tâches de la solution. Ensuite, une liste de pétales de tâches et des agents associés est extraite de la solution S J à évaluer à l’étape 54 d’extraction de la liste de pétales de tâches. En effet, selon une deuxième écriture, une solution d’allocation de tâches à des agents est une union de pétales à effectuer par des agents. La liste des pétales et des agents associés est obtenue en parcourant la solution à évaluer S J dans la première écriture (écrite selon [MATH 8]), pour extraire, pour chaque indice d’agent a j distinct, les indices n tels que r n =a j dans la solution S J . On obtient un pétale P m associé à l’agent a j dans la solution S J . Après considération de tous les indices d’agent distincts, on obtient A SJ pétales, la somme des longueurs des pétales étant égale à T, A SJ étant un nombre compris entre 1 et T. A titre d’exemple, pour J=685, pour T=6 et A=3, on obtient : La solution d’indice 685 s’écrit alors selon la première écriture: On en extrait les 3 pétales suivants : - associé à l’agent a 0 - associé à l’agent a 1 - associé à l’agent a 2 La solution S 685 est la réunion des associations des pétales et agents mentionnés ci-dessus. Pour chaque pétale extrait (étape 56), un indice de pétale est calculé à l’étape de calcul d’indice de pétale 58, selon l’ordonnancement des pétales défini ci-dessus. Le calcul d’un indice de pétale à partir des indices de tâches formant le pétale et de la longueur du pétale est effectué en appliquant les formules récursives suivantes. Soit un pétale de longueur L : L’indice du pétale P, noté est donné par une somme de 2 termes comme explicité ci-après : Où est l’indice du premier pétale de longueur L, et est la position du pétale considéré parmi les pétales de longueur L. On trouve ces valeurs par les formules récursives suivantes : Et où est le nombre de pétales de longueur n pour un ensemble de T tâches, qui ont la tâche d’indice t en position 0. Selon une autre formule : Selon une formule générale on note le nombre de pétales de longueur L (parmi tous les pétales pour T tâches), identiques jusqu’à la (k-1)ème position et ayant la tâche d’indice t en position k, où k varie de 0 à L-1. On a, pour tout i : En d’autres termes, il n’y a qu’un seul pétale de longueur L finissant par la tâche i (i en position L-1) et commençant par (L-1) tâches données. Et : Les valeurs sont toutes facilement calculées par récurrence en utilisant les formules [MATH 12] et [MATH 13] Pour calculer le deuxième terme de la somme fournissant l’indice de pétale, on met en œuvre la formule : Où : Par exemple, la solution S 685 est constituée des pétales : - d’indice 1 associé à l’agent a 0 - d’indice 25 associé à l’agent a 1 - d’indice 20 associé à l’agent a 2 La solution S 685 peut également s’écrire : Pour chaque pétale, en fonction de l’indice de pétale calculé et de l’indice d’agent associé dans la solution S J évaluée, un coût d’exécution de pétale est extrait de la structure de mémorisation des coûts (étape 60), qui est, dans un mode de réalisation, une table de mémorisation de coûts. Par exemple, pour évaluer le coût d’exécution de la solution S 685 , trois accès à la table de coûts sont effectués. Avantageusement, l’accès est rapide et parallélisable. Ensuite, un coût d’exécution associé à la solution évaluée S J est calculé et mémorisé à l’étape de calcul 62, selon une politique d’agrégation des coûts d’exécution des pétales par les agents. Par exemple, la politique d’agrégation consiste à effectuer un calcul, par exemple une somme, une moyenne, un écart-type, ou à appliquer un opérateur, par exemple le « min » ou le « max » consistant à retenir respectivement la valeur minimum ou la valeur maximum parmi les valeurs de coûts extraites à l’étape d’extraction des coûts 60. Par exemple, le coût associé à la solution est le coût maximum parmi les coûts extraits de la table de coûts. Le coût d’exécution de la solution S J évaluée, Coût(S J ) ainsi calculé est mémorisé suivant une stratégie définie ci-après. Cela permet d’effectuer par la suite des comparaisons des coûts d’exécution des solutions évaluées, afin de choisir une solution qui optimise le coût selon un critère d’optimisation de coût, par exemple la solution de coût d’exécution minimal. Dans un mode de réalisation préféré, l’ensemble complet de solutions d’allocations de tâches aux agents est testé, en effectuant des calculs en parallèle sur une pluralité d’unités de calcul. Avantageusement, l’empreinte mémoire du procédé est maîtrisée. La est un logigramme d’un mode de réalisation de la phase d’évaluation des coûts des solutions d’allocation, mise en œuvre par une pluralité de N unités de calcul. Le procédé comprend une étape 70 d’attribution d’un sous-ensemble de solutions à évaluer à chaque unité de calcul parmi les N unités de calcul. Le sous-ensemble de solutions est défini par des indices de solutions. Chaque unité de calcul met en œuvre un calcul 72 d’un coût d’exécution optimal parmi les coûts d’exécution des solutions évaluées, et une mémorisation de ce coût d’exécution optimal et de l’indice de solution associé (i.e. indice de la solution de coût d’exécution optimal parmi le sous-ensemble de solutions attribuées à l’unité de calcul). Pour la mise en œuvre du calcul 72 d’un coût d’exécution optimal, dans un mode de réalisation, les étapes décrites en référence à la sont mises en œuvre par chaque unité de calcul. Ces étapes comportent pour chaque solution évaluée S e du sous-ensemble de solutions à évaluer, un calcul 74 du coût d’exécution de la solution S e . Par exemple, le procédé décrit en référence à la est mis en œuvre. Le coût d’exécution obtenu est alors comparé à l’étape de comparaison 76 à un coût d’exécution optimal de référence associé à l’unité de calcul courante et au sous-ensemble de solutions évaluées. Ce coût d’exécution optimal de référence est initialisé à une valeur par défaut. Si par exemple le critère d’optimisation est la minimisation du coût d’exécution, il est vérifié à l’étape de comparaison 76 si le coût d’exécution de la solution est inférieur au coût d’exécution optimal de référence préalablement mémorisé. Si la réponse est oui, alors la solution évaluée S e est meilleure, au sens du critère d’optimisation, que toutes les solutions préalablement évaluées. L’étape de comparaison 76 est alors suivie d’une étape 78 de mémorisation du coût d’exécution de S e comme coût optimal d’exécution de référence, et de l’indice de la solution S e comme indice de solution optimale associé. Si la réponse à l’étape de comparaison 76 est non elle est suivie de l’étape 80 de sélection d’une solution suivante du sous-ensemble de solutions à évaluer par l’unité de calcul courante. L’étape 78 est également suivie de l’étape 80. Lorsque toutes les solutions du sous-ensemble de solutions à évaluer par l’unité de calcul ont été testées, l’étape 72 est finalisée. Le coût d’exécution optimal associé au sous-ensemble évalué, égal au coût d’exécution optimal de référence mémorisé, est obtenu, ainsi que l’indice de solution associé. De retour à la , les coûts d’exécution optimaux pour chaque sous-ensemble de solutions évaluées sont comparés à l’étape de comparaison 82, et la solution dont le coût d’exécution est optimal (e.g. minimal) parmi toutes les solutions évaluées en parallèle est déterminée à l’étape 84. Avantageusement, la quantité de données mémorisées est minimisée, puisque seul le coût d’exécution optimal de référence est retenu pour chaque sous-ensemble de solutions évaluées par chaque unité de calcul. En effet, le nombre de solutions par sous-ensemble de solutions à évaluer en parallèle est choisi librement. Avantageusement, le procédé d’allocation de tâches décrit permet de contrôler l’espace mémoire utilisé, et de tester, en un temps prévisible, l’ensemble exhaustif de solutions possibles. Pour conserver une efficacité calculatoire, tout en effectuant une évaluation exhaustive de l’ensemble des solutions, selon le nombre d’unités de calcul disponible, le nombre de tâches et d’agents est fixé. Pour trouver des solutions à des problèmes de plus grande taille en termes de nombre de tâches et de nombre d’agents, il est possible d’envisager une approche multi-résolution, en regroupant les tâches groupes de tâches formant des macro-tâches et les agents par groupes d’agents formant des macro-agents dans un premier temps, puis affiner l’allocation des tâches par agent à l’intérieur d’une macro-tâche pour un groupe d’agents. Cette approche est appelée approche multi-résolution. Plusieurs niveaux de résolution dans une approche multi-résolution sont envisageables, et réalisables grâce au fait que le procédé d’allocation de tâches est massivement parrallélisable. Par exemple, dans une application pratique, une flotte de 16 avions et 32 drones ont à traiter des cibles situées dans 9 localités : 2 bases aériennes, 4 postes avancés, 3 zones industrielles. Dans une première phase, on considère 4 équipes de 4 avions et 8 drones chacune, constituant ainsi 4 macro-agents. Les 9 localités sont autant de macro-tâches. Le procédé permet de répartir ces 9 localités entre les 4 macro-agents. Le procédé sera ensuite utilisé 9 fois, à savoir une fois par localité, pour affiner les allocations en fonctions de missions associées aux localités. Le procédé d’allocation de tâches entre agents permet aisément de prendre en compte des agents hétérogènes. En effet, si certains agents ne sont pas capables de traiter certaines tâches, il suffit d’associer un coût spécifique (coût non valide) à chaque pétale incluant la ou les tâches qui ne peuvent pas être traitées par l’agent considéré. Procédé d’allocation de tâches entre agents pour exécution de chaque tâche par un agent d’un ensemble d’agents formé de A agents, A étant un entier strictement positif, les tâches appartenant à un ensemble de tâches formé de T tâches à exécuter par au moins une partie des agents, T étant un entier strictement positif, le procédé étant mis en œuvre par au moins une unité de calcul d’un processeur, et étant caractérisé en ce qu’il comporte : pour au moins une solution d’allocation des tâches à exécuter entre au moins une partie desdits agents, dite solution évaluée, obtenir (50, 52) une liste de T indices d’agents définissant la solution évaluée, chaque indice d’agent correspondant à l’agent alloué pour effectuer la tâche dont l’indice est fourni par le rang dans ladite liste d’agents ; calculer (54), à partir de la liste de T indices d’agents, un ou plusieurs pétales de tâches à effectuer par des agents distincts, chaque pétale de tâches étant associé à un agent identifié par un indice distinct de la liste de T indices d’agents, un pétale de tâches étant une liste de L tâches, identifiées par leur indice dans l’ordre croissant, L étant un nombre compris entre 1 et T ; pour chaque pétale de tâches, calculer(58) un indice de pétale associé, et accéder (60) à une structure de mémorisation pour extraire, en fonction dudit indice de pétale, au moins un coût d’exécution des tâches du pétale par l’agent associé, calculer (62) un coût d’exécution de la solution évaluée en fonction des coûts d’exécution extraits pour chaque pétale et d’une politique d’agrégation de coûts donnée. Procédé selon la revendication 1, comportant l’évaluation (72) d’une pluralité de solutions, et une détermination (82, 84) d’une solution de coût d’exécution optimal selon un critère d’optimalité donné en fonction des coûts d’exécution calculés pour chaque solution évaluée. Procédé selon la revendication 2, mis en œuvre par une pluralité d’unités de calcul d’un ou plusieurs processeurs, lesdites unités de calcul étant adaptées à fonctionner en parallèle, comportant en outre une attribution (70) à chaque unité de calcul d’un sous-ensemble de solutions à évaluer. Procédé selon la revendication 3, dans lequel chaque solution dudit sous-ensemble de solutions à évaluer est définie par un indice de solution, comportant un calcul (52), pour chaque indice de solution évaluée, de la liste de T indices d’agents formant ladite solution par décomposition en base A de l’indice de solution. Procédé selon la revendication 3 ou 4, comportant, pour chaque unité de calcul, une détermination (72) d’un coût d’exécution optimal associé au sous-ensemble de solutions évaluées par ladite unité de calcul, et un indice de solution associé, et une détermination (82, 84) d’une solution optimale par comparaison (82) des coûts optimaux d’exécution associés aux sous-ensembles des solutions évaluées par chaque unité de calcul. Procédé selon l’une des revendications 3 à 5, dans lequel chaque unité de calcul met en œuvre, pour chaque solution évaluée, le calcul (74) d’un coût d’exécution de ladite solution, puis une comparaison (76) dudit coût d’exécution à un coût d’exécution optimal de référence associé au sous-ensemble de solutions évaluées par ladite unité de calcul, et si le coût d’exécution est meilleur que le coût d’exécution optimal de référence selon ledit critère d’optimalité, un remplacement (78) dudit coût d’exécution optimal de référence par ledit coût d’exécution et une mémorisation (78) de l’indice de ladite solution. Procédé selon l’une des revendications 1 à 6, comportant une étape préalable de calcul (30, 32) des coûts d’exécution des pétales de tâches par les agents de l’ensemble d’agents, et de mémorisation (34) des coûts calculés dans ladite structure de mémorisation. Procédé selon la revendication 7, dans lequel le calcul des coûts d’exécution des pétales de tâches comporte un ordonnancement (30) des pétales de tâches selon un ordre de rangement par tailles croissantes, pour les pétales de tâches de même taille, par un ordonnancement lexicographique des indices des tâches des pétales. Procédé selon l’une des revendications 7 ou 8, dans lequel, pour un pétale de tâches donné, le calcul (58) de l’indice de pétale est effectué en fonction du nombre de tâches dans ledit pétale de tâches et des indices de tâches dudit pétale de tâches. Procédé selon l’une des revendications 7 à 9, dans lequel ladite structure de mémorisation (18) est une table de coûts (40), indexée dans l’ordre croissant des indices de pétales de tâches selon ledit ordonnancement des pétales de tâches et des indices d’agents de l’ensemble des agents. Procédé selon l’une des revendications 1 à 10, dans lequel la politique d’agrégation de coûts consiste à calculer le coût d’exécution de la solution par application d’une fonction sur les coûts d’exécution extraits pour chaque pétale. Procédé selon la revendication 11, dans lequel ladite fonction calcule la moyenne, ou la somme, ou le minimum ou le maximum des coûts d’exécution extraits pour chaque pétale. Programme d’ordinateur comportant des instructions logicielles qui, lorsqu’elles sont exécutées par un dispositif électronique programmable, mettent en œuvre un procédé d’allocation de tâches entre agents conforme aux revendications 1 à 12. Dispositif d’allocation de tâches entre agents pour exécution de chaque tâche par un agent d’un ensemble d’agents formé de A agents, A étant un entier strictement positif, les tâches appartenant à un ensemble de tâches formé de T tâches à exécuter par au moins une partie des agents, T étant un entier strictement positif, comportant au moins une unité de calcul d’un processeur caractérisé en ce qu’il est configuré pour mettre en oeuvre : pour au moins une solution d’allocation des tâches à exécuter entre au moins une partie desdits agents, dite solution évaluée, un module d’obtention d’une liste de T indices d’agents définissant la solution évaluée, chaque indice d’agent correspondant à l’agent alloué pour effectuer la tâche dont l’indice est fourni par le rang dans ladite liste d’agents ; un module de calcul, à partir de la liste de T indices d’agents, d’un ou plusieurs pétales de tâches à effectuer par des agents distincts, chaque pétale de tâches étant associé à un agent identifié par un indice distinct de la liste de T indices d’agents, un pétale de tâches étant une liste de L tâches, identifiées par leur indice dans l’ordre croissant, L étant un nombre compris entre 1 et T ; configuré pour calculer, pour chaque pétale de tâches, un indice de pétale associé, et accéder à une structure de mémorisation (18) pour extraire, en fonction dudit indice de pétale, au moins un coût d’exécution des tâches du pétale par l’agent associé, un module de calcul pour calculer un coût d’exécution de la solution évaluée en fonction des coûts d’exécution extraits pour chaque pétale et d’une politique d’agrégation de coûts donnée. Dispositif selon la revendication 14, comportant une pluralité d’unités de calcul d’un ou plusieurs processeurs, lesdites unités de calcul étant adaptées à fonctionner en parallèle, configuré pour attribuer à chaque unité de calcul d’un sous-ensemble de solutions à évaluer.