74 research outputs found
Algorithmes de formation de coalitions d’agents
No full textCoalition formation is an important mode of interaction in multiagent systems that involves grouping several agents together within different coalitions in order to efficiently achieve their individual or collective goals. Forming certain coalitions can be more valuable than others and deciding which coalitions to form typically involves evaluating multiple coalition structures. The choice of coalitions to form is of crucial importance, as it can have a major impact on the overall success of the endeavor. This is a major problem in artificial intelligence and game theory that is central to many practical applications, such as transportation, disaster response, and distributed sensor networks. A crucial challenge in coalition formation is coalition structure generation, where agents are bundled into a coalition structure---that is, disjoint coalitions in which each agent belongs to only one coalition---in a way that maximizes social welfare. However, this problem of generating an optimal coalition structure is exceptionally complex due to the exponential growth in the number of potential solutions as the number of involved agents increases. In this thesis, we address this problem by introducing a set of algorithms designed to provide optimal or approximate solutions. First, we introduce new concepts and methods for the coalition structure generation problem, including offline phases that improve the efficiency of the search process. Specifically, we divide the coalition structure generation into two phases: an offline phase and an online phase, allowing automated configuration of algorithms for this problem. This is based on non-trivial results of the search space analysis that revealed that exact algorithms for this problem can be improved by automatically tuning them. Second, we develop an algorithm that uses a new representation of the search space, which partitions the space of possible solutions into subspaces and gathers the solutions in a new way. This representation not only enables to optimize the evaluation of coalition structures but also enables to eliminate the redundant processing of common coalition structures, resulting in a significant reduction in computational time. Furthermore, we develop several methods to tackle large-scale instances of this problem. Specifically, we develop two heuristic algorithms based on a new representation of the search space that depicts the space of coalition structures using integers. These algorithms generate the coalition structures by performing index permutations on specific initialization vectors and can handle problems with hundreds or thousands of agents. Last but not least, we develop SALDAE, a multiagent path finding algorithm designed for the coalition structure generation problem. This algorithm significantly outperforms other scalable algorithms in terms of solution quality.La formation de coalitions est un type d'interaction important dans les systèmes multi-agents qui implique le regroupement de plusieurs agents au sein de différentes coalitions afin d'atteindre efficacement leurs objectifs individuels ou collectifs. La formation de certaines coalitions peut être plus intéressante que d'autres et le choix des coalitions à former implique généralement l'évaluation de plusieurs structures de coalition. Le choix des coalitions à former est d'une importance cruciale, car il peut avoir un impact majeur sur le succès global de tout le processus. Il s'agit d'un problème majeur en intelligence artificielle et en théorie des jeux qui est au cœur de nombreuses applications pratiques, telles que les transports, les interventions en cas de catastrophe et les réseaux de capteurs distribués. Un défi crucial dans la formation de coalitions est la génération de structure de coalitions, où les agents sont regroupés dans une structure de coalition---c'est-à-dire des coalitions disjointes dans lesquelles chaque agent n'appartient qu'à une seule coalition---d'une manière qui maximise le bien-être social. Cependant, ce problème de génération d'une structure de coalition optimale est exceptionnellement complexe en raison de la croissance exponentielle du nombre de solutions potentielles à mesure que le nombre d'agents impliqués augmente. Dans cette thèse, nous abordons ce problème en introduisant un ensemble d'algorithmes conçus pour fournir des solutions optimales ou approximatives. Tout d'abord, nous introduisons de nouveaux concepts et méthodes pour le problème de la génération de structures de coalitions, y compris des phases offline qui améliorent l'efficacité du processus de recherche. Plus précisément, nous divisons la génération de structures de coalitions en deux phases : une phase offline et une phase online, ce qui permet une configuration automatisée des algorithmes pour ce problème. Ceci est basé sur des résultats non triviaux de l'analyse de l'espace de recherche qui a révélé que les algorithmes exacts pour ce problème peuvent être améliorés en les réglant automatiquement. Deuxièmement, nous développons un algorithme qui utilise une nouvelle représentation de l'espace de recherche, qui partitionne l'espace des solutions possibles en sous-espaces et rassemble les solutions d'une nouvelle manière. Cette représentation permet non seulement d'optimiser l'évaluation des structures de coalition, mais aussi d'éliminer le traitement redondant des structures de coalition communes, ce qui se traduit par une réduction significative du temps de calcul. En outre, nous développons plusieurs méthodes pour traiter les instances à grande échelle de ce problème. Plus précisément, nous développons deux algorithmes heuristiques basés sur une nouvelle représentation de l'espace de recherche qui décrit l'espace des structures de coalitions en utilisant des nombres entiers. Ces algorithmes génèrent les structures de coalitions en effectuant des permutations d'index sur des vecteurs d'initialisation spécifiques et peuvent traiter des problèmes avec des centaines ou des milliers d'agents. Enfin, nous développons SALDAE, un algorithme de recherche de chemin multi-agents conçu pour le problème de la génération de structures de coalitions. Cet algorithme est nettement plus performant que d'autres algorithmes en termes de qualité des solutions
Algorithmes de formation de coalitions d’agents
No full textCoalition formation is an important mode of interaction in multiagent systems that involves grouping several agents together within different coalitions in order to efficiently achieve their individual or collective goals. Forming certain coalitions can be more valuable than others and deciding which coalitions to form typically involves evaluating multiple coalition structures. The choice of coalitions to form is of crucial importance, as it can have a major impact on the overall success of the endeavor. This is a major problem in artificial intelligence and game theory that is central to many practical applications, such as transportation, disaster response, and distributed sensor networks. A crucial challenge in coalition formation is coalition structure generation, where agents are bundled into a coalition structure---that is, disjoint coalitions in which each agent belongs to only one coalition---in a way that maximizes social welfare. However, this problem of generating an optimal coalition structure is exceptionally complex due to the exponential growth in the number of potential solutions as the number of involved agents increases. In this thesis, we address this problem by introducing a set of algorithms designed to provide optimal or approximate solutions. First, we introduce new concepts and methods for the coalition structure generation problem, including offline phases that improve the efficiency of the search process. Specifically, we divide the coalition structure generation into two phases: an offline phase and an online phase, allowing automated configuration of algorithms for this problem. This is based on non-trivial results of the search space analysis that revealed that exact algorithms for this problem can be improved by automatically tuning them. Second, we develop an algorithm that uses a new representation of the search space, which partitions the space of possible solutions into subspaces and gathers the solutions in a new way. This representation not only enables to optimize the evaluation of coalition structures but also enables to eliminate the redundant processing of common coalition structures, resulting in a significant reduction in computational time. Furthermore, we develop several methods to tackle large-scale instances of this problem. Specifically, we develop two heuristic algorithms based on a new representation of the search space that depicts the space of coalition structures using integers. These algorithms generate the coalition structures by performing index permutations on specific initialization vectors and can handle problems with hundreds or thousands of agents. Last but not least, we develop SALDAE, a multiagent path finding algorithm designed for the coalition structure generation problem. This algorithm significantly outperforms other scalable algorithms in terms of solution quality.La formation de coalitions est un type d'interaction important dans les systèmes multi-agents qui implique le regroupement de plusieurs agents au sein de différentes coalitions afin d'atteindre efficacement leurs objectifs individuels ou collectifs. La formation de certaines coalitions peut être plus intéressante que d'autres et le choix des coalitions à former implique généralement l'évaluation de plusieurs structures de coalition. Le choix des coalitions à former est d'une importance cruciale, car il peut avoir un impact majeur sur le succès global de tout le processus. Il s'agit d'un problème majeur en intelligence artificielle et en théorie des jeux qui est au cœur de nombreuses applications pratiques, telles que les transports, les interventions en cas de catastrophe et les réseaux de capteurs distribués. Un défi crucial dans la formation de coalitions est la génération de structure de coalitions, où les agents sont regroupés dans une structure de coalition---c'est-à-dire des coalitions disjointes dans lesquelles chaque agent n'appartient qu'à une seule coalition---d'une manière qui maximise le bien-être social. Cependant, ce problème de génération d'une structure de coalition optimale est exceptionnellement complexe en raison de la croissance exponentielle du nombre de solutions potentielles à mesure que le nombre d'agents impliqués augmente. Dans cette thèse, nous abordons ce problème en introduisant un ensemble d'algorithmes conçus pour fournir des solutions optimales ou approximatives. Tout d'abord, nous introduisons de nouveaux concepts et méthodes pour le problème de la génération de structures de coalitions, y compris des phases offline qui améliorent l'efficacité du processus de recherche. Plus précisément, nous divisons la génération de structures de coalitions en deux phases : une phase offline et une phase online, ce qui permet une configuration automatisée des algorithmes pour ce problème. Ceci est basé sur des résultats non triviaux de l'analyse de l'espace de recherche qui a révélé que les algorithmes exacts pour ce problème peuvent être améliorés en les réglant automatiquement. Deuxièmement, nous développons un algorithme qui utilise une nouvelle représentation de l'espace de recherche, qui partitionne l'espace des solutions possibles en sous-espaces et rassemble les solutions d'une nouvelle manière. Cette représentation permet non seulement d'optimiser l'évaluation des structures de coalition, mais aussi d'éliminer le traitement redondant des structures de coalition communes, ce qui se traduit par une réduction significative du temps de calcul. En outre, nous développons plusieurs méthodes pour traiter les instances à grande échelle de ce problème. Plus précisément, nous développons deux algorithmes heuristiques basés sur une nouvelle représentation de l'espace de recherche qui décrit l'espace des structures de coalitions en utilisant des nombres entiers. Ces algorithmes génèrent les structures de coalitions en effectuant des permutations d'index sur des vecteurs d'initialisation spécifiques et peuvent traiter des problèmes avec des centaines ou des milliers d'agents. Enfin, nous développons SALDAE, un algorithme de recherche de chemin multi-agents conçu pour le problème de la génération de structures de coalitions. Cet algorithme est nettement plus performant que d'autres algorithmes en termes de qualité des solutions
Algorithmes de formation de coalitions d’agents
No full textCoalition formation is an important mode of interaction in multiagent systems that involves grouping several agents together within different coalitions in order to efficiently achieve their individual or collective goals. Forming certain coalitions can be more valuable than others and deciding which coalitions to form typically involves evaluating multiple coalition structures. The choice of coalitions to form is of crucial importance, as it can have a major impact on the overall success of the endeavor. This is a major problem in artificial intelligence and game theory that is central to many practical applications, such as transportation, disaster response, and distributed sensor networks. A crucial challenge in coalition formation is coalition structure generation, where agents are bundled into a coalition structure---that is, disjoint coalitions in which each agent belongs to only one coalition---in a way that maximizes social welfare. However, this problem of generating an optimal coalition structure is exceptionally complex due to the exponential growth in the number of potential solutions as the number of involved agents increases. In this thesis, we address this problem by introducing a set of algorithms designed to provide optimal or approximate solutions. First, we introduce new concepts and methods for the coalition structure generation problem, including offline phases that improve the efficiency of the search process. Specifically, we divide the coalition structure generation into two phases: an offline phase and an online phase, allowing automated configuration of algorithms for this problem. This is based on non-trivial results of the search space analysis that revealed that exact algorithms for this problem can be improved by automatically tuning them. Second, we develop an algorithm that uses a new representation of the search space, which partitions the space of possible solutions into subspaces and gathers the solutions in a new way. This representation not only enables to optimize the evaluation of coalition structures but also enables to eliminate the redundant processing of common coalition structures, resulting in a significant reduction in computational time. Furthermore, we develop several methods to tackle large-scale instances of this problem. Specifically, we develop two heuristic algorithms based on a new representation of the search space that depicts the space of coalition structures using integers. These algorithms generate the coalition structures by performing index permutations on specific initialization vectors and can handle problems with hundreds or thousands of agents. Last but not least, we develop SALDAE, a multiagent path finding algorithm designed for the coalition structure generation problem. This algorithm significantly outperforms other scalable algorithms in terms of solution quality.La formation de coalitions est un type d'interaction important dans les systèmes multi-agents qui implique le regroupement de plusieurs agents au sein de différentes coalitions afin d'atteindre efficacement leurs objectifs individuels ou collectifs. La formation de certaines coalitions peut être plus intéressante que d'autres et le choix des coalitions à former implique généralement l'évaluation de plusieurs structures de coalition. Le choix des coalitions à former est d'une importance cruciale, car il peut avoir un impact majeur sur le succès global de tout le processus. Il s'agit d'un problème majeur en intelligence artificielle et en théorie des jeux qui est au cœur de nombreuses applications pratiques, telles que les transports, les interventions en cas de catastrophe et les réseaux de capteurs distribués. Un défi crucial dans la formation de coalitions est la génération de structure de coalitions, où les agents sont regroupés dans une structure de coalition---c'est-à-dire des coalitions disjointes dans lesquelles chaque agent n'appartient qu'à une seule coalition---d'une manière qui maximise le bien-être social. Cependant, ce problème de génération d'une structure de coalition optimale est exceptionnellement complexe en raison de la croissance exponentielle du nombre de solutions potentielles à mesure que le nombre d'agents impliqués augmente. Dans cette thèse, nous abordons ce problème en introduisant un ensemble d'algorithmes conçus pour fournir des solutions optimales ou approximatives. Tout d'abord, nous introduisons de nouveaux concepts et méthodes pour le problème de la génération de structures de coalitions, y compris des phases offline qui améliorent l'efficacité du processus de recherche. Plus précisément, nous divisons la génération de structures de coalitions en deux phases : une phase offline et une phase online, ce qui permet une configuration automatisée des algorithmes pour ce problème. Ceci est basé sur des résultats non triviaux de l'analyse de l'espace de recherche qui a révélé que les algorithmes exacts pour ce problème peuvent être améliorés en les réglant automatiquement. Deuxièmement, nous développons un algorithme qui utilise une nouvelle représentation de l'espace de recherche, qui partitionne l'espace des solutions possibles en sous-espaces et rassemble les solutions d'une nouvelle manière. Cette représentation permet non seulement d'optimiser l'évaluation des structures de coalition, mais aussi d'éliminer le traitement redondant des structures de coalition communes, ce qui se traduit par une réduction significative du temps de calcul. En outre, nous développons plusieurs méthodes pour traiter les instances à grande échelle de ce problème. Plus précisément, nous développons deux algorithmes heuristiques basés sur une nouvelle représentation de l'espace de recherche qui décrit l'espace des structures de coalitions en utilisant des nombres entiers. Ces algorithmes génèrent les structures de coalitions en effectuant des permutations d'index sur des vecteurs d'initialisation spécifiques et peuvent traiter des problèmes avec des centaines ou des milliers d'agents. Enfin, nous développons SALDAE, un algorithme de recherche de chemin multi-agents conçu pour le problème de la génération de structures de coalitions. Cet algorithme est nettement plus performant que d'autres algorithmes en termes de qualité des solutions
Algorithmes de formation de coalitions d’agents
No full textCoalition formation is an important mode of interaction in multiagent systems that involves grouping several agents together within different coalitions in order to efficiently achieve their individual or collective goals. Forming certain coalitions can be more valuable than others and deciding which coalitions to form typically involves evaluating multiple coalition structures. The choice of coalitions to form is of crucial importance, as it can have a major impact on the overall success of the endeavor. This is a major problem in artificial intelligence and game theory that is central to many practical applications, such as transportation, disaster response, and distributed sensor networks. A crucial challenge in coalition formation is coalition structure generation, where agents are bundled into a coalition structure---that is, disjoint coalitions in which each agent belongs to only one coalition---in a way that maximizes social welfare. However, this problem of generating an optimal coalition structure is exceptionally complex due to the exponential growth in the number of potential solutions as the number of involved agents increases. In this thesis, we address this problem by introducing a set of algorithms designed to provide optimal or approximate solutions. First, we introduce new concepts and methods for the coalition structure generation problem, including offline phases that improve the efficiency of the search process. Specifically, we divide the coalition structure generation into two phases: an offline phase and an online phase, allowing automated configuration of algorithms for this problem. This is based on non-trivial results of the search space analysis that revealed that exact algorithms for this problem can be improved by automatically tuning them. Second, we develop an algorithm that uses a new representation of the search space, which partitions the space of possible solutions into subspaces and gathers the solutions in a new way. This representation not only enables to optimize the evaluation of coalition structures but also enables to eliminate the redundant processing of common coalition structures, resulting in a significant reduction in computational time. Furthermore, we develop several methods to tackle large-scale instances of this problem. Specifically, we develop two heuristic algorithms based on a new representation of the search space that depicts the space of coalition structures using integers. These algorithms generate the coalition structures by performing index permutations on specific initialization vectors and can handle problems with hundreds or thousands of agents. Last but not least, we develop SALDAE, a multiagent path finding algorithm designed for the coalition structure generation problem. This algorithm significantly outperforms other scalable algorithms in terms of solution quality.La formation de coalitions est un type d'interaction important dans les systèmes multi-agents qui implique le regroupement de plusieurs agents au sein de différentes coalitions afin d'atteindre efficacement leurs objectifs individuels ou collectifs. La formation de certaines coalitions peut être plus intéressante que d'autres et le choix des coalitions à former implique généralement l'évaluation de plusieurs structures de coalition. Le choix des coalitions à former est d'une importance cruciale, car il peut avoir un impact majeur sur le succès global de tout le processus. Il s'agit d'un problème majeur en intelligence artificielle et en théorie des jeux qui est au cœur de nombreuses applications pratiques, telles que les transports, les interventions en cas de catastrophe et les réseaux de capteurs distribués. Un défi crucial dans la formation de coalitions est la génération de structure de coalitions, où les agents sont regroupés dans une structure de coalition---c'est-à-dire des coalitions disjointes dans lesquelles chaque agent n'appartient qu'à une seule coalition---d'une manière qui maximise le bien-être social. Cependant, ce problème de génération d'une structure de coalition optimale est exceptionnellement complexe en raison de la croissance exponentielle du nombre de solutions potentielles à mesure que le nombre d'agents impliqués augmente. Dans cette thèse, nous abordons ce problème en introduisant un ensemble d'algorithmes conçus pour fournir des solutions optimales ou approximatives. Tout d'abord, nous introduisons de nouveaux concepts et méthodes pour le problème de la génération de structures de coalitions, y compris des phases offline qui améliorent l'efficacité du processus de recherche. Plus précisément, nous divisons la génération de structures de coalitions en deux phases : une phase offline et une phase online, ce qui permet une configuration automatisée des algorithmes pour ce problème. Ceci est basé sur des résultats non triviaux de l'analyse de l'espace de recherche qui a révélé que les algorithmes exacts pour ce problème peuvent être améliorés en les réglant automatiquement. Deuxièmement, nous développons un algorithme qui utilise une nouvelle représentation de l'espace de recherche, qui partitionne l'espace des solutions possibles en sous-espaces et rassemble les solutions d'une nouvelle manière. Cette représentation permet non seulement d'optimiser l'évaluation des structures de coalition, mais aussi d'éliminer le traitement redondant des structures de coalition communes, ce qui se traduit par une réduction significative du temps de calcul. En outre, nous développons plusieurs méthodes pour traiter les instances à grande échelle de ce problème. Plus précisément, nous développons deux algorithmes heuristiques basés sur une nouvelle représentation de l'espace de recherche qui décrit l'espace des structures de coalitions en utilisant des nombres entiers. Ces algorithmes génèrent les structures de coalitions en effectuant des permutations d'index sur des vecteurs d'initialisation spécifiques et peuvent traiter des problèmes avec des centaines ou des milliers d'agents. Enfin, nous développons SALDAE, un algorithme de recherche de chemin multi-agents conçu pour le problème de la génération de structures de coalitions. Cet algorithme est nettement plus performant que d'autres algorithmes en termes de qualité des solutions
FACS: Fast code-based Algorithm for Coalition Structure Generation, Student Abstract, Selected for presentation
No full textInternational audienc
A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation.
No full textInternational audienc
A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation, Accepted Paper
No full textInternational audienc
Efficient Size-based Hybrid Algorithm for Optimal Coalition Structure Generation, Long Abstract
No full textInternational audienc
A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation, Long Abstract
No full textInternational audienc
- …
