This paper proposes a system that supports effective evacuation from danger using a distributedconstraintoptimization Algorithm. The use of the algorithm facilitates the assisted optimization of people's evacuat...
详细信息
ISBN:
(纸本)9781479921348;9780769550718
This paper proposes a system that supports effective evacuation from danger using a distributedconstraintoptimization Algorithm. The use of the algorithm facilitates the assisted optimization of people's evacuation timing, by estimating the location of evacuees. This system enables assistance in terms of evacuation guidance to be given to relieve congestion, by calculating evacuation routes via an adhoc network of evacuees' mobile devices (phones, PCs, etc.), intercommunication function, and location information.
Traffic signal control (TSC) has been one of the most useful ways for reducing urban road congestion. The challenge of TSC includes 1) real-time signal decision, 2) the complexity in traffic dynamics, and 3) the netwo...
详细信息
Traffic signal control (TSC) has been one of the most useful ways for reducing urban road congestion. The challenge of TSC includes 1) real-time signal decision, 2) the complexity in traffic dynamics, and 3) the network-level coordination. Reinforcement learning (RL) methods can query policies by mapping the traffic state to the signal decision in real-time, however, are inadequate for different traffic flow environment. By observing real traffic information, online planning methods can compute the signal decisions in a responsive manner. Unfortunately, existing online planning methods either require high computation complexity or get stuck in local coordination. Against this background, we propose an explicit multiagent coordination (EMC)-based online planning methods that can satisfy adaptive, real-time and network-level TSC. By multiagent, we model each intersection as an autonomous agent, and the coordination efficiency is modeled by a cost function between neighbor intersections. By network-level coordination, each agent exchanges messages of cost function with its neighbors in a fully decentralized manner. By real-time, the message-passing procedure can interrupt at any time when the real time limit is reached and agents select the optimal signal decisions according to current message. Finally, we test our EMC method in both synthetic and real road network datasets. Experimental results are encouraging: compared to RL and conventional transportation baselines, our EMC method performs reasonably well in terms of adapting to real-time traffic dynamics, minimizing vehicle travel time and scalability to city-scale road networks.
Local search algorithms are widely applied in solving large-scale distributed constraint optimization problem (DCOP). distributed stochastic algorithm (DSA) is a typical local search algorithm to solve DCOP. However, ...
详细信息
Local search algorithms are widely applied in solving large-scale distributed constraint optimization problem (DCOP). distributed stochastic algorithm (DSA) is a typical local search algorithm to solve DCOP. However, DSA has some drawbacks including easily falling into local optima and the unfairness of assignment choice. This paper presents a novel local search algorithm named VLSs to solve the issues. In VLSs, sampling according to the probability corresponding to assignment is introduced to enable each agent to choose other promising values. Besides, each agent alternately performs a greedy choice among multiple parallel solutions to reduce the chance of falling into local optima and a variance adjustment mechanism to guide the search into a relatively good initial solution in a periodic manner. We give the proof of variance adjustment mechanism rationality and theoretical explanation of impact of greed among multiple parallel solutions. The experimental results show the superiority of VLSs over state-of-the-art DCOP algorithms.
Local search algorithms are widely applied in solving large-scale distributed constraint optimization problems (DCOPs) where each agent holds a value assignment to its variable and iteratively makes a decision on whet...
详细信息
Local search algorithms are widely applied in solving large-scale distributed constraint optimization problems (DCOPs) where each agent holds a value assignment to its variable and iteratively makes a decision on whether to replace its assignment according to its neighbor states. However, the value assignments of their neighbors confine their search to a small space so that agents in local search algorithms easily fall into local optima. Fortunately, Genetic Algorithms (GAs) can direct a search process to a more promising space and help the search process to break up the confine of local states. Accordingly, we propose a GA-based framework (LSGA) to enhance local search algorithms, where a series of genetic operators are redesigned for agents in distributed scenario to accommodate DCOPs. First, a fitness function is designed to evaluate the assignments for each agent, considering the balance of local benefits and global benefits. Then, a new method is provided to decide crossover positions in terms of agent-communication and topological structure of DCOPs. Besides, a self-adaptive crossover probability and a self-adaptive mutation probability are proposed to control the uses of crossover operator and mutation operator, respectively. And more importantly, the LSGA framework can be easily applied in any local search algorithm. The experimental results demonstrate the superiority of the use of LSGA in the typical search algorithms over state-of-the-art incomplete algorithms.
The Coalition Formation with Spatial and Temporal constraints problem (CFSTP) is a multi-agent task allocation problem in which few agents have to perform many tasks, each with its deadline and workload. To maximize t...
详细信息
ISBN:
(数字)9783030822545
ISBN:
(纸本)9783030822538;9783030822545
The Coalition Formation with Spatial and Temporal constraints problem (CFSTP) is a multi-agent task allocation problem in which few agents have to perform many tasks, each with its deadline and workload. To maximize the number of completed tasks, the agents need to cooperate by forming, disbanding and reforming coalitions. The original mathematical programming formulation of the CFSTP is difficult to implement, since it is lengthy and based on the problematic Big-M method. In this paper, we propose a compact and easy-to-implement formulation. Moreover, we design D-CTS, a distributed version of the state-of-the-art CFSTP algorithm. Using public London Fire Brigade records, we create a dataset with 347588 tasks and a test framework that simulates the mobilization of firefighters in dynamic environments. In problems with up to 150 agents and 3000 tasks, compared to DSA-SDP, a state-of-the-art distributed algorithm, D-CTS completes 3.79%+/-[42.22%, 1.96%] more tasks, and is one order of magnitude more efficient in terms of communication overhead and time complexity. D-CTS sets the first large-scale, dynamic and distributed CFSTP benchmark.
distributed constraint optimization problem (DCOP) is a promising framework for modeling a wide variety of multi-agent coordination problems. Best-First search (BFS) and Depth-First search (DFS) are two main search st...
详细信息
distributed constraint optimization problem (DCOP) is a promising framework for modeling a wide variety of multi-agent coordination problems. Best-First search (BFS) and Depth-First search (DFS) are two main search strategies used for search-based complete DCOP algorithms. Unfortunately, BFS often has to deal with a large number of solution reconstructions whereas DFS is unable to promptly prune sub-optimal branch. However, their weaknesses will be remedied if the two search strategies are combined based on agents' positions in a pseudo-tree. Therefore, a hybrid DCOP algorithm with the combination of BFS and DFS, called BD-ADOPT, is proposed, in which a layering boundary is introduced to divide all agents into BFS-based agents and DFS-based agents. Furthermore, this paper gives a rule to find a suitable layering boundary with a new strategy for the agents near the boundary to realize the seamless joint between BFS and DFS strategies. Detailed experimental results show that BD-ADOPT outperforms some famous search-based complete DCOP algorithms on the benchmark problems.
Virtual Networks (VNs) offer a flexible and economic approach to deploy customer suited networks. However, defining how resources of a physical network are used to support VNs requirements is a NP-hard problem. For th...
详细信息
Virtual Networks (VNs) offer a flexible and economic approach to deploy customer suited networks. However, defining how resources of a physical network are used to support VNs requirements is a NP-hard problem. For this reason, heuristics have been used on mapping of virtual networks. Although heuristics do not ensure the optimal solution, they implement fast solutions and showed satisfactory results. This work presents a modeling of the node and link allocation problem using distributed constraint optimization problem (DCOP) with factor graphs, which is a formalism widely used in real distributedoptimizationproblems. In our approach, we use the max-sum algorithm to solve the DCOP. Correctness criteria for this approach are discussed and verifications are conducted through model checking.
Local search algorithms are widely adopted in solving large-scale distributed constraint optimization problems (DCOPs). However, since each agent always makes its value decision based on the values of its neighbors in...
详细信息
ISBN:
(纸本)9781510855076
Local search algorithms are widely adopted in solving large-scale distributed constraint optimization problems (DCOPs). However, since each agent always makes its value decision based on the values of its neighbors in local search, those algorithms usually suffer from local premature convergence. More concretely, an agent cannot make a wise decision with poor values of its neighbors since its decision space is bound up with those poor values. In this paper, we propose a Partial Decision Scheme (PDS) to relax the decision space of an agent by ignoring the value of its neighbor which has the bad impact on its local benefits. The PDS comprises two partial decision processes: trigger partial decision and recursive partial decision. The former is iteratively performed by agents who cannot enhance their local benefits unilaterally to break out of potential local optima. The latter is recursively performed by neglected agents to improve global benefits. Besides, the trigger conditions along with a self-adaptive probability are introduced to control the use of PDS. The PDS can be easily applied to any local search algorithm to overcome its local premature convergence with a small additional overhead. In our theoretical analysis, we prove the feasibility and convergence of PDS. Moreover, the experimental results also demonstrate the superiority of the use of PDS in the typical local search algorithms over state-of-the-art local search algorithms.
Local search algorithms are widely adopted in solving large-scale distributed constraint optimization problems (DCOPs) However, since each agent always makes its value decision based on the values of its neighbors in ...
详细信息
ISBN:
(纸本)9781510855076
Local search algorithms are widely adopted in solving large-scale distributed constraint optimization problems (DCOPs) However, since each agent always makes its value decision based on the values of its neighbors in local search, those algorithms usually suffer from local premature convergence More concretely, an agent cannot make a wise decision with poor values of its neighbors since its decision space is bound up with those poor values In this paper, we propose a Partial Decision Scheme (PDS) to relax the decision space of an agent by ignoring the value of its neighbor which has the bad impact on its local benefits. The PDS comprises two partial decision processes trigger partial decision and recursive partial decision The former is iteratively performed by agents who cannot enhance their local benefits unilaterally to break out of potential local optima. The latter is recursively performed by neglected agents to improve global benefits Besides, the trigger conditions along with a self-adaptive probability are introduced to control the use of PDS The PDS can be easily applied to any local search algorithm to overcome its local premature convergence with a small additional overhead In our theoretical analysis, we prove the feasibility and convergence of PDS Moreover, the experimental results also demonstrate the superiority of the use of PDS in the typical local search algorithms over state-of-the-art local search algorithms.
distributed sensor network is an important research area Of multi-agent systems. We focus On a type of distributed sensor network systems that cooperatively observe multiple targets with multiple autonomous sensors th...
详细信息
ISBN:
(纸本)9783642111600
distributed sensor network is an important research area Of multi-agent systems. We focus On a type of distributed sensor network systems that cooperatively observe multiple targets with multiple autonomous sensors that can control their own view. The problem of allocating. observation resource of the distributed sensor network can be formalized as distributed constraint optimization problems. However, in the previous works, the computation cost to solve the resource allocation problem highly increases with its scale/density. In this work, we divide the problem into two layers of problems, and two layered cooperative solvers are applied to those problems. The result of the experiment shows that our proposed method reduces the number of message cycles.
暂无评论