Phil 12.12.17

7:00 – 3:30 ASRC MKT

  • Need to make sure that an amplified agent also has amplified influence in calculating velocity – Fixed
  • Towards the end of this video is an interview with Ian Couzin talking about how mass communication is disrupting our ability to flock ‘correctly’ due to the decoupling of distance and information
  • Write up fire stampede. Backups everywhere, one hole, antennas burn so the AI keeps trust in A* but loses awareness as the antennas burn: “The Los Angeles Police Department asked drivers to avoid navigation apps, which are steering users onto more open routes — in this case, streets in the neighborhoods that are on fire.” [LA Times] Also this slow motion version of the same thing: For the Good of Society — and Traffic! — Delete Your Map App
  • First self-driving car ‘race’ ends in a crash at the Buenos Aires Formula E ePrix; two cars enter, one car survives
  • Taking a closer look at Oscillator Models and Collective Motion (178 Citations) and Consensus and Cooperation in Networked Multi-Agent Systems (6,291 Citations)
  • Consensus and Cooperation in Networked Multi-Agent Systems
    • Reza Olfati-SaberAlex Fax, and Richard M. Murray
    • We discuss the connections between consensus problems in networked dynamic systems and diverse applications including synchronization of coupled oscillators, flocking, formation control, fast consensus in small world networks, Markov processes and gossip-based algorithms, load balancing in networks, rendezvous in space, distributed sensor fusion in sensor networks, and belief propagation. We establish direct connections between spectral and structural properties of complex networks and the speed of information diffusion of consensus algorithms (Abstract)
    • In networks of agents (or dynamic systems), “consensus” means to reach an agreement regarding a certain quantity of interest that depends on the state of all agents. A “consensus algorithm” (or protocol) is an interaction rule that specifies the information exchange between an agent and all of its (nearest) neighbors on the network (pp 215)
      • In my work, this is agreement on heading and velocity
    • Graph Laplacians are an important point of focus of this paper. It is worth mentioning that the second smallest eigenvalue of graph Laplacians called algebraic connectivity quantifies the speed of convergence of consensus algorithms. (pp 216)
    • More recently, there has been a tremendous surge of interest among researchers from various disciplines of engineering and science in problems related to multi-agent networked systems with close ties to consensus problems. This includes subjects such as consensus [26]–[32], collective behavior of flocks and swarms [19], [33]–[37], sensor fusion [38]–[40], random networks [41], [42], synchronization of coupled oscillators [42]–[46], algebraic connectivity of complex networks [47]–[49], asynchronous distributed algorithms [30], [50], formation control for multi-robot systems [51]–[59], optimization-based cooperative control [60]–[63], dynamic graphs [64]–[67], complexity of coordinated tasks [68]–[71], and consensus-based belief propagation in Bayesian networks [72], [73]. (pp 216)
      • That is a dense lit review. How did they order it thematically?
    • A byproduct of this framework is to demonstrate that seemingly different consensus algorithms in the literature [10], [12]–[15] are closely related. (pp 216)
    • To understand the role of cooperation in performing coordinated tasks, we need to distinguish between unconstrained and constrained consensus problems. An unconstrained consensus problem is simply the alignment problem in which it suffices that the state of all agents asymptotically be the same. In contrast, in distributed computation of a function f(z), the state of all agents has to asymptotically become equal to f(z), meaning that the consensus problem is constrained. We refer to this constrained consensus problem as the f-consensus problem. (pp 217)
      • Normal exploring/flocking/stampeding is unconstrained. Herding adds constraint, though it’s dynamic. The variables that have to be manipulated in the case of constraint to result in the same amount of consensus are probably what’s interesting here. Examples could be how ‘loud’ does the herder have to be? Also, how ‘primed’ does the population have to be to accept herding?
    • …cooperation can be informally interpreted as “giving consent to providing one’s state and following a common protocol that serves the group objective.” (pp 217)
    • Formal analysis of the behavior of systems that involve more than one type of agent is more complicated, particularly, in presence of adversarial agents in noncooperative games [79], [80]. (pp 217)
    • The reason matrix theory [81] is so widely used in analysis of consensus algorithms [10], [12], [13], [14], [15], [64] is primarily due to the structure of P in (4) and its connection to graphs. (pp 218)
    • The role of consensus algorithms in particle based flocking is for an agent to achieve velocity matching with respect to its neighbors. In [19], it is demonstrated that flocks are networks of dynamic systems with a dynamic topology. This topology is a proximity graph that depends on the state of all agents and is determined locally for each agent, i.e., the topology of flocks is a state dependent graph. The notion of state-dependent graphs was introduced by Mesbahi [64] in a context that is independent of flocking. (pp 218)
      • They leave out heading alignment here. Deliberate? Or is heading alignment just another variant on velocity
    • Consider a network of decision-making agents with dynamics ẋi = ui interested in reaching a consensus via local communication with their neighbors on a graph G = (V, E). By reaching a consensus, we mean asymptotically converging to a one-dimensional agreement space characterized by the following equation: x1 = x2 = … = x (pp 219)
    • A dynamic graph G(t) = (V, E(t)) is a graph in which the set of edges E(t) and the adjacency matrix A(t) are time-varying. Clearly, the set of neighbors Ni(t) of every agent in a dynamic graph is a time-varying set as well. Dynamic graphs are useful for describing the network topology of mobile sensor networks and flocks [19]. (pp 219)
    • GraphLaplacianGradientDescent(pp 220)
  • algebraic connectivity of a graph: The algebraic connectivity (also known as Fiedler value or Fiedler eigenvalue) of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G.[1] This eigenvalue is greater than 0 if and only if G is a connected graph. This is a corollary to the fact that the number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph. The magnitude of this value reflects how well connected the overall graph is. It has been used in analysing the robustness and synchronizability of networks. (wikipedia) (pp 220)
  • According to Gershgorin theorem [81], all eigenvalues of L in the complex plane are located in a closed disk centered at delta + 0j with a radius of delta, the maximum degree of a graph (pp 220)
    • This is another measure that I can do of the nomad/flock/stampede structures combined with DBSCAN. Each agent knows what agents it is connected with, and we know how many agents there are. Each agent row should just have the number of agents it is connected to.
  • In many scenarios, networked systems can possess a dynamic topology that is time-varying due to node and link failures/creations, packet-loss [40], [98], asynchronous consensus [41], state-dependence [64], formation reconfiguration [53], evolution [96], and flocking [19], [99]. Networked systems with a dynamic topology are commonly known as switching networks. (pp 226)
  • Conclusion: A theoretical framework was provided for analysis of consensus algorithms for networked multi-agent systems with fixed or dynamic topology and directed information flow. The connections between consensus problems and several applications were discussed that include synchronization of coupled oscillators, flocking, formation control, fast consensus in small-world networks, Markov processes and gossip-based algorithms, load balancing in networks, rendezvous in space, distributed sensor fusion in sensor networks, and belief propagation. The role of “cooperation” in distributed coordination of networked autonomous systems was clarified and the effects of lack of cooperation was demonstrated by an example. It was demonstrated that notions such as graph Laplacians, nonnegative stochasticmatrices, and algebraic connectivity of graphs and digraphs play an instrumental role in analysis of consensus algorithms. We proved that algorithms introduced by Jadbabaie et al. and Fax and Murray are identical for graphs with n self-loops and are both special cases of the consensus algorithm of Olfati-Saber and Murray. The notion of Perron matrices was introduced as the discrete-time counterpart of graph Laplacians in consensus protocols. A number of fundamental spectral properties of Perron matrices were proved. This led to a unified framework for expression and analysis of consensus algorithms in both continuous-time and discrete-time. Simulation results for reaching a consensus in small-worlds versus lattice-type nearest-neighbor graphs and cooperative control of multivehicle formations were presented. (pp 231)
  • Not sure about this one. It just may be another set of algorithms to do flocking. Maybe some network implications? Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory. It is one of the papers that the Consensus and Cooperation paper above leans on heavily though…
  • The Emergence of Consensus: A Primer
    • The origin of population-scale coordination has puzzled philosophers and scientists for centuries. Recently, game theory, evolutionary approaches and complex systems science have provided quantitative insights on the mechanisms of social consensus. However, the literature is vast and scattered widely across fields, making it hard for the single researcher to navigate it. This short review aims to provide a compact overview of the main dimensions over which the debate has unfolded and to discuss some representative examples. It focuses on those situations in which consensus emerges ‘spontaneously’ in absence of centralised institutions and covers topic that include the macroscopic consequences of the different microscopic rules of behavioural contagion, the role of social networks, and the mechanisms that prevent the formation of a consensus or alter it after it has emerged. Special attention is devoted to the recent wave of experiments on the emergence of consensus in social systems.
  • Critical dynamics in population vaccinating behavior
    • Complex adaptive systems exhibit characteristic dynamics near tipping points such as critical slowing down (declining resilience to perturbations). We studied Twitter and Google search data about measles from California and the United States before and after the 2014–2015 Disneyland, California measles outbreak. We find critical slowing down starting a few years before the outbreak. However, population response to the outbreak causes resilience to increase afterward. A mathematical model of measles transmission and population vaccine sentiment predicts the same patterns. Crucially, critical slowing down begins long before a system actually reaches a tipping point. Thus, it may be possible to develop analytical tools to detect populations at heightened risk of a future episode of widespread vaccine refusal.
  • For Aaron’s Social Gradient Descent Agent research (lit review)
    • On distributed search in an uncertain environment (Something like Social Gradient Descent Agents)
      • The paper investigates the case where N agents solve a complex search problem by communicating to each other their relative successes in solving the task. The problem consists in identifying a set of unknown points distributed in an n–dimensional space. The interaction rule causes the agents to organize themselves so that, asymptotically, each agent converges to a different point. The emphasis of this paper is on analyzing the collective dynamics resulting from nonlinear interactions and, in particular, to prove convergence of the search process.
    • A New Clustering Algorithm Based Upon Flocking On Complex Network (Sizing and timing for flocking systems seems to be ok?)
      • We have proposed a model based upon flocking on a complex network, and then developed two clustering algorithms on the basis of it. In the algorithms, firstly a k-nearest neighbor (knn) graph as a weighted and directed graph is produced among all data points in a dataset each of which is regarded as an agent who can move in space, and then a time-varying complex network is created by adding long-range links for each data point. Furthermore, each data point is not only acted by its k nearest neighbors but also r long-range neighbors through fields established in space by them together, so it will take a step along the direction of the vector sum of all fields. It is more important that these long-range links provides some hidden information for each data point when it moves and at the same time accelerate its speed converging to a center. As they move in space according to the proposed model, data points that belong to the same class are located at a same position gradually, whereas those that belong to different classes are away from one another. Consequently, the experimental results have demonstrated that data points in datasets are clustered reasonably and efficiently, and the rates of convergence of clustering algorithms are fast enough. Moreover, the comparison with other algorithms also provides an indication of the effectiveness of the proposed approach.
  • Done with the first draft of the white paper! And added the RFP section to the LMN productization version
  • Amazon Sage​Maker: Amazon SageMaker is a fully managed machine learning service. With Amazon SageMaker, data scientists and developers can quickly and easily build and train machine learning models, and then directly deploy them into a production-ready hosted environment. It provides an integrated Jupyter authoring notebook instance for easy access to your data sources for exploration and analysis, so you don’t have to manage servers. It also provides common machine learning algorithms that are optimized to run efficiently against extremely large data in a distributed environment. With native support for bring-your-own-algorithms and frameworks, Amazon SageMaker offers flexible distributed training options that adjust to your specific workflows. Deploy a model into a secure and scalable environment by launching it with a single click from the Amazon SageMaker console. Training and hosting are billed by minutes of usage, with no minimum fees and no upfront commitments. (from the documentation)

4:00 – 5:00 Meeting with Aaron M. to discuss Academic RB wishlist.

4 thoughts on “Phil 12.12.17

  1. Pingback: Phil 12.13.17 | viztales

  2. Pingback: Phil 12.14.17 | viztales

  3. Pingback: Phil 12.18.17 | viztales

  4. Pingback: Phil 12.19.17 | viztales

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.