Multi-agent systems (MASs) consisting of a number of autonomous agents that communicate, coordinate, and jointly sense the environment to achieve complex missions can be found in a variety of applications such as robotics, smart cities, and internet-of-things applications. Modeling and monitoring MAS requirements to guarantee overall mission objectives, safety, and reliability is an important problem. Such requirements implicitly require reasoning about diverse sensing and communication modalities between agents, analysis of the dependencies between agent tasks, and the spatial or virtual distance between agents. To capture such rich MAS requirements, we model agent interactions via multiple directed graphs, and introduce a new logic -- Spatio-Temporal Logic with Graph Operators (STL-GO). The key innovation in STL-GO are graph operators that enable us to reason about the number of agents along either the incoming or outgoing edges of the underlying interaction graph that satisfy a given property of interest; for example, the requirement that an agent should sense at least two neighboring agents whose task graphs indicate the ability to collaborate. We then propose novel distributed monitoring conditions for individual agents that use only local information to determine whether or not an STL-GO specification is satisfied. We compare the expressivity of STL-GO against existing spatio-temporal logic formalisms, and demonstrate the utility of STL-GO and our distributed monitors in a bike-sharing and a multi-drone case study.

Alzheimer's disease (AD) affects 50 million people worldwide and is projected to overwhelm 152 million by 2050. AD is characterized by cognitive decline due partly to disruptions in metabolic brain connectivity. Thus, early and accurate detection of metabolic brain network impairments is crucial for AD management. Chief to identifying such impairments is FDG-PET data. Despite advancements, most graph-based studies using FDG-PET data rely on group-level analysis or thresholding. Yet, group-level analysis can veil individual differences and thresholding may overlook weaker but biologically critical brain connections. Additionally, machine learning-based AD prediction largely focuses on univariate outcomes, such as disease status. Here, we introduce explainable graph-theoretical machine learning (XGML), a framework employing kernel density estimation and dynamic time warping to construct individual metabolic brain graphs that capture the distance between pair-wise brain regions and identify subgraphs most predictive of multivariate AD-related outcomes. Using FDG-PET data from the Alzheimer's Disease Neuroimaging Initiative, XGML builds metabolic brain graphs and uncovers subgraphs predictive of eight AD-related cognitive scores in new subjects. XGML shows robust performance, particularly for predicting scores measuring learning, memory, language, praxis, and orientation, such as CDRSB ($r = 0.74$), ADAS11 ($r = 0.73$), and ADAS13 ($r = 0.71$). Moreover, XGML unveils key edges jointly but differentially predictive of several AD-related outcomes; they may serve as potential network biomarkers for assessing overall cognitive decline. Together, we show the promise of graph-theoretical machine learning in biomarker discovery and disease prediction and its potential to improve our understanding of network neural mechanisms underlying AD.

The formalism of Simple Temporal Networks (STNs) provides methods for evaluating the feasibility of temporal plans. The basic formalism deals with the consistency of quantitative temporal requirements on scheduled events. This implicitly assumes a single agent has full control over the timing of events. The extension of Simple Temporal Networks with Uncertainty (STNU) introduces uncertainty into the timing of some events. Two main approaches to the feasibility of STNUs involve (1) where a single schedule works irrespective of the duration outcomes, called Strong Controllability, and (2) whether a strategy exists to schedule future events based on the outcomes of past events, called Dynamic Controllability. Case (1) essentially assumes the timing of uncertain events cannot be observed by the agent while case (2) assumes full observability. The formalism of Partially Observable Simple Temporal Networks with Uncertainty (POSTNU) provides an intermediate stance between these two extremes, where a known subset of the uncertain events can be observed when they occur. A sound and complete polynomial algorithm to determining the Dynamic Controllability of POSTNUs has not previously been known; we present one in this paper. This answers an open problem that has been posed in the literature. The approach we take factors the problem into Strong Controllability micro-problems in an overall Dynamic Controllability macro-problem framework. It generalizes the notion of labeled distance graph from STNUs. The generalized labels are expressed as max/min expressions involving the observables. The paper introduces sound generalized reduction rules that act on the generalized labels. These incorporate tightenings based on observability that preserve dynamic viable strategies. It is shown that if the generalized reduction rules reach quiescence without exposing an inconsistency, then the POSTNU is Dynamically Controllable (DC). The paper also presents algorithms that apply the reduction rules in an organized way and reach quiescence in a polynomial number of steps if the POSTNU is Dynamically Controllable. Remarkably, the generalized perspective leads to a simpler and more uniform framework that applies also to the STNU special case. It helps illuminate the previous methods inasmuch as the max/min label representation is more semantically clear than the ad-hoc upper/lower case labels previously used.

In this technical report, we present our solution for the Baidu KDD Cup 2022 Spatial Dynamic Wind Power Forecasting Challenge. Wind power is a rapidly growing source of clean energy. Accurate wind power forecasting is essential for grid stability and the security of supply. Therefore, organizers provide a wind power dataset containing historical data from 134 wind turbines and launch the Baidu KDD Cup 2022 to examine the limitations of current methods for wind power forecasting. The average of RMSE (Root Mean Square Error) and MAE (Mean Absolute Error) is used as the evaluation score. We adopt two spatial-temporal graph neural network models, i.e., AGCRN and MTGNN, as our basic models. We train AGCRN by 5-fold cross-validation and additionally train MTGNN directly on the training and validation sets. Finally, we ensemble the two models based on the loss values of the validation set as our final submission. Using our method, our team \team achieves -45.36026 on the test set. We release our codes on Github (https://github.com/BUAABIGSCity/KDDCUP2022) for reproduction.

Urban ride-hailing demand prediction is a crucial but challenging task for intelligent transportation system construction. Predictable ride-hailing demand can facilitate more reasonable vehicle scheduling and online car-hailing platform dispatch. Conventional deep learning methods with no external structured data can be accomplished via hybrid models of CNNs and RNNs by meshing plentiful pixel-level labeled data, but spatial data sparsity and limited learning capabilities on temporal long-term dependencies are still two striking bottlenecks. To address these limitations, we propose a new virtual graph modeling method to focus on significant demand regions and a novel Deep Multi-View Spatiotemporal Virtual Graph Neural Network (DMVST-VGNN) to strengthen learning capabilities of spatial dynamics and temporal long-term dependencies. Specifically, DMVST-VGNN integrates the structures of 1D Convolutional Neural Network, Multi Graph Attention Neural Network and Transformer layer, which correspond to short-term temporal dynamics view, spatial dynamics view and long-term temporal dynamics view respectively. In this paper, experiments are conducted on two large-scale New York City datasets in fine-grained prediction scenes. And the experimental results demonstrate effectiveness and superiority of DMVST-VGNN framework in significant citywide ride-hailing demand prediction.

TCSPs (Temporal Constraint Satisfaction Problems), as defined in [Dechter et al., 1991], get rid of unary constraints by binarising them after having added an "origin of the world" variable. The constraints are therefore exclusively binary; additionally, a TCSP verifies the property that it is node-consistent and arc-consistent. Path-consistency, the next higher local consistency, solves the consistency problem of a convex TCSP, referred to in [Dechter et al., 1991] as an STP (Simple Temporal Problem); more than that, the output of path-consistency applied to an n+1-variable STP is a minimal and strongly n+1-consistent STP. Weaker versions of path-consistency, aimed at avoiding what is referred to in [Schwalb and Dechter, 1997] as the "fragmentation problem", are used as filtering procedures in recursive backtracking algorithms for the consistency problem of a general TCSP. In this work, we look at the constraints between the "origin of the world" variable and the other variables, as the (binarised) domains of these other variables. With this in mind, we define a notion of arc-consistency for TCSPs, which we will refer to as binarised-domains Arc-Consistency, or bdArc-Consistency for short. We provide an algorithm achieving bdArc-Consistency for a TCSP, which we will refer to as bdAC3, for it is an adaptation of Mackworth's [1977] well-known arc-consistency algorithm AC3. We show that bdArc-Consistency computes the minimal (binarised) domains of an STP. We then show how to use the result in a general TCSP solver, in a TCSP-based job shop scheduler, and in generalising the well-known Dijkstra's one-to-all shortest paths algorithm.

This work presents Drake, a dynamic executive for temporal plans with choice. Dynamic plan execution strategies allow an autonomous agent to react quickly to unfolding events, improving the robustness of the agent. Prior work developed methods for dynamically dispatching Simple Temporal Networks, and further research enriched the expressiveness of the plans executives could handle, including discrete choices, which are the focus of this work. However, in some approaches to date, these additional choices induce significant storage or latency requirements to make flexible execution possible. Drake is designed to leverage the low latency made possible by a preprocessing step called compilation, while avoiding high memory costs through a compact representation. We leverage the concepts of labels and environments, taken from prior work in Assumption-based Truth Maintenance Systems (ATMS), to concisely record the implications of the discrete choices, exploiting the structure of the plan to avoid redundant reasoning or storage. Our labeling and maintenance scheme, called the Labeled Value Set Maintenance System, is distinguished by its focus on properties fundamental to temporal problems, and, more generally, weighted graph algorithms. In particular, the maintenance system focuses on maintaining a minimal representation of non-dominated constraints. We benchmark Drake's performance on random structured problems, and find that Drake reduces the size of the compiled representation by a factor of over 500 for large problems, while incurring only a modest increase in run-time latency, compared to prior work in compiled executives for temporal plans with discrete choices.

The Simple Temporal Problem (STP) is a popular representation for solving centralized scheduling and planning problems. When scheduling agents are associated with different users who need to coordinate some of their activities, however, considerations such as privacy and scalability suggest solving the joint STP in a more distributed manner. Building on recent advances in STP algorithms that exploit loosely-coupled problem structure, this paper develops and evaluates algorithms for solving the multiagent STP. We define a partitioning of the multiagent STP with provable privacy guarantees, and show that our algorithms can exploit this partitioning while still finding the tightest consistent bounds on timepoints that must be coordinated across agents. We also demonstrate empirically that our algorithms can exploit concurrent computation, leading to solution time speed-ups over state-of-the-art centralized approaches, and enabling scalability to problems involving larger numbers of loosely-coupled agents.

The dispatcher uses the dispatchable form to quickly make dynamic scheduling decisions. As autonomous systems become more capable and common, However, developing flexible executives for plans with they will need to reason about complex tasks and robustly choices, has been more difficult. Kim, Williams, and execute plans in uncertain environments. In previous work, Abramson present an executive called Kirk, which uses a Williams et al. introduced the Reactive Model-Based Programming deliberative planning step to change the execution sequence Language (RMPL), which is designed to allow online (2001). Although their results show improvement engineers to simply and intuitively express the desired behavior over prior planning systems, the latency is still too high for of the system (2003). Then the agent's executive determines tightly coupled systems, for example robots working with the correct sequence of actions to accomplish this humans or walking robots with fast dynamics. Recently, behavior, relieving the programmer of explicitly coding that Shah and Williams extended the compiler and dispatcher logic. RMPL programs often involve temporal constraints model to Temporal Constraint Satisfaction Problems (TCwhich the executives must reason over. SPs), a type of temporal problems with choice, by compactly Kim, Williams, and Abramson previously developed recording the possible set of solutions and efficiently Temporal Plan Networks (TPNs) as a temporal constraint reasoning over the possible options (2008).