اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA scalable distributed dynamical systems approach to compute the strongly connected components and diameter of networks
63
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Finding strongly connected components (SCCs) and the diameter of a directed network play a key role in a variety of discrete optimization problems, and subsequently, machine learning and control theory problems. On the one hand, SCCs are used in solving the 2-satisfiability problem, which has applications in clustering, scheduling, and visualization. On the other hand, the diameter has applications in network learning and discovery problems enabling efficient internet routing and searches, as well as identifying faults in the power grid. In this paper, we leverage consensus-based principles to find the SCCs in a scalable and distributed fashion with a computational complexity of $mathcal{O}left(Dd_{text{in-degree}}^{max}right)$, where $D$ is the (finite) diameter of the network and $d_{text{in-degree}}^{max}$ is the maximum in-degree of the network. Additionally, we prove that our algorithm terminates in $D+1$ iterations, which allows us to retrieve the diameter of the network. We illustrate the performance of our algorithm on several random networks, including ErdH{o}s-Renyi, Barabasi-Albert, and mbox{Watts-Strogatz} networks.
قيم البحث
اقرأ أيضاً
We propose a fully distributed control system architecture, amenable to in-vehicle implementation, that aims to safely coordinate connected and automated vehicles (CAVs) in road intersections. For control purposes, we build upon a fully distributed m
odel predictive control approach, in which the agents solve a nonconvex optimal control problem (OCP) locally and synchronously, and exchange their optimized trajectories via vehicle-to-vehicle (V2V) communication. To accommodate a fast solution of the nonconvex OCPs, we apply the penalty convex-concave procedure which aims to solve a convexified version of the original OCP. For experimental evaluation, we complement the predictive controller with a localization layer, being in charge of self-localization and the estimation of joint collision points with other agents. Moreover, we come up with a proprietary communication protocol to exchange trajectories with other agents. Experimental tests reveal the efficacy of proposed control system architecture.
Collision-free or contact-free routing through connected networks has been actively studied in the industrial automation and manufacturing context. Contact-free routing of personnel through connected networks (e.g., factories, retail warehouses) may
also be required in the COVID-19 context. In this context, we present an optimization framework for identifying routes through a connected network that eliminate or minimize contacts between randomly arriving agents needing to visit a subset of nodes in the network in minimal time. We simulate the agent arrival and network traversal process, and introduce stochasticity in travel speeds, node dwell times, and compliance with assigned routes. We present two optimization formulations for generating optimal routes - no-contact and minimal-contact - on a real-time basis for each agent arriving to the network given the route information of other agents already in the network. We generate results for the time-average number of contacts and normalized time spent in the network.
Optimization in distributed networks plays a central role in almost all distributed machine learning problems. In principle, the use of distributed task allocation has reduced the computational time, allowing better response rates and higher data rel
iability. However, for these computational algorithms to run effectively in complex distributed systems, the algorithms ought to compensate for communication asynchrony, network node failures and delays known as stragglers. These issues can change the effective connection topology of the network, which may vary over time, thus hindering the optimization process. In this paper, we propose a new distributed unconstrained optimization algorithm for minimizing a convex function which is adaptable to a parameter server network. In particular, the network worker nodes solve their local optimization problems, allowing the computation of their local coded gradients, which will be sent to different server nodes. Then within this parameter server platform each server node aggregates its communicated local gradients, allowing convergence to the desired optimizer. This algorithm is robust to network s worker node failures, disconnection, or delaying nodes known as stragglers. One way to overcome the straggler problem is to allow coding over the network. We further extend this coding framework to enhance the convergence of the proposed algorithm under such varying network topologies. By using coding and utilizing evaluations of gradients of uniformly bounded delay we further enhance the proposed algorithm performance. Finally, we implement the proposed scheme in MATLAB and provide comparative results demonstrating the effectiveness of the proposed framework
This paper investigates the H2 and H-infinity suboptimal distributed filtering problems for continuous time linear systems. Consider a linear system monitored by a number of filters, where each of the filters receives only part of the measured output
of the system. Each filter can communicate with the other filters according to an a priori given strongly connected weighted directed graph. The aim is to design filter gains that guarantee the H2 or H-infinity norm of the transfer matrix from the disturbance input to the output estimation error to be smaller than an a priori given upper bound, while all local filters reconstruct the full system state asymptotically. We provide a centralized design method for obtaining such H2 and H-infinity suboptimal distributed filters. The proposed design method is illustrated by a simulation example.
This paper aims to answer the research question as to optimal design of decision-making processes for autonomous vehicles (AVs), including dynamical selection of driving velocity and route choices on a transportation network. Dynamic traffic assignme
nt (DTA) has been widely used to model travelerss route choice or/and departure-time choice and predict dynamic traffic flow evolution in the short term. However, the existing DTA models do not explicitly describe ones selection of driving velocity on a road link. Driving velocity choice may not be crucial for modeling the movement of human drivers but it is a must-have control to maneuver AVs. In this paper, we aim to develop a game-theoretic model to solve for AVss optimal driving strategies of velocity control in the interior of a road link and route choice at a junction node. To this end, we will first reinterpret the DTA problem as an N-car differential game and show that this game can be tackled with a general mean field game-theoretic framework. The developed mean field game is challenging to solve because of the forward and backward structure for velocity control and the complementarity conditions for route choice. An efficient algorithm is developed to address these challenges. The model and the algorithm are illustrated on the Braess network and the OW network with a single destination. On the Braess network, we first compare the LWR based DTA model with the proposed game and find that the driving and routing control navigates AVs with overall lower costs. We then compare the total travel cost without and with the middle link and find that the Braess paradox may still arise under certain conditions. We also test our proposed model and solution algorithm on the OW network.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
