Collaboration and Coordination in Multi-Agent Systems
137 Followers
Recent papers in Collaboration and Coordination in Multi-Agent Systems
Les problèmes d’ordonnancement des personnels sont devenus de plus en plus diffusés dans notre vie réelle. Le problème d’emploi du temps est une instance des problèmes d’ordonnancement des tâches et en particulier des problèmes... more
Les problèmes d’ordonnancement des personnels sont devenus de plus en plus diffusés dans notre vie réelle. Le problème d’emploi du temps est une instance des problèmes d’ordonnancement des tâches et en particulier des problèmes d’ordonnancement des personnels, il est bien connu comme un problème NP-complet. Il joue un rôle très important dans plusieurs types d’organisation tels que les hôpitaux, les sociétés de transports, les services de protection et d’urgence et les universités.
Nous nous intéressons, dans ce travail, à la résolution du problème d’emploi du temps des cours universitaires. En effet, nous proposons un modèle multi-agents à base d’agents coopératifs, nommé M.A.T.P (Multi-Agent model for Timetabling Problem), permettant un traitement décentralisé et fortement parallèle du problème et intégrant de nouveaux détails qui n’ont pas été pris en compte par les travaux de la littérature.
Afin d’évaluer notre modèle, nous choisissons d’aborder un cas réel (instances de l’Ecole Supérieure de Commerce de Tunis). Les performances du modèle proposé sont exhibées à travers des comparaisons expérimentales avec l’approche de [Xiang et Zhang 08]. Nous concluons que notre modèle est plus efficace que ce dernier en termes de temps d’exécution et de considération de contraintes soft qui engendrent une augmentation de la complexité du problème mais aussi qui améliorent la qualité de la solution.
Nous nous intéressons, dans ce travail, à la résolution du problème d’emploi du temps des cours universitaires. En effet, nous proposons un modèle multi-agents à base d’agents coopératifs, nommé M.A.T.P (Multi-Agent model for Timetabling Problem), permettant un traitement décentralisé et fortement parallèle du problème et intégrant de nouveaux détails qui n’ont pas été pris en compte par les travaux de la littérature.
Afin d’évaluer notre modèle, nous choisissons d’aborder un cas réel (instances de l’Ecole Supérieure de Commerce de Tunis). Les performances du modèle proposé sont exhibées à travers des comparaisons expérimentales avec l’approche de [Xiang et Zhang 08]. Nous concluons que notre modèle est plus efficace que ce dernier en termes de temps d’exécution et de considération de contraintes soft qui engendrent une augmentation de la complexité du problème mais aussi qui améliorent la qualité de la solution.
Identifies Service Level Agreements as a mechanism of coordination and monitoring Interoperability in future Smart grids. A use case of Electrical Vehicle (EV) business case is illustrating our methodology
In this paper, we consider a decentralized approach to the multi-agent target assignment problem and explore the deterioration of the quality of assignment solution in respect to the decrease of the quantity of the information exchanged... more
In this paper, we consider a decentralized approach to the multi-agent target assignment problem and explore the deterioration of the quality of assignment solution in respect to the decrease of the quantity of the information exchanged among communicating agents and their communication range when the latter is not sufficient to maintain the connected communication graph. The assignment is achieved through a dynamic iterative auction algorithm in which agents (robots) assign the targets and move towards them in each period. In the case of static targets and connected communication graph, the algorithm results in an optimal assignment solution. The assignment results are compared with two benchmark cases: a centralized one in which all the global information is known and therefore, the optimal assignment can be found, and the greedy one in which each agent moves towards the target with the highest benefit without communication with any other agent.
In this paper we study the problem of the assignment of road paths to vehicles. If we assume available the real-time road network information, then (self-concerned) vehicles select paths in a way related to user optimization which results... more
In this paper we study the problem of the assignment of road paths to vehicles. If we assume available the real-time road network information, then (self-concerned) vehicles select paths in a way related to user optimization which results in Wardrop equilibrium. The latter, even though fair for the vehicles of the same Origin-Destination (O-D) pair, in general can be arbitrarily more costly than the system optimum. System optimization, on the other hand, can produce unfair assignments both for the vehicles of the same as of different O-D pairs. To surmount the performance issue of the user- in respect to the system-optimization while considering the fairness issues, we propose a MAS-based distributed optimization model for path assignment to vehicles from the same and different OD pairs at two levels. On the upper level, the proposed model optimizes the overall O-D pairs' Nash Welfare with the fairness related constraints while on the lower level, for every O-D pair separately, paths are assigned to individual vehicles through the auction algorithm. We test the solution approach through simulation, compare it with the conventional user- and system-optimization, and thus demonstrate that it results in fair and globally efficient path-vehicle assignments.
This chapter will address how agent organisations can improve and accelerate coordination processes in open environments. A state-of-art of recent proposals for describing agent organisations will be given, relating the different... more
This chapter will address how agent organisations can improve and accelerate coordination processes in open environments. A state-of-art of recent proposals for describing agent organisations will be given, relating the different methodologies
and formal approaches for defining agent organisations in an explicit way. Since artificial institutions can be seen as a regulative layer for agent organisations, a review of recent approaches of this issue will be also included. Moreover, there have been some recent approaches for making agents that might be capable of understanding the organisation structure and functionality and then being able for deciding whether participate inside or even to decide new structures for the organisation. A review of this kind of agents, known as organisation-aware agents, will be provided. Finally, an important question in open systems is how to endow an organisation with autonomic capabilities to yield a dynamical answer to changing circumstances. Thus, a review of methods for designing and/or implementing adaptive agent organisations will be given.
and formal approaches for defining agent organisations in an explicit way. Since artificial institutions can be seen as a regulative layer for agent organisations, a review of recent approaches of this issue will be also included. Moreover, there have been some recent approaches for making agents that might be capable of understanding the organisation structure and functionality and then being able for deciding whether participate inside or even to decide new structures for the organisation. A review of this kind of agents, known as organisation-aware agents, will be provided. Finally, an important question in open systems is how to endow an organisation with autonomic capabilities to yield a dynamical answer to changing circumstances. Thus, a review of methods for designing and/or implementing adaptive agent organisations will be given.
Sensor-based coverage problems have many applications such as patrolling, search-rescue, and surveillance. Using multi-robot team increases efficiency by reducing completion time of a sensor-based coverage task. Robustness to robot... more
Sensor-based coverage problems have many applications such as patrolling, search-rescue, and surveillance. Using multi-robot team increases efficiency by reducing completion time of a sensor-based coverage task. Robustness to robot failures is another advantage of using multiple robots for coverage. Although there are many works to increase the efficiency of coverage methods, there are few works related to robot failures in the literature. In this paper, fault-tolerant control architecture is proposed for sensor-based coverage. Robot failures are detected using the heartbeat strategy. To show the effectiveness of the proposed approach, experiments are conducted using P3-DX mobile robots both in laboratory and simulation environment.
Keywords: Fault-tolerant, multi-robot, sensor-based coverage, control architecture.
Paper videos can be reached from this URLs: http://www.youtube.com/playlist?list=PLENSkat0854tXKZWJ7X6dWBOyOBcW2jZC
http://www.ai-robotlab.ogu.edu.tr/gallery-movies.htm
Keywords: Fault-tolerant, multi-robot, sensor-based coverage, control architecture.
Paper videos can be reached from this URLs: http://www.youtube.com/playlist?list=PLENSkat0854tXKZWJ7X6dWBOyOBcW2jZC
http://www.ai-robotlab.ogu.edu.tr/gallery-movies.htm
In this paper, we present a short overview of the people flow coordination methods and propose a multi-agent based route recommender architecture for smart spaces which considers the influence of stress on human reactions to the... more
In this paper, we present a short overview of the people flow coordination methods and propose a multi-agent based route recommender architecture for smart spaces which considers the influence of stress on human reactions to the recommended routes. The objective of the architecture is to ensure that people can efficiently move in and among smart spaces while at the same time improve the overall system performance. The functioning of the architecture is demonstrated on a case study. The proposed approach can be used, among others, in route recommendation in smart cities, large public events, and emergency evacuations.
In this work, we approach the problem of a box transport by the robots that are requested to bring a box from an arbitrary initial to some preassigned target position. The robots are modeled as rational collaborative autonomous agents... more
In this work, we approach the problem of a box transport by the robots that are requested to bring a box from an arbitrary initial to some preassigned target position. The robots are modeled as rational collaborative autonomous agents working on their movement coordination in a discrete state space. The proposed method for coordinating the multirobot system is a two-level control model in which on the upper level, a Virtual Structure (VS) agent calculates offline the box trajectory from the initial to the goal position with incomplete obstacles data and informs the robots of the nominal route. The robots on the lower level, on the basis of the preassigned positions and the data about the unforeseen obstacles sensed by limited range sensors and exchanged among all the robots, individually optimize their local movement objective functions to mutually push the box following a preassigned trajectory in a safe manner. When the robots, due to the unforeseen obstacles, move from the trajectory defined by the VS agent too far away, more than a predefined distance, they contact the VS agent for the recalculation of the same. The results of the proposed coordination model's simulation in 2D environment are described.
Social Networks has become one of the most popular platforms to allow users to communicate, and share their interests without being at the same geographical location. With the great and rapid growth of Social Media sites such as Facebook,... more
Social Networks has become one of the most popular platforms to allow users to communicate, and share their interests without being at the same geographical location. With the great and rapid growth of Social Media sites such as Facebook, LinkedIn, Twitter…etc. causes huge amount of user-generated content. Thus, the improvement in the information quality and integrity becomes a great challenge to all social media sites, which allows users to get the desired content or be linked to the best link relation using improved search / link technique. So introducing semantics to social networks will widen up the representation of the social networks. In this paper, a new model of social networks based on semantic tag ranking is introduced. This model is based on the concept of multi-agent systems. In this proposed model the representation of social links will be extended by the semantic relationships found in the vocabularies which are known as (tags) in most of social networks.The proposed model for the social media engine is based on enhanced Latent Dirichlet Allocation(E-LDA) as a semantic indexing algorithm, combined with Tag Rank as social network ranking algorithm. The improvements on (E-LDA) phase is done by optimizing (LDA) algorithm using the optimal parameters. Then a filter is introduced to enhance the final indexing output. In ranking phase, using Tag Rank based on the indexing phase has improved the output of the ranking. Simulation results of the proposed model have shown improvements in indexing and ranking output.
In this study, motion planning and control scheme for a cooperative transportation system, which consists of a single object and multiple autonomous non-holonomic mobile robots included forklifts, is proposed. Virtual leader-follower... more
In this study, motion planning and control scheme for a cooperative transportation system, which consists of a single object and multiple autonomous non-holonomic mobile robots included forklifts, is proposed. Virtual leader-follower formation control strategy is used for the cooperative transportation system. The object is assumed as the virtual leader of the system and the robots carrying the object on their forklifts are considered as follower robots. A smooth path is generated by considering the constraints of the virtual robot. The origin of the coordinate system attached to the center of gravity of the object tracks the generated path. A path for each follower robot is generated to keep the formation structure. The follower robots track their paths. A communication framework is used for the messaging between robots, and asymptotically stable tracking control is used for trajectory tracking. The proposed method is verified with real applications and simulations using Pioneer P3-DX mobile robots and a single object.
Paper videos can be reached from this URL: http://www.youtube.com/playlist?list=PLENSkat0854sw9XIuLI_hz3NzoauVJDaC
Please look at the further study of "Formation-based cooperative transportation by a group of non-holonomic mobile robots"
Paper videos can be reached from this URL: http://www.youtube.com/playlist?list=PLENSkat0854sw9XIuLI_hz3NzoauVJDaC
Please look at the further study of "Formation-based cooperative transportation by a group of non-holonomic mobile robots"
This paper addresses a fundamental problem related to the interaction of autonomous agents in pervasive and intelligent environments. Such autonomous agent could be static, nomadic or highly mobile, and in general, be programmed (rule... more
This paper addresses a fundamental problem related to the interaction of autonomous agents in pervasive and intelligent environments. Such autonomous agent could be static, nomadic or highly mobile, and in general, be programmed (rule based) to produce required behaviours by different users. In addition, the communication between these agents may include delays, because of the network, or because their own speed of processing the information. These two characteristics – the rules of behaviour and the temporal delays - could lead the system to display some unwanted periodic behaviour. In this paper we describe our work in progress which includes a framework to study this problem, and a set of initial guidelines to detect this behaviour. We conclude by describing the future direction of our work.
In this paper we study the coordination of Emergency Medical Service (EMS) for patients with acute myocardial infarction with ST-segment elevation (STEMI). This is a health problem with high associated mortality. A " golden standard "... more
In this paper we study the coordination of Emergency Medical Service (EMS) for patients with acute myocardial infarction with ST-segment elevation (STEMI). This is a health problem with high associated mortality. A " golden standard " treatment for STEMI is angioplasty, which requires a catheterization lab and a highly qualified cardiology team. It should be performed as soon as possible since the delay to treatment worsens the pa-tient's prognosis. The decrease of the delay is achieved by coordination of EMS, which is especially important in the case of multiple simultaneous patients. Nowadays, this process is based on the First-Come-First-Served (FCFS) principle and it heavily depends on human control and phone communication with high proneness to human error and delays. The objective is, therefore, to automate the EMS coordination while minimizing the time from symptom onset to reperfusion and thus to lower the mortality and morbidity resulting from this disease. In this paper, we present a multi-agent decision-support system for the distributed coordination of EMS focusing on urgent out-of-hospital STEMI patients awaiting angioplasty. The system is also applicable to emergency patients of any pathology needing pre-hospital acute medical care and urgent hospital treatment. The assignment of patients to ambulances and angioplasty-enabled hospitals with cardiology teams is performed via a three-level optimization model. At each level, we find a globally efficient solution by a modification of the distributed relaxation method for the assignment problem called the auction algorithm. The efficiency of the proposed model is demonstrated by simulation experiments.
From the multi-agent system perspective Intelligent Buildings (IB) are a new research area and this domain poses several interesting challenges. Our IB model comprises a building containing room based embedded-agents which control... more
From the multi-agent system perspective Intelligent Buildings (IB) are a new research area and this domain poses several interesting challenges. Our IB model comprises a building containing room based embedded-agents which control environmental variables and devices within rooms that communicate with each other via a network. Inter-agent communication is central to such multi-agent systems. In this paper we explain why existing agent communication languages (ACLs) are unsuitable for IB embedded-agents and present a specification for a hierarchical Distributed Intelligent Building Agent Language (DIBAL) that overcomes the problems in applying ACLs to IB based embedded-agents. The paper begins by reviewing existing Agent Communication Languages (ACL) and discussing their unsuitability for IB applications before presenting our IB embedded-agent communication language, DIBAL. We then illustrate the ways in which DIBAL would facilitate the functionality we require by looking at a few IB scenarios in some detail.
Transparency is an important factor in democratic societies composed of characteristics such as accessibility, usability, informativeness, understandability and auditability. In this research we focus on auditability since it plays an... more
Transparency is an important factor in democratic societies composed of characteristics such as accessibility, usability, informativeness, understandability and auditability. In this research we focus on auditability since it plays an important role for citizens that need to understand and audit public information. Although auditability has been a subject of discussion when designing systems, there is a lack of systematization in its specification. We propose an approach to systematically add auditability requirements specification during the goal-oriented agent-based Tropos methodology. We used the Transparency Softgoal Interdependency Graph that captures the different facets of transparency while considering their operationalization. An empirical evaluation was conducted through the design and implementation of LawDisTrA system that distributes lawsuits among judges in an appellate court. Experiments included the distribution of over 300,000 lawsuits at the Brazilian Superior Labor Court. We theorize that the presented approach for auditability provides adequate techniques to address the cross-organizational nature of transparency.
This paper treats the coordination of Emergency Medical Assistance (EMA) and hospitals for after-hours surgeries of urgent patients arriving by ambulance. A standard hospital approach during night-shifts is to have standby surgery teams... more
This paper treats the coordination of Emergency Medical Assistance (EMA) and hospitals for after-hours surgeries of urgent patients arriving by ambulance. A standard hospital approach during night-shifts is to have standby surgery teams come to hospital after alert to cover urgent cases that cannot be covered by the in-house surgery teams. This approach results in a considerable decrease in staffing costs in respect to having sufficient permanent in-house staff. Therefore, coordinating EMA and the hospitals in a region with their outhouse staff with the objective to have as fast urgent surgery treatments as possible with minimized cost is a crucial parameter of the medical system efficiency and as such deserves a thorough investigation. In practice, the process is manual and the process management is case-specific, with great load on human phone communication. In this paper, we propose a decision support system for the automated coordination of hospitals, surgery teams on standby from home, and ambulances to decrease the time to surgery of urgent patients. The efficiency of the proposed model is proven over simulation experiments.
Multi-agent systems underpin the vision for ambient intelligence. However, developing multi-agent systems is a complex and challenging process. For example, pervasive computing has been found susceptible to instability, due to unwanted... more
Multi-agent systems underpin the vision for ambient intelligence. However, developing multi-agent systems is a complex and challenging process. For example, pervasive computing has been found susceptible to instability, due to unwanted behaviour arising from unplanned interaction between rule based agents. This instability is impossible to predict, as it depends on the rules of interaction, the initial state of the system, the user interaction, and in the time delay of the system (due to network traffic, different speed of processing, etc). In this paper we present a theoretical framework, an Interaction Network (IN), together with a communication locking strategy that we call INPRES (Instability Prevention System) that can be used to identify and eliminate this problem. In addition we describe a Multi-Dimensional Model (MDM) to represent the agents and the state of each agent over time. A theorem showing the role of delays in an unstable system is presented. We present experimental results based on simulations and a physical emulation that demonstrate the effectiveness of these methods.
Inspired by the new achievements in mobile robotics having as a result mobile robots able to execute different production tasks, we consider a factory producing a set of distinct products via or with the additional help of mobile robots.... more
Inspired by the new achievements in mobile robotics having as a result mobile robots able to execute different production tasks, we consider a factory producing a set of distinct products via or with the additional help of mobile robots. This particularly flexible layout requires the definition and the solution of a complex planning and scheduling problem. In order to minimize production costs, dynamic determination of the number of robots for each production task and the individual robot allocation are needed. We propose a solution in terms of a two-level decentralized Multi-Agent System (MAS) framework: at the first, production planning level, agents are tasks which compete for robots (resources at this level); at the second, scheduling level, agents are robots which reallocate themselves among different tasks to satisfy the requests coming from the first level. An iterative auction based negotiation protocol is used at the first level while the second level solves a Multi-Robot Task Allocation (MRTA) problem through a distributed version of the Hungarian Method. A comparison of the results with a centralized approach is presented.
Highlights
► Factories producing different goods with additional mobile resources (robots). ► A two-level multi-agent system framework for production planning and scheduling. ► First: allocate robots to fulfill demands with minimum production cost. ► An iterative auction method inspired by Lagrangean relaxation is adopted. ► Second: robots (re)schedule themselves with a distributed version of Hungarian method.
Highlights
► Factories producing different goods with additional mobile resources (robots). ► A two-level multi-agent system framework for production planning and scheduling. ► First: allocate robots to fulfill demands with minimum production cost. ► An iterative auction method inspired by Lagrangean relaxation is adopted. ► Second: robots (re)schedule themselves with a distributed version of Hungarian method.
In this paper, we consider a decentralized approach to the multi-agent target allocation problem where agents are partitioned in two groups and every member of each group is a possible target for the members of the opposite group. Each... more
In this paper, we consider a decentralized approach to the multi-agent target allocation problem where agents are partitioned in two groups and every member of each group is a possible target for the members of the opposite group. Each agent has a limited communication range (radius) and individual preferences for the target allocation based on its individual local utility function. Furthermore, all agents are mobile and the allocation is achieved through a proposed dynamic iterative auction algorithm. Every agent in each step finds its best target based on the auction algorithm and the exchange of information with connected agents and moves towards it without any insight in the decision-making processes of other agents in the system. In the case of connected communication graph among all agents, the algorithm results in an optimal allocation solution. We explore the deterioration of the allocation solution in respect to the decrease of the quantity of the information exchanged amon...
Exercise completed by: gFSC and FSAC Afghanistan in 2013. The Food Security and Agriculture Cluster (FSAC) in Afghanistan was established in 2008 and is co-led by WFP and FAO, with Islamic Relief currently serving as the NGO co-chair.... more
Exercise completed by: gFSC and FSAC Afghanistan in 2013.
The Food Security and Agriculture Cluster (FSAC) in Afghanistan was established in 2008 and is co-led by WFP and FAO, with Islamic Relief currently serving as the NGO co-chair. The main aim of the cluster is to provide an action-oriented forum for bringing together national and international humanitarian partners to improve the timeliness and effectiveness of humanitarian assistance in the lives of crisis-affected populations in Afghanistan. FSAC is also operational at sub-national level in all six regions of Afghanistan.
The Food Security and Agriculture Cluster (FSAC) in Afghanistan was established in 2008 and is co-led by WFP and FAO, with Islamic Relief currently serving as the NGO co-chair. The main aim of the cluster is to provide an action-oriented forum for bringing together national and international humanitarian partners to improve the timeliness and effectiveness of humanitarian assistance in the lives of crisis-affected populations in Afghanistan. FSAC is also operational at sub-national level in all six regions of Afghanistan.
Our environments are being gradually occupied with an abundant number of digital objects with networking and computing capabilities. After these devices are plugged into a network, they initially advertise their presence and capabilities... more
Our environments are being gradually occupied with an abundant number of digital objects with networking and computing capabilities. After these devices are plugged into a network, they initially advertise their presence and capabilities in the form of services so that they can be discovered and, if desired, exploited by a user or other networked device. With the increasing number of these devices attached to networks the complexity to configure and control them increases which may lead to major processing and communication overheads. Hence, the devices are no longer expected to just act as primitive stand-alone appliances which only provide the facilities and services to the user they are designed for, rather they can offer complex services from unique combinations of devices; which in turn creates the necessity for these devices to be equipped with some sort of intelligence and self-awareness which enables them to be self configuring and self programming. Intelligence in devices is obtained by embedding intelligent agents into them which provides them with proactive control and learning capabilities. Self-awareness within agents enables capabilities to operate in with a minimum of cognitive loading of the user, thereby supporting the vision for cognitive disappearance or ambient intelligence. This paper present a novel intelligent embedded agent technique for reducing the number of associations and interconnections between various agents operating within an AIE in order to minimize the processing latency and overhead caused by message flooding in a Pub/Sub middleware whilst reducing the cognitive load of configuringthese associations to personalize themselves to the user needs. The main goal of the proposed fuzzy based intelligent embedded agents includes learning and adapting the network configuration and the system functionality to meet the user’s needs based on monitoring the user behaviors in a lifelong non intrusive mode to pre-emptively control the environment on his behalf. In addition, the F-IAS agent aimed at reducing the agent associations and interconnections to the most relevant set in order to reduce its processing overheads and thus implicitly improving the system overall efficiency. Moreover, we employ ambassador agents which limit the number of messages reaching the societies by performing an analysis and filtering routine to determine if the propagated events mat ch the desired criteria of the member agents of the societies. Ambassadors are also utilized with novel characteristics to discover and select associations among agent pairs residing in separate societies based on a concurrence analysis of published events. In order to validate the efficiency of the proposed methods we will present two set of unique experiments. The first experiments described the obtained results carried out within the intelligent Dormitory (iDorm) which is a real world test bed for AIE research. Here we specifically demonstrate the utilization of the F-IAS agents and discuss that by optimizing the set of associations, the agents increases efficiency and performance. The second set of experiments is based on emulation of an iDorm-like large scale multi society based AIE environment. The results illustrate how ambassadors discover strongly correlated agent pairs and cause them to form associations so that relevant agents of separate societies can start interacting with each other.
Recent advances in technology and manufacturing have resulted in more powerful and smaller processors to be embedded in the various artefacts within smart environments. Most of these artefacts are network enabled and thanks to pervasive... more
Recent advances in technology and manufacturing have resulted in more powerful and smaller processors to be embedded in the various artefacts within smart environments. Most of these artefacts are network enabled and thanks to pervasive networking such artefacts can communicate and collaborate together to support our daily lives. Furthermore, these artefacts can also be equipped with embedded agents to provide intelligent reasoning, planning and learning capabilities. However, the multitude of interconnected devices and artefacts can result in major network and processing delays as well as creating inherent complexities in programming and configuring smart environments to personalise themselves to suit the individual needs. Hence, a major challenge to the design and use of smart environments involves finding the best set of device associations and interconnections that are most suitable to the environment and user needs. In this paper, we will present a novel intelligent method for reducing the number of associations and interconnections between the various devices and artefacts within smart environments to minimise the network and processing overheads while reducing the cognitive load associated with configuring and programming smart environments.
In this work we address the Multi-Robot Task Allocation Problem (MRTA). We assume that the decision making environment is decentralized with as many decision makers (agents) as the robots in the system. To solve this problem, we developed... more
In this work we address the Multi-Robot Task Allocation Problem (MRTA). We assume that the decision making environment is decentralized with as many decision makers (agents) as the robots in the system. To solve this problem, we developed a distributed version of the Hungarian Method for the assignment problem. The robots autonomously perform different substeps of the Hungarian algorithm on the base of the individual and the information received through the messages from the other robots in the system. It is assumed that each robot agent has an information regarding its distance from the targets in the environment. The inter-robot communication is performed over a connected dynamic communication network and the solution to the assignment problem is reached without any common coordinator or a shared memory of the system. The algorithm comes up with a global optimum solution in O(n3) cumulative time (O(n2) for each robot), with O(n3) number of messages exchanged among the n robots.
In this paper we study the problem of the assignment of road paths to vehicles. Due to the assumption that a low percentage of vehicles follow the routes proposed by route guidance systems (RGS) and the increase of the use of the same,... more
In this paper we study the problem of the assignment of road paths to vehicles. Due to the assumption that a low percentage of vehicles follow the routes proposed by route guidance systems (RGS) and the increase of the use of the same, the conventional RGS might shortly result obsolete.
Assuming a complete road network information at the disposal of RGSs, their proposed paths are related with user optimization which in general can be arbitrarily more costly than the system optimum. However, the user optimum is fair for the drivers of the same Origin–Destination (O–D) pair but it does not guarantee fairness for different O–D pairs. Contrary, the system optimum can produce unfair assignments both for the vehicles of the same as of different O–D pairs. This is the reason why, in this paper, we propose an optimization model which bridges this gap between the user and system optimum, and propose a new mathematical programming formulation based on Nash Welfare optimization which results in a good egalitarian and utilitarian welfare for all O–D pairs. To avoid the issues with the lack of robustness related with the centralized implementation, the proposed model is highly distributed. We test the solution approach through simulation and compare it with the conventional user- and system-optimization.
Assuming a complete road network information at the disposal of RGSs, their proposed paths are related with user optimization which in general can be arbitrarily more costly than the system optimum. However, the user optimum is fair for the drivers of the same Origin–Destination (O–D) pair but it does not guarantee fairness for different O–D pairs. Contrary, the system optimum can produce unfair assignments both for the vehicles of the same as of different O–D pairs. This is the reason why, in this paper, we propose an optimization model which bridges this gap between the user and system optimum, and propose a new mathematical programming formulation based on Nash Welfare optimization which results in a good egalitarian and utilitarian welfare for all O–D pairs. To avoid the issues with the lack of robustness related with the centralized implementation, the proposed model is highly distributed. We test the solution approach through simulation and compare it with the conventional user- and system-optimization.
This paper presents a novel fuzzy-based intelligent architecture that aims to find relevant and important associations between embedded-agent based services that form Ambient Intelligent Environments (AIEs). The embedded agents are used... more
This paper presents a novel fuzzy-based intelligent architecture that aims to find relevant and important associations between embedded-agent based services that form Ambient Intelligent Environments (AIEs). The embedded agents are used in two ways; first they monitor the inhabitants of the AIE, learning their behaviours in an online, non-intrusive and life-long fashion with the aim of pre-emptively setting the environment to the users preferred state. Secondly, they evaluate the relevance and significance of the associations to various services with the aim of eliminating redundant associations in order to minimize the agent computational latency within the AIE. The embedded agents employ fuzzy-logic due to its robustness to the uncertainties, noise and imprecision encountered in AIEs. We describe unique real world experiments that were conducted in the Essex intelligent Dormitory (iDorm) to evaluate and validate the significance of the proposed architecture and methods.
Ambient Intelligence (AmI) has been found to suffer from cyclic instability that manifests itself in the form of periodic oscillation of device states, such as lights flickering in smart homes. This behaviour emerges from interaction... more
Ambient Intelligence (AmI) has been found to suffer from cyclic instability that manifests itself in the form of periodic oscillation of device states, such as lights flickering in smart homes. This behaviour emerges from interaction between rule based devices. Complex systems theory has shown that it is not possible, in general, to predict whether a set of rules and initial conditions will lead a system into periodic behaviour. As a consequence, we have developed a strategy called Instability Prevention Systems (INPRES) to prevent this unwanted behaviour and a framework called Interaction Networks (IN) that captures the rule dependencies using graph theory. INPRES uses IN theory to analyse the rules and dependencies, identifying potential causes of instability and inoculating the network against instability by selectively locking network nodes in a way that seeks to preserve environment functionality.. The INPRES strategy has been proven effective for preventing this oscillatory behaviour; however, it has the inherent disadvantage of preventing information spreading across the system due to locking nodes. Thus, locking needs to be applied in a selective way. Towards this end we have found that the analysis of the local rules of the systems can provide additional information, that can improve the performance of INPRES: that is, it is possible to lock fewer agents thereby reducing the extent of the disabling effects of the locking. In this paper we show how this can be achieved by presenting the concept of weak and strong coupling of oscillatory subsystems and showing how this can be used as part of the IN methodology to produce a more effective locking arrangement. Additionally, some examples of this refinement using computing simulations are given. Finally, we discuss the potential for applying this work applications ranging from pervasive computing to political and financial systems.
Since protein structure similarity searching is very complex and time-consuming, one of the possible acceleration methods is parallelization by distributing the calculation on multiple computers. In the paper, we present a theoretical... more
Since protein structure similarity searching is very complex and time-consuming, one of the possible acceleration methods is parallelization by distributing the calculation on multiple computers. In the paper, we present a theoretical model of the hierarchical multi-agent system dedicated to the task of protein structure similarity searching. We also show results of several numerical experiments confirming a suitability of such distribution for the similarity searching performed for the Muconate Lactonizing Enzyme (PDB ID = 1MUC) from the Protein Data Bank (PDB) against the database containing almost thousand randomly chosen molecules.
Related Topics