An official website of the United States government
The electric power distribution system (PDS) and the water distribution system (WDS) are coupled with each other through electricity-driven water facilities (EdWFs), such as pumps, water desalination plants, and wastewater treatment facilities. However, they are generally owned and operated by different utilities, and there does not exist an operator that possesses full information of both systems. As a result, centralized methods are not applicable for coordinating the operation of the two systems. This paper proposes a decentralized framework where the PDS and WDS operators solve their own operation problems, respectively, by sharing only limited information. Nevertheless, the boundary variables (i.e., the variables shared between two systems) are discontinuous due to their dependence on the on/off nature of EdWFs. Unfortunately, mature decentralized/distributed optimization algorithms like the alternating direction method of multipliers (ADMM) cannot guarantee convergence and optimality for a case like this. Therefore, this paper develops a novel algorithm that can guarantee convergence and optimality for the decentralized optimization of PDS and WDS based on a recently developed algorithm called the SD-GS-AL method. The SD-GS-AL method is a combination of the simplicial decomposition (SD), gauss–seidel (GS), and augmented Lagrangian (AL) methods, which can guarantee convergence and optimality for mixed-integer programs (MIPs) with continuous boundary variables. Nonetheless, the original SD-GS-AL algorithm does not work for the PDS-WDS coordination problem where the boundary variables are discontinuous. This paper modifies and improves the original SD-GS-AL algorithm by introducing update rules to discontinuous boundary variables (called the Auxiliary Variables Update step). The proposed mixed-integer boundary compatible (MIBC) SD-GS-AL algorithm has the following benefits: (1) it is capable of handling cases whose boundary variables are discontinuous with convergence and optimality guaranteed for mild assumptions, and (2) it only requires limited information exchange between PDS and WDS operators, which will help preserve the privacy of the two utilities and reduce the investment in building additional communication channels. Simulations on two coupled PDS and WDS test cases (Case 1: IEEE-13 node PDS and 11-node WDS, and Case 2: IEEE-37 node PDS and 36-node WDS) show that the proposed MIBC algorithm converges to the optimal solutions while the original SD-GS-AL does not converge for both test cases. The ADMM does not converge for the first test case while it converges to a sub-optimal solution, 63 % more than the optimal solution for the second test case.
more »
« less
A Decentralized Medium Access Protocol for Real-Time Wireless Ad Hoc Networks With Unreliable Transmissions
This paper proposes a feasibility-optimal decentralized algorithm for real-time wireless ad hoc networks, where a strict deadline is imposed for each packet. While centralized scheduling algorithms provide provably optimal theoretical guarantees, they may not be practical in many settings, such as industrial networked control systems. Therefore, it is of great importance to design an algorithm that achieves feasibility optimality in a decentralized manner. To design a decentralized algorithm, we leverage two widely-used functions of wireless devices: carrier sensing and backoff timers. Different from the conventional approach, the proposed algorithm utilizes a collision-free backoff scheme to enforce the transmission priority of different links. This design obviates the capacity loss due to collision with quantifiably small backoff overhead. The algorithm is fully decentralized in the sense that every link only needs to know its own priority, and links contend for priorities only through carrier sensing. We prove that the proposed algorithm is feasibility-optimal. NS-3 simulation results show that the proposed algorithm indeed performs as well as the feasibility-optimal centralized algorithm. Moreover, the results also show that the proposed algorithm converges to optimality very fast.
more »
« less
- Award ID(s):
- 1719384
- PAR ID:
- 10094847
- Date Published:
- Journal Name:
- 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS)
- Page Range / eLocation ID:
- 972 to 982
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
As various smart services are increasingly deployed in modern cities, many unexpected conflicts arise due to various physical world couplings. Existing solutions for conflict resolution often rely on centralized control to enforce predetermined and fixed priorities of different services, which is challenging due to the inconsistent and private objectives of the services. Also, the centralized solutions miss opportunities to more effectively resolve conflicts according to their spatiotemporal locality of the conflicts. To address this issue, we design a decentralized negotiation and conflict resolution framework named DeResolver, which allows services to resolve conflicts by communicating and negotiating with each other to reach a Pareto-optimal agreement autonomously and efficiently. Our design features a two-step self-supervised learning-based algorithm to predict acceptable proposals and their rankings of each opponent through the negotiation. Our design is evaluated with a smart city case study of three services: intelligent traffic light control, pedestrian service, and environmental control. In this case study, a data-driven evaluation is conducted using a large dataset consisting of the GPS locations of 246 surveillance cameras and an automatic traffic monitoring system with more than 3 million records per day to extract real-world vehicle routes. The evaluation results show that our solution achieves much more balanced results, i.e., only increasing the average waiting time of vehicles, the measurement metric of intelligent traffic light control service, by 6.8% while reducing the weighted sum of air pollutant emission, measured for environment control service, by 12.1%, and the pedestrian waiting time, the measurement metric of pedestrian service, by 33.1%, compared to priority-based solution.more » « less
-
A critical design decision for crowdsourcing platforms is the degree to which the platform mediator controls participant interactions. Platforms having a centralized model of mediation optimize for convenience, speed, and security in participant interactions, while platforms operating under decentralized control require greater user effort but offer them greater control and agency. The research described in this paper is a preliminary study using agent-based modeling to evaluate and compare the performance of crowd-shipping platforms with centralized/decentralized control over matchmaking of carriers and senders. Results indicate that centralized matchmaking protects the platform from premature failure when initial carrier/sender participation is low. Furthermore, when the platform’s assignment algorithm is designed to maximize platform revenue, subject to meeting carriers’ profit expectations, centralized matchmaking will tend to outperform decentralized matchmaking for both the mediator and the carriers.more » « less
-
We study a hinted heterogeneous multi-agent multi-armed bandits problem (HMA2B), where agents can query low-cost observations (hints) in addition to pulling arms. In this framework, each of the M agents has a unique reward distribution over K arms, and in T rounds, they can observe the reward of the arm they pull only if no other agent pulls that arm. The goal is to maximize the total utility by querying the minimal necessary hints without pulling arms, achieving time-independent regret. We study HMA2B in both centralized and decentralized setups. Our main centralized algorithm, GP-HCLA, which is an extension of HCLA, uses a central decision-maker for arm-pulling and hint queries, achieving O(M^4 K) regret with O(M K log T) adaptive hints. In decentralized setups, we propose two algorithms, HD-ETC and EBHD-ETC, that allow agents to choose actions independently through collision-based communication and query hints uniformly until stopping, yielding O(M^3 K^2) regret with O(M^3 K log T) hints, where the former requires knowledge of the minimum gap and the latter does not. Finally, we establish lower bounds to prove the optimality of our results and verify them through numerical simulations.more » « less
-
Centralized Training for Decentralized Execution, where agents are trained offline using centralized information but execute in a decentralized manner online, has gained popularity in the multi-agent reinforcement learning community. In particular, actor-critic methods with a centralized critic and decentralized actors are a common instance of this idea. However, the implications of using a centralized critic in this context are not fully discussed and understood even though it is the standard choice of many algorithms. We therefore formally analyze centralized and decentralized critic approaches, providing a deeper understanding of the implications of critic choice. Because our theory makes unrealistic assumptions, we also empirically compare the centralized and decentralized critic methods over a wide set of environments to validate our theories and to provide practical advice. We show that there exist misconceptions regarding centralized critics in the current literature and show that the centralized critic design is not strictly beneficial, but rather both centralized and decentralized critics have different pros and cons that should be taken into account by algorithm designersmore » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ICDCS.2018.00098
