Showing 1–33 of 33 results for author: Qiu, F

Settling the Communication Complexity of VCG-based Mechanisms for all Approximation Guarantees

Authors: Frederick V. Qiu, S. Matthew Weinberg

Abstract: We consider truthful combinatorial auctions with items $M = [m]$ for sale to $n$ bidders, where each bidder $i$ has a private monotone valuation $v_i : 2^M \to R_+$. Among truthful mechanisms, maximal-in-range (MIR) mechanisms achieve the best-known approximation guarantees among all poly-communication deterministic truthful mechanisms in all previously-studied settings. Our work settles the commu… ▽ More We consider truthful combinatorial auctions with items $M = [m]$ for sale to $n$ bidders, where each bidder $i$ has a private monotone valuation $v_i : 2^M \to R_+$. Among truthful mechanisms, maximal-in-range (MIR) mechanisms achieve the best-known approximation guarantees among all poly-communication deterministic truthful mechanisms in all previously-studied settings. Our work settles the communication necessary to achieve any approximation guarantee via an MIR mechanism. Specifically: Let MIRsubmod$(m,k)$ denote the best approximation guarantee achievable by an MIR mechanism using $2^k$ communication between bidders with submodular valuations over $m$ items. Then for all $k = Ω(\log(m))$, MIRsubmod$(m,k) = Ω(\sqrt{m/(k\log(m/k))})$. When $k = Θ(\log(m))$, this improves the previous best lower bound for poly-comm. MIR mechanisms from $Ω(m^{1/3}/\log^{2/3}(m))$ to $Ω(\sqrt{m}/\log(m))$. We also have MIRsubmod$(m,k) = O(\sqrt{m/k})$. Moreover, our mechanism is optimal w.r.t. the value query and succinct representation models. When $k = Θ(\log(m))$, this improves the previous best approximation guarantee for poly-comm. MIR mechanisms from $O(\sqrt{m})$ to $O(\sqrt{m/\log(m)})$. Let also MIRgen$(m,k)$ denote the best approximation guarantee achievable by an MIR mechanism using $2^k$ communication between bidders with general valuations over $m$ items. Then for all $k = Ω(\log(m))$, MIRgen$(m,k) = Ω(m/k)$. When $k = Θ(\log(m))$, this improves the previous best lower bound for poly-comm. MIR mechanisms from $Ω(m/\log^2(m))$ to $Ω(m/\log(m))$. We also have MIRgen$(m,k) = O(m/k)$. Moreover, our mechanism is optimal w.r.t. the value query and succinct representation models. When $k = Θ(\log(m))$, this improves the previous best approximation guarantee for poly-comm. MIR mechanisms from $O(m/\sqrt{\log(m)})$ to $O(m/\log(m))$. △ Less

Submitted 31 March, 2024; originally announced April 2024.

Comments: 40 pages, 2 figures, to appear in STOC 2024

ECNet: Effective Controllable Text-to-Image Diffusion Models

Authors: Sicheng Li, Keqiang Sun, Zhixin Lai, Xiaoshi Wu, Feng Qiu, Haoran Xie, Kazunori Miyata, Hongsheng Li

Abstract: The conditional text-to-image diffusion models have garnered significant attention in recent years. However, the precision of these models is often compromised mainly for two reasons, ambiguous condition input and inadequate condition guidance over single denoising loss. To address the challenges, we introduce two innovative solutions. Firstly, we propose a Spatial Guidance Injector (SGI) which en… ▽ More The conditional text-to-image diffusion models have garnered significant attention in recent years. However, the precision of these models is often compromised mainly for two reasons, ambiguous condition input and inadequate condition guidance over single denoising loss. To address the challenges, we introduce two innovative solutions. Firstly, we propose a Spatial Guidance Injector (SGI) which enhances conditional detail by encoding text inputs with precise annotation information. This method directly tackles the issue of ambiguous control inputs by providing clear, annotated guidance to the model. Secondly, to overcome the issue of limited conditional supervision, we introduce Diffusion Consistency Loss (DCL), which applies supervision on the denoised latent code at any given time step. This encourages consistency between the latent code at each time step and the input signal, thereby enhancing the robustness and accuracy of the output. The combination of SGI and DCL results in our Effective Controllable Network (ECNet), which offers a more accurate controllable end-to-end text-to-image generation framework with a more precise conditioning input and stronger controllable supervision. We validate our approach through extensive experiments on generation under various conditions, such as human body skeletons, facial landmarks, and sketches of general objects. The results consistently demonstrate that our method significantly enhances the controllability and robustness of the generated images, outperforming existing state-of-the-art controllable text-to-image models. △ Less

Submitted 27 March, 2024; originally announced March 2024.

Affective Behaviour Analysis via Integrating Multi-Modal Knowledge

Authors: Wei Zhang, Feng Qiu, Chen Liu, Lincheng Li, Heming Du, Tiancheng Guo, Xin Yu

Abstract: Affective Behavior Analysis aims to facilitate technology emotionally smart, creating a world where devices can understand and react to our emotions as humans do. To comprehensively evaluate the authenticity and applicability of emotional behavior analysis techniques in natural environments, the 6th competition on Affective Behavior Analysis in-the-wild (ABAW) utilizes the Aff-Wild2, Hume-Vidmimic… ▽ More Affective Behavior Analysis aims to facilitate technology emotionally smart, creating a world where devices can understand and react to our emotions as humans do. To comprehensively evaluate the authenticity and applicability of emotional behavior analysis techniques in natural environments, the 6th competition on Affective Behavior Analysis in-the-wild (ABAW) utilizes the Aff-Wild2, Hume-Vidmimic2, and C-EXPR-DB datasets to set up five competitive tracks, i.e., Valence-Arousal (VA) Estimation, Expression (EXPR) Recognition, Action Unit (AU) Detection, Compound Expression (CE) Recognition, and Emotional Mimicry Intensity (EMI) Estimation. In this paper, we present our method designs for the five tasks. Specifically, our design mainly includes three aspects: 1) Utilizing a transformer-based feature fusion module to fully integrate emotional information provided by audio signals, visual images, and transcripts, offering high-quality expression features for the downstream tasks. 2) To achieve high-quality facial feature representations, we employ Masked-Auto Encoder as the visual features extraction model and fine-tune it with our facial dataset. 3) Considering the complexity of the video collection scenes, we conduct a more detailed dataset division based on scene characteristics and train the classifier for each scene. Extensive experiments demonstrate the superiority of our designs. △ Less

Submitted 16 March, 2024; originally announced March 2024.

Comments: 11 pages, 1 figure

Federated Battery Diagnosis and Prognosis

Authors: Nur Banu Altinpulluk, Deniz Altinpulluk, Paritosh Ramanan, Noah Paulson, Feng Qiu, Susan Babinec, Murat Yildirim

Abstract: Battery diagnosis, prognosis and health management models play a critical role in the integration of battery systems in energy and mobility fields. However, large-scale deployment of these models is hindered by a myriad of challenges centered around data ownership, privacy, communication, and processing. State-of-the-art battery diagnosis and prognosis methods require centralized collection of dat… ▽ More Battery diagnosis, prognosis and health management models play a critical role in the integration of battery systems in energy and mobility fields. However, large-scale deployment of these models is hindered by a myriad of challenges centered around data ownership, privacy, communication, and processing. State-of-the-art battery diagnosis and prognosis methods require centralized collection of data, which further aggravates these challenges. Here we propose a federated battery prognosis model, which distributes the processing of battery standard current-voltage-time-usage data in a privacy-preserving manner. Instead of exchanging raw standard current-voltage-time-usage data, our model communicates only the model parameters, thus reducing communication load and preserving data confidentiality. The proposed model offers a paradigm shift in battery health management through privacy-preserving distributed methods for battery data processing and remaining lifetime prediction. △ Less

Submitted 14 October, 2023; originally announced October 2023.

Assessing Electricity Service Unfairness with Transfer Counterfactual Learning

Authors: Song Wei, Xiangrui Kong, Alinson Santos Xavier, Shixiang Zhu, Yao Xie, Feng Qiu

Abstract: Energy justice is a growing area of interest in interdisciplinary energy research. However, identifying systematic biases in the energy sector remains challenging due to confounding variables, intricate heterogeneity in counterfactual effects, and limited data availability. First, this paper demonstrates how one can evaluate counterfactual unfairness in a power system by analyzing the average caus… ▽ More Energy justice is a growing area of interest in interdisciplinary energy research. However, identifying systematic biases in the energy sector remains challenging due to confounding variables, intricate heterogeneity in counterfactual effects, and limited data availability. First, this paper demonstrates how one can evaluate counterfactual unfairness in a power system by analyzing the average causal effect of a specific protected attribute. Subsequently, we use subgroup analysis to handle model heterogeneity and introduce a novel method for estimating counterfactual unfairness based on transfer learning, which helps to alleviate the data scarcity in each subgroup. In our numerical analysis, we apply our method to a unique large-scale customer-level power outage data set and investigate the counterfactual effect of demographic factors, such as income and age of the population, on power outage durations. Our results indicate that low-income and elderly-populated areas consistently experience longer power outages under both daily and post-disaster operations, and such discrimination is exacerbated under severe conditions. These findings suggest a widespread, systematic issue of injustice in the power service systems and emphasize the necessity for focused interventions in disadvantaged communities. △ Less

Submitted 24 January, 2024; v1 submitted 4 October, 2023; originally announced October 2023.

Comments: The preliminary version titled "Detecting Electricity Service Equity Issues with Transfer Counterfactual Learning on Large-Scale Outage Datasets" is presented at NeurIPS 2023 Workshops on Causal Representation Learning (CRL) and Algorithmic Fairness through the Lens of Time (AFT); See v1

Random Projections of Sparse Adjacency Matrices

Authors: Frank Qiu

Abstract: We analyze a random projection method for adjacency matrices, studying its utility in representing sparse graphs. We show that these random projections retain the functionality of their underlying adjacency matrices while having extra properties that make them attractive as dynamic graph representations. In particular, they can represent graphs of different sizes and vertex sets in the same space,… ▽ More We analyze a random projection method for adjacency matrices, studying its utility in representing sparse graphs. We show that these random projections retain the functionality of their underlying adjacency matrices while having extra properties that make them attractive as dynamic graph representations. In particular, they can represent graphs of different sizes and vertex sets in the same space, allowing for the aggregation and manipulation of graphs in a unified manner. We also provide results on how the size of the projections need to scale in order to preserve accurate graph operations, showing that the size of the projections can scale linearly with the number of vertices while accurately retaining first-order graph information. We conclude by characterizing our random projection as a distance-preserving map of adjacency matrices analogous to the usual Johnson-Lindenstrauss map. △ Less

Submitted 4 September, 2023; originally announced September 2023.

Comments: 21 pages

MSC Class: 65F50

Tensor Products and Hyperdimensional Computing

Authors: Frank Qiu

Abstract: Following up on a previous analysis of graph embeddings, we generalize and expand some results to the general setting of vector symbolic architectures (VSA) and hyperdimensional computing (HDC). Importantly, we explore the mathematical relationship between superposition, orthogonality, and tensor product. We establish the tensor product representation as the central representation, with a suite of… ▽ More Following up on a previous analysis of graph embeddings, we generalize and expand some results to the general setting of vector symbolic architectures (VSA) and hyperdimensional computing (HDC). Importantly, we explore the mathematical relationship between superposition, orthogonality, and tensor product. We establish the tensor product representation as the central representation, with a suite of unique properties. These include it being the most general and expressive representation, as well as being the most compressed representation that has errorrless unbinding and detection. △ Less

Submitted 20 May, 2023; v1 submitted 17 May, 2023; originally announced May 2023.

Comments: 18 pages

MSC Class: 68T30

Multi-modal Facial Affective Analysis based on Masked Autoencoder

Authors: Wei Zhang, Bowen Ma, Feng Qiu, Yu Ding

Abstract: Human affective behavior analysis focuses on analyzing human expressions or other behaviors to enhance the understanding of human psychology. The CVPR 2023 Competition on Affective Behavior Analysis in-the-wild (ABAW) is dedicated to providing high-quality and large-scale Aff-wild2 for the recognition of commonly used emotion representations, such as Action Units (AU), basic expression categories(… ▽ More Human affective behavior analysis focuses on analyzing human expressions or other behaviors to enhance the understanding of human psychology. The CVPR 2023 Competition on Affective Behavior Analysis in-the-wild (ABAW) is dedicated to providing high-quality and large-scale Aff-wild2 for the recognition of commonly used emotion representations, such as Action Units (AU), basic expression categories(EXPR), and Valence-Arousal (VA). The competition is committed to making significant strides in improving the accuracy and practicality of affective analysis research in real-world scenarios. In this paper, we introduce our submission to the CVPR 2023: ABAW5. Our approach involves several key components. First, we utilize the visual information from a Masked Autoencoder(MAE) model that has been pre-trained on a large-scale face image dataset in a self-supervised manner. Next, we finetune the MAE encoder on the image frames from the Aff-wild2 for AU, EXPR and VA tasks, which can be regarded as a static and uni-modal training. Additionally, we leverage the multi-modal and temporal information from the videos and implement a transformer-based framework to fuse the multi-modal features. Our approach achieves impressive results in the ABAW5 competition, with an average F1 score of 55.49\% and 41.21\% in the AU and EXPR tracks, respectively, and an average CCC of 0.6372 in the VA track. Our approach ranks first in the EXPR and AU tracks, and second in the VA track. Extensive quantitative experiments and ablation studies demonstrate the effectiveness of our proposed method. △ Less

Submitted 11 April, 2023; v1 submitted 19 March, 2023; originally announced March 2023.

InterMulti:Multi-view Multimodal Interactions with Text-dominated Hierarchical High-order Fusion for Emotion Analysis

Authors: Feng Qiu, Wanzeng Kong, Yu Ding

Abstract: Humans are sophisticated at reading interlocutors' emotions from multimodal signals, such as speech contents, voice tones and facial expressions. However, machines might struggle to understand various emotions due to the difficulty of effectively decoding emotions from the complex interactions between multimodal signals. In this paper, we propose a multimodal emotion analysis framework, InterMulti… ▽ More Humans are sophisticated at reading interlocutors' emotions from multimodal signals, such as speech contents, voice tones and facial expressions. However, machines might struggle to understand various emotions due to the difficulty of effectively decoding emotions from the complex interactions between multimodal signals. In this paper, we propose a multimodal emotion analysis framework, InterMulti, to capture complex multimodal interactions from different views and identify emotions from multimodal signals. Our proposed framework decomposes signals of different modalities into three kinds of multimodal interaction representations, including a modality-full interaction representation, a modality-shared interaction representation, and three modality-specific interaction representations. Additionally, to balance the contribution of different modalities and learn a more informative latent interaction representation, we developed a novel Text-dominated Hierarchical High-order Fusion(THHF) module. THHF module reasonably integrates the above three kinds of representations into a comprehensive multimodal interaction representation. Extensive experimental results on widely used datasets, (i.e.) MOSEI, MOSI and IEMOCAP, demonstrate that our method outperforms the state-of-the-art. △ Less

Submitted 20 December, 2022; originally announced December 2022.

Comments: 9 pages, 3 figures. arXiv admin note: text overlap with arXiv:2212.08661

EffMulti: Efficiently Modeling Complex Multimodal Interactions for Emotion Analysis

Authors: Feng Qiu, Chengyang Xie, Yu Ding, Wanzeng Kong

Abstract: Humans are skilled in reading the interlocutor's emotion from multimodal signals, including spoken words, simultaneous speech, and facial expressions. It is still a challenge to effectively decode emotions from the complex interactions of multimodal signals. In this paper, we design three kinds of multimodal latent representations to refine the emotion analysis process and capture complex multimod… ▽ More Humans are skilled in reading the interlocutor's emotion from multimodal signals, including spoken words, simultaneous speech, and facial expressions. It is still a challenge to effectively decode emotions from the complex interactions of multimodal signals. In this paper, we design three kinds of multimodal latent representations to refine the emotion analysis process and capture complex multimodal interactions from different views, including a intact three-modal integrating representation, a modality-shared representation, and three modality-individual representations. Then, a modality-semantic hierarchical fusion is proposed to reasonably incorporate these representations into a comprehensive interaction representation. The experimental results demonstrate that our EffMulti outperforms the state-of-the-art methods. The compelling performance benefits from its well-designed framework with ease of implementation, lower computing complexity, and less trainable parameters. △ Less

Submitted 15 December, 2022; originally announced December 2022.

Comments: 6 pages,1 figure

Commutativity and Disentanglement from the Manifold Perspective

Authors: Frank Qiu

Abstract: In this paper, we interpret disentanglement as the discovery of local charts of the data manifold and trace how this definition naturally leads to an equivalent condition for disentanglement: commutativity between factors of variation. We study the impact of this manifold framework to two classes of problems: learning matrix exponential operators and compressing data-generating models. In each pro… ▽ More In this paper, we interpret disentanglement as the discovery of local charts of the data manifold and trace how this definition naturally leads to an equivalent condition for disentanglement: commutativity between factors of variation. We study the impact of this manifold framework to two classes of problems: learning matrix exponential operators and compressing data-generating models. In each problem, the manifold perspective yields interesting results about the feasibility and fruitful approaches their solutions. We also link our manifold framework to two other common disentanglement paradigms: group theoretic and probabilistic approaches to disentanglement. In each case, we show how these frameworks can be merged with our manifold perspective. Importantly, we recover commutativity as a central property in both alternative frameworks, further highlighting its importance in disentanglement. △ Less

Submitted 16 December, 2023; v1 submitted 14 October, 2022; originally announced October 2022.

Comments: 26 pages

MSC Class: 68P02

Graph Embeddings via Tensor Products and Approximately Orthonormal Codes

Authors: Frank Qiu

Abstract: We propose a dynamic graph representation method, showcasing its rich representational capacity and establishing some of its theoretical properties. Our representation falls under the bind-and-sum approach in hyperdimensional computing (HDC), and we show that the tensor product is the most general binding operation that respects the superposition principle employed in HDC. We also establish some p… ▽ More We propose a dynamic graph representation method, showcasing its rich representational capacity and establishing some of its theoretical properties. Our representation falls under the bind-and-sum approach in hyperdimensional computing (HDC), and we show that the tensor product is the most general binding operation that respects the superposition principle employed in HDC. We also establish some precise results characterizing the behavior of our method, including a memory vs. size analysis of how our representation's size must scale with the number of edges in order to retain accurate graph operations. True to its HDC roots, we also compare our graph representation to another typical HDC representation, the Hadamard-Rademacher scheme, showing that these two graph representations have the same memory-capacity scaling. We establish a link to adjacency matrices, showing that our method is a pseudo-orthogonal generalization of adjacency matrices. In light of this, we briefly discuss its applications toward a dynamic compressed representation of large sparse graphs. △ Less

Submitted 3 June, 2023; v1 submitted 18 August, 2022; originally announced August 2022.

Comments: 59 pages, 2 tables. arxiv admin note: substantial text overlap with arXiv:2208.08769

MSC Class: 68P02

Memory and Capacity of Graph Embedding Methods

Authors: Frank Qiu

Abstract: THIS PAPER IS NOW DEFUNCT: Check out "Graph Embeddings via Tensor Products and Approximately Orthonormal Codes", where it has been combined into one paper. THIS PAPER IS NOW DEFUNCT: Check out "Graph Embeddings via Tensor Products and Approximately Orthonormal Codes", where it has been combined into one paper. △ Less

Submitted 13 May, 2023; v1 submitted 18 August, 2022; originally announced August 2022.

Comments: 23 Pages, 2 Figures

MSC Class: 68P02

Submodular Dominance and Applications

Authors: Frederick Qiu, Sahil Singla

Abstract: In submodular optimization we often deal with the expected value of a submodular function $f$ on a distribution $\mathcal{D}$ over sets of elements. In this work we study such submodular expectations for negatively dependent distributions. We introduce a natural notion of negative dependence, which we call Weak Negative Regression (WNR), that generalizes both Negative Association and Negative Regr… ▽ More In submodular optimization we often deal with the expected value of a submodular function $f$ on a distribution $\mathcal{D}$ over sets of elements. In this work we study such submodular expectations for negatively dependent distributions. We introduce a natural notion of negative dependence, which we call Weak Negative Regression (WNR), that generalizes both Negative Association and Negative Regression. We observe that WNR distributions satisfy Submodular Dominance, whereby the expected value of $f$ under $\mathcal{D}$ is at least the expected value of $f$ under a product distribution with the same element-marginals. Next, we give several applications of Submodular Dominance to submodular optimization. In particular, we improve the best known submodular prophet inequalities, we develop new rounding techniques for polytopes of set systems that admit negatively dependent distributions, and we prove existence of contention resolution schemes for WNR distributions. △ Less

Submitted 11 July, 2022; originally announced July 2022.

Comments: Appears in APPROX 2022, 21 pages, 1 figure

Parallel Power System Restoration

Authors: Sunil Chopra, Feng Qiu, Sangho Shim

Abstract: Power system restoration is an essential activity for grid resilience, where grid operators restart generators, re-establish transmission paths, and restore loads after a blackout event. With a goal of restoring electric service in the shortest time, the core decisions in restoration planning are to partition the grid into sub-networks, each of which has an initial power source for black-start (ca… ▽ More Power system restoration is an essential activity for grid resilience, where grid operators restart generators, re-establish transmission paths, and restore loads after a blackout event. With a goal of restoring electric service in the shortest time, the core decisions in restoration planning are to partition the grid into sub-networks, each of which has an initial power source for black-start (called sectionalization problem), and then restart all generators in each network (called generator startup sequencing problem or GSS) as soon as possible. Due to the complexity of each problem, the sectionalization and GSS problems are usually solved separately, often resulting in a sub-optimal solution. Our paper develops models and computational methods to solve the two problems simultaneously. We first study the computational complexity of the GSS problem and develop an efficient integer linear programming formulation. We then integrate the GSS problem with the sectionalization problem and develop an integer linear programming formulation for the parallel power system restoration (PPSR) problem to find exact optimal solutions. To solve larger systems, we then develop bounding approaches that find good upper and lower bounds efficiently. Finally, to address computational challenges for very large power grids, we develop a randomized approach to find a high-quality feasible solution quickly. Our computational experiments demonstrate that the proposed approaches are able to find good solutions for PPSR in up to 2000-bus systems. △ Less

Submitted 18 August, 2022; v1 submitted 4 April, 2022; originally announced April 2022.

Comments: 30 pages, working paper

Transformer-based Multimodal Information Fusion for Facial Expression Analysis

Authors: Wei Zhang, Feng Qiu, Suzhen Wang, Hao Zeng, Zhimeng Zhang, Rudong An, Bowen Ma, Yu Ding

Abstract: Human affective behavior analysis has received much attention in human-computer interaction (HCI). In this paper, we introduce our submission to the CVPR 2022 Competition on Affective Behavior Analysis in-the-wild (ABAW). To fully exploit affective knowledge from multiple views, we utilize the multimodal features of spoken words, speech prosody, and facial expression, which are extracted from the… ▽ More Human affective behavior analysis has received much attention in human-computer interaction (HCI). In this paper, we introduce our submission to the CVPR 2022 Competition on Affective Behavior Analysis in-the-wild (ABAW). To fully exploit affective knowledge from multiple views, we utilize the multimodal features of spoken words, speech prosody, and facial expression, which are extracted from the video clips in the Aff-Wild2 dataset. Based on these features, we propose a unified transformer-based multimodal framework for Action Unit detection and also expression recognition. Specifically, the static vision feature is first encoded from the current frame image. At the same time, we clip its adjacent frames by a sliding window and extract three kinds of multimodal features from the sequence of images, audio, and text. Then, we introduce a transformer-based fusion module that integrates the static vision features and the dynamic multimodal features. The cross-attention module in the fusion module makes the output integrated features focus on the crucial parts that facilitate the downstream detection tasks. We also leverage some data balancing techniques, data augmentation techniques, and postprocessing methods to further improve the model performance. In the official test of ABAW3 Competition, our model ranks first in the EXPR and AU tracks. The extensive quantitative evaluations, as well as ablation studies on the Aff-Wild2 dataset, prove the effectiveness of our proposed method. △ Less

Submitted 18 April, 2022; v1 submitted 23 March, 2022; originally announced March 2022.

Learning Diverse Policies in MOBA Games via Macro-Goals

Authors: Yiming Gao, Bei Shi, Xueying Du, Liang Wang, Guangwei Chen, Zhenjie Lian, Fuhao Qiu, Guoan Han, Weixuan Wang, Deheng Ye, Qiang Fu, Wei Yang, Lanxiao Huang

Abstract: Recently, many researchers have made successful progress in building the AI systems for MOBA-game-playing with deep reinforcement learning, such as on Dota 2 and Honor of Kings. Even though these AI systems have achieved or even exceeded human-level performance, they still suffer from the lack of policy diversity. In this paper, we propose a novel Macro-Goals Guided framework, called MGG, to learn… ▽ More Recently, many researchers have made successful progress in building the AI systems for MOBA-game-playing with deep reinforcement learning, such as on Dota 2 and Honor of Kings. Even though these AI systems have achieved or even exceeded human-level performance, they still suffer from the lack of policy diversity. In this paper, we propose a novel Macro-Goals Guided framework, called MGG, to learn diverse policies in MOBA games. MGG abstracts strategies as macro-goals from human demonstrations and trains a Meta-Controller to predict these macro-goals. To enhance policy diversity, MGG samples macro-goals from the Meta-Controller prediction and guides the training process towards these goals. Experimental results on the typical MOBA game Honor of Kings demonstrate that MGG can execute diverse policies in different matches and lineups, and also outperform the state-of-the-art methods over 102 heroes. △ Less

Submitted 27 October, 2021; originally announced October 2021.

Comments: Accepted at NeurIPS 2021

Contingency Analysis Based on Partitioned and Parallel Holomorphic Embedding

Authors: Rui Yao, Feng Qiu, Kai Sun

Abstract: In the steady-state contingency analysis, the traditional Newton-Raphson method suffers from non-convergence issues when solving post-outage power flow problems, which hinders the integrity and accuracy of security assessment. In this paper, we propose a novel robust contingency analysis approach based on holomorphic embedding (HE). The HE-based simulator guarantees convergence if the true power f… ▽ More In the steady-state contingency analysis, the traditional Newton-Raphson method suffers from non-convergence issues when solving post-outage power flow problems, which hinders the integrity and accuracy of security assessment. In this paper, we propose a novel robust contingency analysis approach based on holomorphic embedding (HE). The HE-based simulator guarantees convergence if the true power flow solution exists, which is desirable because it avoids the influence of numerical issues and provides a credible security assessment conclusion. In addition, based on the multi-area characteristics of real-world power systems, a partitioned HE (PHE) method is proposed with an interface-based partitioning of HE formulation. The PHE method does not undermine the numerical robustness of HE and significantly reduces the computation burden in large-scale contingency analysis. The PHE method is further enhanced by parallel or distributed computation to become parallel PHE (P${}^\mathrm{2}$HE). Tests on a 458-bus system, a synthetic 419-bus system and a large-scale 21447-bus system demonstrate the advantages of the proposed methods in robustness and efficiency. △ Less

Submitted 6 April, 2021; originally announced April 2021.

Hybrid QSS and Dynamic Extended-Term Simulation Based on Holomorphic Embedding

Authors: Rui Yao, Feng Qiu

Abstract: Power system simulations that extend over a time period of minutes, hours, or even longer are called extended-term simulations. As power systems evolve into complex systems with increasing interdependencies and richer dynamic behaviors across a wide range of timescales, extended-term simulation is needed for many power system analysis tasks (e.g., resilience analysis, renewable energy integration,… ▽ More Power system simulations that extend over a time period of minutes, hours, or even longer are called extended-term simulations. As power systems evolve into complex systems with increasing interdependencies and richer dynamic behaviors across a wide range of timescales, extended-term simulation is needed for many power system analysis tasks (e.g., resilience analysis, renewable energy integration, cascading failures), and there is an urgent need for efficient and robust extended-term simulation approaches. The conventional approaches are insufficient for dealing with the extended-term simulation of multi-timescale processes. This paper proposes an extended-term simulation approach based on the holomorphic embedding (HE) methodology. Its accuracy and computational efficiency are backed by HE's high accuracy in event-driven simulation, larger and adaptive time steps, and flexible switching between full-dynamic and quasi-steady-state (QSS) models. We used this proposed extended-term simulation approach to evaluate bulk power system restoration plans, and it demonstrates satisfactory accuracy and efficiency in this complex simulation task. △ Less

Submitted 6 April, 2021; originally announced April 2021.

Encoding Frequency Constraints in Preventive Unit Commitment Using Deep Learning with Region-of-Interest Active Sampling

Authors: Yichen Zhang, Hantao Cui, Jianzhe Liu, Feng Qiu, Tianqi Hong, Rui Yao, Fangxing Li

Abstract: With the increasing penetration of renewable energy, frequency response and its security are of significant concerns for reliable power system operations. Frequency-constrained unit commitment (FCUC) is proposed to address this challenge. Despite existing efforts in modeling frequency characteristics in unit commitment (UC), current strategies can only handle oversimplified low-order frequency res… ▽ More With the increasing penetration of renewable energy, frequency response and its security are of significant concerns for reliable power system operations. Frequency-constrained unit commitment (FCUC) is proposed to address this challenge. Despite existing efforts in modeling frequency characteristics in unit commitment (UC), current strategies can only handle oversimplified low-order frequency response models and do not consider wide-range operating conditions. This paper presents a generic data-driven framework for FCUC under high renewable penetration. Deep neural networks (DNNs) are trained to predict the frequency response using real data or high-fidelity simulation data. Next, the DNN is reformulated as a set of mixed-integer linear constraints to be incorporated into the ordinary UC formulation. In the data generation phase, all possible power injections are considered, and a region-of-interests active sampling is proposed to include power injection samples with frequency nadirs closer to the UFLC threshold, which significantly enhances the accuracy of frequency constraints in FCUC. The proposed FCUC is verified on the the IEEE 39-bus system. Then, a full-order dynamic model simulation using PSS/E verifies the effectiveness of FCUC in frequency-secure generator commitments. △ Less

Submitted 12 October, 2021; v1 submitted 18 February, 2021; originally announced February 2021.

Disentangling images with Lie group transformations and sparse coding

Authors: Ho Yin Chau, Frank Qiu, Yubei Chen, Bruno Olshausen

Abstract: Discrete spatial patterns and their continuous transformations are two important regularities contained in natural signals. Lie groups and representation theory are mathematical tools that have been used in previous works to model continuous image transformations. On the other hand, sparse coding is an important tool for learning dictionaries of patterns in natural signals. In this paper, we combi… ▽ More Discrete spatial patterns and their continuous transformations are two important regularities contained in natural signals. Lie groups and representation theory are mathematical tools that have been used in previous works to model continuous image transformations. On the other hand, sparse coding is an important tool for learning dictionaries of patterns in natural signals. In this paper, we combine these ideas in a Bayesian generative model that learns to disentangle spatial patterns and their continuous transformations in a completely unsupervised manner. Images are modeled as a sparse superposition of shape components followed by a transformation that is parameterized by n continuous variables. The shape components and transformations are not predefined, but are instead adapted to learn the symmetries in the data, with the constraint that the transformations form a representation of an n-dimensional torus. Training the model on a dataset consisting of controlled geometric transformations of specific MNIST digits shows that it can recover these transformations along with the digits. Training on the full MNIST dataset shows that it can learn both the basic digit shapes and the natural transformations such as shearing and stretching that are contained in this data. △ Less

Submitted 11 December, 2020; originally announced December 2020.

Hybrid Imitation Learning for Real-Time Service Restoration in Resilient Distribution Systems

Authors: Yichen Zhang, Feng Qiu, Tianqi Hong, Zhaoyu Wang, Fangxing Li

Abstract: Self-healing capability is one of the most critical factors for a resilient distribution system, which requires intelligent agents to automatically perform restorative actions online, including network reconfiguration and reactive power dispatch. These agents should be equipped with a predesigned decision policy to meet real-time requirements and handle highly complex $N-k$ scenarios. The disturba… ▽ More Self-healing capability is one of the most critical factors for a resilient distribution system, which requires intelligent agents to automatically perform restorative actions online, including network reconfiguration and reactive power dispatch. These agents should be equipped with a predesigned decision policy to meet real-time requirements and handle highly complex $N-k$ scenarios. The disturbance randomness hampers the application of exploration-dominant algorithms like traditional reinforcement learning (RL), and the agent training problem under $N-k$ scenarios has not been thoroughly solved. In this paper, we propose the imitation learning (IL) framework to train such policies, where the agent will interact with an expert to learn its optimal policy, and therefore significantly improve the training efficiency compared with the RL methods. To handle tie-line operations and reactive power dispatch simultaneously, we design a hybrid policy network for such a discrete-continuous hybrid action space. We employ the 33-node system under $N-k$ disturbances to verify the proposed framework. △ Less

Submitted 10 May, 2021; v1 submitted 29 November, 2020; originally announced November 2020.

Towards Playing Full MOBA Games with Deep Reinforcement Learning

Authors: Deheng Ye, Guibin Chen, Wen Zhang, Sheng Chen, Bo Yuan, Bo Liu, Jia Chen, Zhao Liu, Fuhao Qiu, Hongsheng Yu, Yinyuting Yin, Bei Shi, Liang Wang, Tengfei Shi, Qiang Fu, Wei Yang, Lanxiao Huang, Wei Liu

Abstract: MOBA games, e.g., Honor of Kings, League of Legends, and Dota 2, pose grand challenges to AI systems such as multi-agent, enormous state-action space, complex action control, etc. Developing AI for playing MOBA games has raised much attention accordingly. However, existing work falls short in handling the raw game complexity caused by the explosion of agent combinations, i.e., lineups, when expand… ▽ More MOBA games, e.g., Honor of Kings, League of Legends, and Dota 2, pose grand challenges to AI systems such as multi-agent, enormous state-action space, complex action control, etc. Developing AI for playing MOBA games has raised much attention accordingly. However, existing work falls short in handling the raw game complexity caused by the explosion of agent combinations, i.e., lineups, when expanding the hero pool in case that OpenAI's Dota AI limits the play to a pool of only 17 heroes. As a result, full MOBA games without restrictions are far from being mastered by any existing AI system. In this paper, we propose a MOBA AI learning paradigm that methodologically enables playing full MOBA games with deep reinforcement learning. Specifically, we develop a combination of novel and existing learning techniques, including curriculum self-play learning, policy distillation, off-policy adaption, multi-head value estimation, and Monte-Carlo tree-search, in training and playing a large pool of heroes, meanwhile addressing the scalability issue skillfully. Tested on Honor of Kings, a popular MOBA game, we show how to build superhuman AI agents that can defeat top esports players. The superiority of our AI is demonstrated by the first large-scale performance test of MOBA AI agent in the literature. △ Less

Submitted 31 December, 2020; v1 submitted 25 November, 2020; originally announced November 2020.

Comments: NeurIPS 2020

Supervised Learning Achieves Human-Level Performance in MOBA Games: A Case Study of Honor of Kings

Authors: Deheng Ye, Guibin Chen, Peilin Zhao, Fuhao Qiu, Bo Yuan, Wen Zhang, Sheng Chen, Mingfei Sun, Xiaoqian Li, Siqin Li, Jing Liang, Zhenjie Lian, Bei Shi, Liang Wang, Tengfei Shi, Qiang Fu, Wei Yang, Lanxiao Huang

Abstract: We present JueWu-SL, the first supervised-learning-based artificial intelligence (AI) program that achieves human-level performance in playing multiplayer online battle arena (MOBA) games. Unlike prior attempts, we integrate the macro-strategy and the micromanagement of MOBA-game-playing into neural networks in a supervised and end-to-end manner. Tested on Honor of Kings, the most popular MOBA at… ▽ More We present JueWu-SL, the first supervised-learning-based artificial intelligence (AI) program that achieves human-level performance in playing multiplayer online battle arena (MOBA) games. Unlike prior attempts, we integrate the macro-strategy and the micromanagement of MOBA-game-playing into neural networks in a supervised and end-to-end manner. Tested on Honor of Kings, the most popular MOBA at present, our AI performs competitively at the level of High King players in standard 5v5 games. △ Less

Submitted 25 November, 2020; originally announced November 2020.

Comments: IEEE Transactions on Neural Networks and Learning Systems (TNNLS)

PowerNet: Multi-agent Deep Reinforcement Learning for Scalable Powergrid Control

Authors: Dong Chen, Kaian Chen. Zhaojian Li, Tianshu Chu, Rui Yao, Feng Qiu, Kaixiang Lin

Abstract: This paper develops an efficient multi-agent deep reinforcement learning algorithm for cooperative controls in powergrids. Specifically, we consider the decentralized inverter-based secondary voltage control problem in distributed generators (DGs), which is first formulated as a cooperative multi-agent reinforcement learning (MARL) problem. We then propose a novel on-policy MARL algorithm, PowerNe… ▽ More This paper develops an efficient multi-agent deep reinforcement learning algorithm for cooperative controls in powergrids. Specifically, we consider the decentralized inverter-based secondary voltage control problem in distributed generators (DGs), which is first formulated as a cooperative multi-agent reinforcement learning (MARL) problem. We then propose a novel on-policy MARL algorithm, PowerNet, in which each agent (DG) learns a control policy based on (sub-)global reward but local states from its neighboring agents. Motivated by the fact that a local control from one agent has limited impact on agents distant from it, we exploit a novel spatial discount factor to reduce the effect from remote agents, to expedite the training process and improve scalability. Furthermore, a differentiable, learning-based communication protocol is employed to foster the collaborations among neighboring agents. In addition, to mitigate the effects of system uncertainty and random noise introduced during on-policy learning, we utilize an action smoothing factor to stabilize the policy execution. To facilitate training and evaluation, we develop PGSim, an efficient, high-fidelity powergrid simulation platform. Experimental results in two microgrid setups show that the developed PowerNet outperforms a conventional model-based control, as well as several state-of-the-art MARL algorithms. The decentralized learning scheme and high sample efficiency also make it viable to large-scale power grids. △ Less

Submitted 31 July, 2021; v1 submitted 24 November, 2020; originally announced November 2020.

Comments: 11 pages

Deep Active Learning for Solvability Prediction in Power Systems

Authors: Yichen Zhang, Jianzhe Liu, Feng Qiu, Tianqi Hong, Rui Yao

Abstract: Traditional methods for solvability region analysis can only have inner approximations with inconclusive conservatism. Machine learning methods have been proposed to approach the real region. In this letter, we propose a deep active learning framework for power system solvability prediction. Compared with the passive learning methods where the training is performed after all instances are labeled,… ▽ More Traditional methods for solvability region analysis can only have inner approximations with inconclusive conservatism. Machine learning methods have been proposed to approach the real region. In this letter, we propose a deep active learning framework for power system solvability prediction. Compared with the passive learning methods where the training is performed after all instances are labeled, the active learning selects most informative instances to be label and therefore significantly reduce the size of labeled dataset for training. In the active learning framework, the acquisition functions, which correspond to different sampling strategies, are defined in terms of the on-the-fly posterior probability from the classifier. The IEEE 39-bus system is employed to validate the proposed framework, where a two-dimensional case is illustrated to visualize the effectiveness of the sampling method followed by the full-dimensional numerical experiments. △ Less

Submitted 22 December, 2020; v1 submitted 26 July, 2020; originally announced July 2020.

Monocular Human Pose and Shape Reconstruction using Part Differentiable Rendering

Authors: Min Wang, Feng Qiu, Wentao Liu, Chen Qian, Xiaowei Zhou, Lizhuang Ma

Abstract: Superior human pose and shape reconstruction from monocular images depends on removing the ambiguities caused by occlusions and shape variance. Recent works succeed in regression-based methods which estimate parametric models directly through a deep neural network supervised by 3D ground truth. However, 3D ground truth is neither in abundance nor can efficiently be obtained. In this paper, we intr… ▽ More Superior human pose and shape reconstruction from monocular images depends on removing the ambiguities caused by occlusions and shape variance. Recent works succeed in regression-based methods which estimate parametric models directly through a deep neural network supervised by 3D ground truth. However, 3D ground truth is neither in abundance nor can efficiently be obtained. In this paper, we introduce body part segmentation as critical supervision. Part segmentation not only indicates the shape of each body part but helps to infer the occlusions among parts as well. To improve the reconstruction with part segmentation, we propose a part-level differentiable renderer that enables part-based models to be supervised by part segmentation in neural networks or optimization loops. We also introduce a general parametric model engaged in the rendering pipeline as an intermediate representation between skeletons and detailed shapes, which consists of primitive geometries for better interpretability. The proposed approach combines parameter regression, body model optimization, and detailed model registration altogether. Experimental results demonstrate that the proposed method achieves balanced evaluation on pose and shape, and outperforms the state-of-the-art approaches on Human3.6M, UP-3D and LSP datasets. △ Less

Submitted 29 January, 2021; v1 submitted 24 March, 2020; originally announced March 2020.

Comments: Accepted by Pacific Graphcis 2020

Journal ref: In Computer Graphics Forum, vol. 39, no. 7, pp. 351-362. 2020

Approximating Trajectory Constraints with Machine Learning -- Microgrid Islanding with Frequency Constraints

Authors: Yichen Zhang, Chen Chen, Guodong Liu, Tianqi Hong, Feng Qiu

Abstract: In this paper, we introduce a deep learning aided constraint encoding method to tackle the frequency-constraint microgrid scheduling problem. The nonlinear function between system operating condition and frequency nadir is approximated by using a neural network, which admits an exact mixed-integer formulation (MIP). This formulation is then integrated with the scheduling problem to encode the freq… ▽ More In this paper, we introduce a deep learning aided constraint encoding method to tackle the frequency-constraint microgrid scheduling problem. The nonlinear function between system operating condition and frequency nadir is approximated by using a neural network, which admits an exact mixed-integer formulation (MIP). This formulation is then integrated with the scheduling problem to encode the frequency constraint. With the stronger representation power of the neural network, the resulting commands can ensure adequate frequency response in a realistic setting in addition to islanding success. The proposed method is validated on a modified 33-node system. Successful islanding with a secure response is simulated under the scheduled commands using a detailed three-phase model in Simulink. The advantages of our model are particularly remarkable when the inertia emulation functions from wind turbine generators are considered. △ Less

Submitted 29 November, 2020; v1 submitted 16 January, 2020; originally announced January 2020.

Ensemble Learning Based Convex Approximation of Three-Phase Power Flow

Authors: Ren Hu, Qifeng Li, Feng Qiu

Abstract: Though the convex optimization has been widely used in power systems, it still cannot guarantee to yield a tight (accurate) solution to some problems. To mitigate this issue, this paper proposes an ensemble learning based convex approximation for AC power flow equations that differs from the existing convex relaxations. The proposed approach is based on quadratic power flow equations in rectangula… ▽ More Though the convex optimization has been widely used in power systems, it still cannot guarantee to yield a tight (accurate) solution to some problems. To mitigate this issue, this paper proposes an ensemble learning based convex approximation for AC power flow equations that differs from the existing convex relaxations. The proposed approach is based on quadratic power flow equations in rectangular coordinates and it can be used in both balanced and unbalanced three-phase power networks. To develop this data-driven convex approximation of power flows, the polynomial regression (PR) is first deployed as a basic learner to fit convex relationships between the independent and dependent variables. Then, ensemble learning algorithms such as gradient boosting (GB) and bagging are introduced to combine learners to boost model performance. Based on the learned convex approximation of power flows, optimal power flow (OPF) is formulated as a convex quadratic programming problem. The simulation results on IEEE standard cases show that, in the context of solving OPF, the proposed data-driven convex approximation outperforms the conventional SDP relaxation in both accuracy and computational efficiency, especially in the cases that the conventional SDP relaxation fails. △ Less

Submitted 15 May, 2020; v1 submitted 12 September, 2019; originally announced September 2019.

Comments: 8 pages, 8 figures, 4 tables

MSC Class: 49-02 ACM Class: I.2.6

Learning to Solve Large-Scale Security-Constrained Unit Commitment Problems

Authors: Alinson S. Xavier, Feng Qiu, Shabbir Ahmed

Abstract: Security-Constrained Unit Commitment (SCUC) is a fundamental problem in power systems and electricity markets. In practical settings, SCUC is repeatedly solved via Mixed-Integer Linear Programming, sometimes multiple times per day, with only minor changes in input data. In this work, we propose a number of machine learning (ML) techniques to effectively extract information from previously solved i… ▽ More Security-Constrained Unit Commitment (SCUC) is a fundamental problem in power systems and electricity markets. In practical settings, SCUC is repeatedly solved via Mixed-Integer Linear Programming, sometimes multiple times per day, with only minor changes in input data. In this work, we propose a number of machine learning (ML) techniques to effectively extract information from previously solved instances in order to significantly improve the computational performance of MIP solvers when solving similar instances in the future. Based on statistical data, we predict redundant constraints in the formulation, good initial feasible solutions and affine subspaces where the optimal solution is likely to lie, leading to significant reduction in problem size. Computational results on a diverse set of realistic and large-scale instances show that, using the proposed techniques, SCUC can be solved on average 4.3x faster with optimality guarantees, and 10.2x faster without optimality guarantees, but with no observed reduction in solution quality. Out-of-distribution experiments provides evidence that the method is somewhat robust against dataset shift. △ Less

Submitted 18 December, 2019; v1 submitted 4 February, 2019; originally announced February 2019.

Collaborative Filtering with Topic and Social Latent Factors Incorporating Implicit Feedback

Authors: Guang-Neng Hu, Xin-Yu Dai, Feng-Yu Qiu, Rui Xia, Tao Li, Shu-Jian Huang, Jia-Jun Chen

Abstract: Recommender systems (RSs) provide an effective way of alleviating the information overload problem by selecting personalized items for different users. Latent factors based collaborative filtering (CF) has become the popular approaches for RSs due to its accuracy and scalability. Recently, online social networks and user-generated content provide diverse sources for recommendation beyond ratings.… ▽ More Recommender systems (RSs) provide an effective way of alleviating the information overload problem by selecting personalized items for different users. Latent factors based collaborative filtering (CF) has become the popular approaches for RSs due to its accuracy and scalability. Recently, online social networks and user-generated content provide diverse sources for recommendation beyond ratings. Although {\em social matrix factorization} (Social MF) and {\em topic matrix factorization} (Topic MF) successfully exploit social relations and item reviews, respectively, both of them ignore some useful information. In this paper, we investigate the effective data fusion by combining the aforementioned approaches. First, we propose a novel model {\em \mbox{MR3}} to jointly model three sources of information (i.e., ratings, item reviews, and social relations) effectively for rating prediction by aligning the latent factors and hidden topics. Second, we incorporate the implicit feedback from ratings into the proposed model to enhance its capability and to demonstrate its flexibility. We achieve more accurate rating prediction on real-life datasets over various state-of-the-art methods. Furthermore, we measure the contribution from each of the three data sources and the impact of implicit feedback from ratings, followed by the sensitivity analysis of hyperparameters. Empirical studies demonstrate the effectiveness and efficacy of our proposed model and its extension. △ Less

Submitted 26 March, 2018; originally announced March 2018.

Comments: 27 pages, 11 figures, 6 tables, ACM TKDD 2018

Scaled VIP Algorithms for Joint Dynamic Forwarding and Caching in Named Data Networks

Authors: Fan Lai, Feng Qiu, Wenjie Bian, Ying Cui, Edmund Yeh

Abstract: Emerging Information-Centric Networking (ICN) architectures seek to optimally utilize both bandwidth and storage for efficient content distribution over the network. The Virtual Interest Packet (VIP) framework has been proposed to enable joint design of forwarding and caching within the Named Data Networking (NDN) architecture. The virtual plane of the VIP framework captures the measured demand fo… ▽ More Emerging Information-Centric Networking (ICN) architectures seek to optimally utilize both bandwidth and storage for efficient content distribution over the network. The Virtual Interest Packet (VIP) framework has been proposed to enable joint design of forwarding and caching within the Named Data Networking (NDN) architecture. The virtual plane of the VIP framework captures the measured demand for content objects, but does not reflect interest collapse and suppression in the NDN network. We aim to further improve the performance of the existing VIP algorithms by using a modified virtual plane where VIP counts are appropriately scaled to reflect interest suppression effects. We characterize the stability region of the modified virtual plane with VIP scaling, develop a new distributed forwarding and caching algorithm operating on the scaled VIPs, and demonstrate the throughput optimality of the scaled VIP algorithm in the virtual plane. Numerical experiments demonstrate significantly enhanced performance relative to the existing VIP algorithm, as well as a number of other baseline algorithms. △ Less

Submitted 15 August, 2016; originally announced August 2016.

Comments: to appear in ICN 2016. arXiv admin note: substantial text overlap with arXiv:1607.03270, arXiv:1310.5569

Technical Report: A Methodology for Studying 802.11p VANET Broadcasting Performance with Practical Vehicle Distribution

Authors: Harry J. F. Qiu, Ivan Wang-Hei Ho, Chi K. Tse, Yu Xie

Abstract: In a Vehicular Ad-hoc Network (VANET), the performance of the communication protocol is influenced heavily by the vehicular density dynamics. However, most of the previous works on VANET performance modeling paid little attention to vehicle distribution, or simply assumed homogeneous car distribution. It is obvious that vehicles are distributed non-homogeneously along a road segment due to traffic… ▽ More In a Vehicular Ad-hoc Network (VANET), the performance of the communication protocol is influenced heavily by the vehicular density dynamics. However, most of the previous works on VANET performance modeling paid little attention to vehicle distribution, or simply assumed homogeneous car distribution. It is obvious that vehicles are distributed non-homogeneously along a road segment due to traffic signals and speed limits at different portions of the road, as well as vehicle interactions that are significant on busy streets. In light of the inadequacy, we present in this paper an original methodology to study the broadcasting performance of 802.11p VANETs with practical vehicle distribution in urban environments. Firstly, we adopt the empirically verified stochastic traffic models, which incorporates the effect of urban settings (such as traffic lights and vehicle interactions) on car distribution and generates practical vehicular density profiles. Corresponding 802.11p protocol and performance models are then developed. When coupled with the traffic models, they can predict broadcasting efficiency, delay, as well as throughput performance of 802.11p VANETs based on the knowledge of car density at each location on the road. Extensive simulation is conducted to verify the accuracy of the developed mathematical models with the consideration of vehicle interaction. In general, our results demonstrate the applicability of the proposed methodology on modeling protocol performance in practical signalized road networks, and shed insights into the design and development of future communication protocols and networking functions for VANETs. △ Less

Submitted 15 October, 2014; originally announced October 2014.