- Description of the Thematic Line +
This thematic area aims to carry out fundamental research for large-scale networked systems, thus assembling a toolbox of models and techniques that empower the remaining thematic areas and, ultimately, a range of key strategic LARSyS applications.
Our ultimate goal is to explore new frontiers of knowledge in themes associated with large-scale distributed decision.
Networks are at the core of the research done at LARSyS. Networks underlie human life: neurons interconnect to form our brain, people interact within social structures, and communication networks link people and organizations. Networks pervade most of LARSyS´s research centers: ISR and MARETEC develop networked robotic teams, IN+ studies dynamic knowledge networks, and MITI interprets users’ behaviors in online social networks and human machine interaction. In the following, we identify three natural directions for future work.
1) Network synthesis
Physical networks flourish. A particular kind of networks -- engineered networks -- is growing. They include smart grids, wireless sensor networks, cognitive radio, vehicular networks, robotic teams. The networks vary in detail but share a high-level pattern: distributed agents capture local data to learn global features of the environment (e.g., a network of cameras is deployed to discover suspicious conducts).
The need for distributed processing. Global features could in principle be inferred at a central unit in which all the local datasets are first piled up. However, this centralized approach triggers huge data congestions near the fusion point; also, an outage of the central unit beheads the network. To ensure robustness and scalability, the nascent large-scale networks demand distributed processing: raw data do not percolate across the network; rather, agents interact with neighbors to recreate the centralized solution, collectively. There is no notion of fusion center; all agents hold the result of the network computation and none is individually critical.
Distributed information systems are also key in social-technical networks -- such systems facilitate user preventive behaviors in energy and health sectors, since scientific literacy and related networks change misperceptions on risk from short to long term. The difficulty lies in combining technology and human-machine interaction (real-time information sharing and learning mechanisms) to encourage the desired behaviors.
The challenge of distributed processing. To synthesize physical networks that meet the distributed paradigm we need to design the collaborative messages, i.e., what data myopic agents transmit to each other. The lack of a general methodology to formulate such distributed interaction rules is the current showstopper. We strive for messages short in size to comply with stringent channel bandwidths, and small in number to quickly execute the network goal. These properties are challenging to secure for the foreseeable highly dynamic networks.
Optimization as a unifying framework. In that regard, the broad field of mathematical optimization is emerging as a powerful framework to express numerous applications and to derive quite effortlessly the much-needed interaction rules. Recent advances in distributed convex optimization enable the ensuing algorithms to cope seamlessly with stochastic environments, to operate with ongoing local data acquisition, and to be tuned in a principled way to strike optimal tradeoffs between message complexity and agent computation burden.
Big Data as a byproduct. The optimization viewpoint entails another reward: the solutions extend beyond the context of distributed systems, and apply to generic inference tasks on massive datasets -- a trend known as Big Data. It suffices to break down the global dataset into chewable chunks owned by virtual agents (e.g., numerical processors in a motherboard). Parallel algorithms are generated at ease.
2) Network analysis
From the fine-grain to the big picture. Physical, social or knowledge based networks realize the same principle: local-global-local interactions elicit novel behaviors. Predicting macroscopic outcomes from microscopic interchanges is the crux of network analysis; only then are can we reverse-engineer the mechanism and formulate interactions that prompt desired behaviors such as collective learning, and widespread adoption of public policies. In the context of social and knowledge based networks, analysis provides insights on how social phenomena arise through risk sharing activities. In the context of physical networks, analysis allows to anticipate the quantitative performance of a given distributed algorithm.
Model sharing. Quantitative models are more elusive for social and knowledge based networks. Yet, recent work has successfully validated analytical models from engineered networks in the social network arena. For example, gossip spreads in online social networks like viruses in computer networks, and learning in social networks follows dynamics similar to coordination of fleets of robotic vehicles. Such work is strong evidence that network analysis provides fertile ground for collaboration between LARSyS groups, by leveraging the rich theory of stochastic dynamical systems.
Structure discovering. The topology of social and knowledge based networks is often unknown. A major challenge consists in unveiling the network structure from the observable individual behaviors. This problem falls within the purview of generative probabilistic graphical models in which researchers recently built a suite of techniques to infer latent (hidden) network substructures. This research topic furnishes yet another channel for collaboration between signal processing and public policy making communities at LARSyS.
3) Networked decision-making
In problems where decisions are based on the situational awareness and assessment provided by a team of agents (networked sensors, networked sensors and actuators and/or robots), decision-theoretic approaches to sequential decision-making under uncertainty play a significant role, as both the observation of the system state and the effects of the actions taken are contaminated with noise and uncertainty, and the optimal policy mapping states onto actions in the presence of uncertainty is obtained (both using model-based dynamic programming and model-free reinforcement learning approaches). This is particularly compelling when the agents in must exchange information over low bandwidth communication channels that are plagued with temporary losses and exhibit time-varying communication topologies. Bayesian inference and optimization methods are also crucial for (active) cooperative perception, where a networked sensor team takes decisions on the optimal estimate of an object location or trajectory and/or on the actions to be taken to actively reduce uncertainty on the decision.
- Structure of the Thematic Line +
João Xavier (ISR) is the Principal Investigator of this thematic area. Evangelos Karapanos (MITI) and Muriel Pádua and Hugo Horta (IN+) form with him the thematic area management committee. Together, they will be responsible for planning the activities mentioned below, and coordinating the scientific strategy of this thematic area in close collaboration with the proposed challenges of laboratories and other thematic areas. The involvement of researchers of various research groups in the management board will guarantee the integration of activities and close collaboration with the research objectives and purposes of the other areas and the laboratory as a whole.
To foster collaboration between LARSyS groups within the context of this thematic area we envision three mechanisms: 1) periodic monthly-based meetings and seminars to share results and keep the groups updated; 2) joint publications in cross-disciplinary journals to corroborate the benefits of the synergetic effort undertaken, and 3) a Summer School with leading experts from the fields of distributed information processing and decision-making, human machine interaction, and knowledge based (including scientometricians) and behavioral science. This will be a satellite event of the annual LARSyS workshop, which also aims to introduce PhD students and senior researchers to the encompassing mathematical framework of network science.
- Objectives of the Thematic Line +
Representative research challenges are fleshed out in the following.
Distributed optimization: augmented lagrangian methods. Numerous scenarios reduce to solving convex optimization problems in a distributed manner. Furthermore, the objective function commonly exhibits a separable structure: it is the sum of convex functions, each of which is private knowledge of an agent (e.g., spectrum sensing for cognitive radio networks). The main distributed algorithms proposed so far are either based on augmented lagrangian (AL) formulations, or of the gradient type. The AL methods require the agents to solve a local optimization problem at each iteration; gradient methods involve simpler computation per iteration, but require more communication between agents. The AL methods are thus communication-efficient but lack theoretical performance guarantees, thus limiting their usage in real-time applications. We propose to close this gap by assessing theoretically how the number of communications of AL methods scale with the network size and topology, and how they perform in the face of randomly fading links and noisy communication channels.
Distributed game theory. Game-theoretic techniques have been recently applied to various resource-allocation problems to achieve distributed solution methods. Game theory is expected to inspire novel approaches to distributed optimization: the key idea consists in interpreting the solution of an optimization problem as the emergent behavior of a set of agents interacting selfishly; the minimum of the problem is seen as the outcome of the game -- the Nash equilibrium. From this standpoint, a distributed optimization algorithm for a given problem can be obtained by finding a suitable associated game, and running well-known game-learning strategies. However, it is unknown how to systematically disclose the appropriate game. We plan to explore the link between games and optimization to generate new distributed optimization methods. We will build on our recent work, in which we successfully extended the fictitious play learning strategy to the distributed setting.
The role of networks for social-technological systems, innovation and economic growth. This area is transversal since networks are pervasive -- all requiring backwards (science) and forwards edges (demand) -- and have different architectures and challenges. For example, biomedical governance requires new agents and complementarities between them (e.g, Hospitals, patients, and new technologically based firms). In the aeronautics, there is the need for analysis of supply chains while in the energy sector, user participation needs to be fostered (i.e, demand side of innovation) to help diminish the rising energy consumption and CO2 emissions profiles (electricity and gas in households and fuels in vehicles). Representing users communities through a network in order to understand mechanisms of propagation of prosocial behavior and participation in public good games is critical.
Decentralized decision-making under uncertainty. Decision-making under uncertainty by a team of networked decision-makers raises open problems, in particular concerning the balance between the local information obtained at each network node and the information required from the other nodes, that must be communicated over a channel that is often faulty and may impose stringent bandwidth limitations. A tradeoff between communication cost and decentralized performance arises in these situations. Methods that i) minimize the amount of information communicated when the local information suffices to obtain the optimal policy, ii) reduce the complexity of decentralized decision-making by restricting the state, observation and/or actions space dimensions, iii) are event-driven, asynchronous, and turn an exponential dependence of observations on the number of agents into a linear one, can lead to an improvement of the performance/cost ratio in decentralized decision-making.