Hong's Research Homepage

This website presents a list of my publications and advised students.

Google Scholar
dblp
ORCID 0000-0001-7874-4518

Advised Students

Han Zhang (Fall 2018 -- Spring 2019): Master's student in Computer Science at the University of Southern California.
Kexuan Sun (Summer 2017 -- Spring 2018): Master's student in Computer Science at the University of Southern California, achieved USC Viterbi School of Engineering Department of Computer Science best research award in April 2018, joined the University of Southern California as a PhD student in Fall 2018.
Cheng Cheng (Summer 2017 -- Fall 2017): Undergraduate student in Computer Science/Economics at the University of Southern California, achieved USC Viterbi School of Engineering computer science award for outstanding research in May 2018, joined Carnegie Mellon University as a PhD student in Fall 2018.
Zhi Wang (Summer 2017): Undergraduate student in Computer Science at the University of Southern California, joined the University of California, San Diego as a PhD student in Fall 2018.
Dylan Johnke (Summer 2015): Undergraduate student in Mathematics at Cornell University, Viterbi Summer Undergraduate Research Experience (SURE) Program.
Masaru Nakajima (Summer 2017 -- Spring 2018): Junior doctoral student in Physics at the University of Southern California.
Ka Wa Yip (Spring 2018): Junior doctoral student in Physics at the University of Southern California.

Publications

Stars (*) next to names in the author lists indicate equal contribution.

2020

Frederick Reiss, Hong Xu*, Bryan Cutler*, Karthik Muthuraman*, and Zachary Eichenberger*. Identifying incorrect labels in the CoNLL-2003 corpus. In Proceedings of the 24th Conference on Computational Natural Language Learning (CoNLL), 215–226. 2020. doi:10.18653/v1/2020.conll-1.16.
[abstract▼] [details] [full text] [BibTeX▼]

The CoNLL-2003 corpus for English-language named entity recognition (NER) is one of the most influential corpora for NER model research. A large number of publications, including many landmark works, have used this corpus as a source of ground truth for NER tasks. In this paper, we examine this corpus and identify over 1300 incorrect labels (out of 35089 in the corpus). In particular, the number of incorrect labels in the test fold is comparable to the number of errors that state-of-the-art models make when running inference over this corpus. We describe the process by which we identified these incorrect labels, using novel variants of techniques from semi-supervised learning. We also summarize the types of errors that we found, and we revisit several recent results in NER in light of the corrected data. Finally, we show experimentally that our corrections to the corpus have a positive impact on three state-of-the-art models.
```
@inproceedings{reiss2020,
    author = "Reiss, Frederick and Xu*, Hong and Cutler*, Bryan and Muthuraman*, Karthik and Eichenberger*, Zachary",
    title = "Identifying Incorrect Labels in the {CoNLL}-2003 Corpus",
    booktitle = "Proceedings of the 24th Conference on Computational Natural Language Learning (CoNLL)",
    year = "2020",
    pages = "215--226",
    doi = "10.18653/v1/2020.conll-1.16"
}
```
Hong Xu, Kexuan Sun, Sven Koenig, and T. K. Satish Kumar. Decision tree learning-inspired dynamic variable ordering for the weighted CSP. In Proceedings of the 13th International Symposium on Combinatorial Search (SoCS), 91–99. 2020. Best paper honourable mention award. URL: https://aaai.org/ocs/index.php/SOCS/SOCS20/paper/viewFile/18522/17561.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

The weighted constraint satisfaction problem (WCSP) is a powerful mathematical framework for combinatorial optimization. The branch-and-bound search paradigm is very successful in solving the WCSP but critically depends on the ordering in which variables are instantiated. In this paper, we introduce a new framework for dynamic variable ordering for solving the WCSP. This framework is inspired by regression decision tree learning. Variables are ordered dynamically based on samples of random assignments of values to variables as well as their corresponding total weights. Within this framework, we propose four variable ordering heuristics (sdr, inv-sdr, rr and inv-rr). We compare them with many state-of-the-art dynamic variable ordering heuristics, and show that sdr and rr outperform them on many real-world and random benchmark instances.
```
@inproceedings{xu2020,
    author = "Xu, Hong and Sun, Kexuan and Koenig, Sven and Kumar, T. K. Satish",
    title = "Decision Tree Learning-Inspired Dynamic Variable Ordering for the Weighted {CSP}",
    year = "2020",
    booktitle = "Proceedings of the 13th International Symposium on Combinatorial Search (SoCS)",
    pages = "91--99",
    url = "https://aaai.org/ocs/index.php/SOCS/SOCS20/paper/viewFile/18522/17561",
    note = "Best paper honourable mention award",
    customlinkslides = "http://files.hong.me/papers/xu2020-slides.pdf"
}
```
Kexuan Sun, Shudan Zhong, and Hong Xu. Learning embeddings of directed networks with text-associated nodes—with application in software package dependency networks. In Proceedings of the 2020 BigGraphs Workshop at IEEE BigData. 2020.
[abstract▼] [details] [full text] [data] [code] [BibTeX▼]

A network embedding consists of a vector representation for each node in the network. Its usefulness has been shown in many real-world application domains, such as social networks and web networks. Directed networks with text associated with each node, such as software package dependency networks, are commonplace. However, to the best of our knowledge, their embeddings have hitherto not been specifically studied. In this paper, we propose PCTADW-1 and PCTADW-2, two algorithms based on neural networks that learn embeddings of directed networks with text associated with each node. We create two new node-labeled such networks: The package dependency networks in two popular GNU/Linux distributions, Debian and Fedora. We experimentally demonstrate that the embeddings produced by our algorithms resulted in node classification with better quality than those of various baselines on these two networks. We observe that there exist systematic presence of analogies (similar to those in word embeddings) in the network embeddings of software package dependency networks. To the best of our knowledge, this is the first time that such systematic presence of analogies is observed in network and document embeddings. We further demonstrate that these network embeddings can be novelly used for better understanding software attributes, such as the development process and user interface of software, etc.
```
@inproceedings{sun2020,
    author = "Sun, Kexuan and Zhong, Shudan and Xu, Hong",
    title = "Learning Embeddings of Directed Networks with Text-Associated Nodes---with Application in Software Package Dependency Networks",
    booktitle = "Proceedings of the 2020 BigGraphs Workshop at IEEE BigData",
    year = "2020",
    customlinkdata = "https://doi.org/10.5281/zenodo.1410669",
    customlinkcode = "https://github.com/shudan/PCTADW"
}
```

2019

Shudan Zhong and Hong Xu. Intelligently recommending key bindings on physical keyboards with demonstrations in Emacs. In Proceedings of the 24th International Conference on Intelligent User Interfaces (IUI), 12–17. 2019. doi:10.1145/3301275.3302272.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

Physical keyboards have been peripheral input devices to electronic computers since early 1970s and become ubiquitous during the past few decades, especially in professional areas such as software programming, professional game playing, and document processing. In these real-world applications, key bindings, a fundamental vehicle for human to interact with software systems using physical keyboards, play a critical role in users' productivity. However, as essential applications of artificial intelligence research, research on intelligent user interfaces and recommender systems barely relates to key bindings on physical keyboards. In this paper, we develop a recommender system (referred to as EKBRS) for intelligently recommending key bindings with demonstration in Emacs, which we use as a base user interface. This is a brand new direction of intelligent user interface research and also a novel application of recommender systems. To the best of our knowledge, this is the world's first intelligent user interface that heavily exploits key bindings of physical keyboards and the world's first recommender system for recommending key bindings. We empirically show the effectiveness of our recommender system and briefly discuss the applicability of this recommender system to other software systems.
```
@inproceedings{zhong2019a,
    author = "Zhong, Shudan and Xu, Hong",
    title = "Intelligently Recommending Key Bindings on Physical Keyboards with Demonstrations in {Emacs}",
    year = "2019",
    booktitle = "Proceedings of the 24th International Conference on Intelligent User Interfaces (IUI)",
    pages = "12--17",
    doi = "10.1145/3301275.3302272",
    customlinkslides = "http://files.hong.me/papers/zhong2019a-slides.pdf"
}
```
Ka Wa Yip, Hong Xu, Sven Koenig, and T. K. Satish Kumar. Quadratic reformulation of nonlinear pseudo-Boolean functions via the constraint composite graph. In Proceedings of the 16th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR). 2019. doi:10.1007/978-3-030-19212-9_43.
[abstract▼] [details] [full text] [BibTeX▼]

Nonlinear pseudo-Boolean optimization (nonlinear PBO) is the minimization problem on nonlinear pseudo-Boolean functions (non linear PBFs). One promising approach to nonlinear PBO is to first use a quadratization algorithm to reduce the PBF to a quadratic PBF by introducing intelligently chosen auxiliary variables and then solve it using a quadratic PBO solver. In this paper, we develop a new quadratization algorithm based on the idea of the constraint composite graph (CCG). We demonstrate its theoretical advantages over state-of-the-art quadratization algorithms. We experimentally demonstrate that our CCG-based quadratization algorithm outperforms the state-of-the-art algorithm in terms of both effectiveness and efficiency on randomly generated instances and a novel reformulation of facility location problems.
```
@inproceedings{yip2019,
    author = "Yip, Ka Wa and Xu, Hong and Koenig, Sven and Kumar, T. K. Satish",
    title = "Quadratic Reformulation of Nonlinear Pseudo-{B}oolean Functions via the Constraint Composite Graph",
    year = "2019",
    booktitle = "Proceedings of the 16th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR)",
    doi = "10.1007/978-3-030-19212-9\_43"
}
```
Alex Bozarth, Brendan Dwyer, Fei Hu, Daniel Jalova, Karthik Muthuraman, Nick Pentreath, Simon Plovyt, Gabriela de Queiroz, Saishruthi Swaminathan, Patrick Titzler, Xin Wu, Hong Xu, Frederick R Reiss, and Vijay Bommireddipalli. Model Asset eXchange: Path to ubiquitous deep learning deployment. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management (CIKM). 2019. Best demo paper award. doi:10.1145/3357384.3357860.
[abstract▼] [details] [full text] [BibTeX▼]

A recent trend observed in traditionally challenging fields such as computer vision and natural language processing has been the significant performance gains shown by deep learning (DL). In many different research fields, DL models have been evolving rapidly and become ubiquitous. Despite researchers' excitement, unfortunately, most software developers are not DL experts and oftentimes have a difficult time following the booming DL research outputs. As a result, it usually takes a significant amount of time for the latest superior DL models to prevail in industry. This issue is further exacerbated by the common use of sundry incompatible DL programming frameworks, such as Tensorflow, PyTorch, Theano, etc. To address this issue, we propose a system, called Model Asset Exchange (MAX), that avails developers of easy access to state-of-the-art DL models. Regardless of the underlying DL programming frameworks, it provides an open source Python library (called the MAX framework) that wraps DL models and unifies programming interfaces with our standardized RESTful APIs. These RESTful APIs enable developers to exploit the wrapped DL models for inference tasks without the need to fully understand different DL programming frameworks. Using MAX, we have wrapped and open-sourced more than 30 state-of-the-art DL models from various research fields, including computer vision, natural language processing and signal processing, etc. In the end, we selectively demonstrate two web applications that are built on top of MAX, as well as the process of adding a DL model to MAX.
```
@inproceedings{bozarth2019,
    author = "Bozarth, Alex and Dwyer, Brendan and Hu, Fei and Jalova, Daniel and Muthuraman, Karthik and Pentreath, Nick and Plovyt, Simon and de Queiroz, Gabriela and Swaminathan, Saishruthi and Titzler, Patrick and Wu, Xin and Xu, Hong and Reiss, Frederick R and Bommireddipalli, Vijay",
    title = "{Model Asset eXchange}: {P}ath to Ubiquitous Deep Learning Deployment",
    year = "2019",
    booktitle = "Proceedings of the 28th ACM International Conference on Information and Knowledge Management (CIKM)",
    doi = "10.1145/3357384.3357860",
    note = "Best demo paper award"
}
```

2018

Hong Xu, Sven Koenig, and T. K. Satish Kumar. Towards effective deep learning for constraint satisfaction problems. In Proceedings of the 24th International Conference on Principles and Practice of Constraint Programming (CP), 588–597. 2018. doi:10.1007/978-3-319-98334-9_38.
[abstract▼] [details] [full text] [slides] [poster] [BibTeX▼]

Many attempts have been made to apply machine learning techniques to constraint satisfaction problems (CSPs). However, none of them have made use of the recent advances in deep learning. In this paper, we apply deep learning to predict the satisfiabilities of CSPs. To the best of our knowledge, this is the first effective application of deep learning to CSPs that yields \(>99.99\%\) prediction accuracy on random Boolean binary CSPs whose constraint tightnesses or constraint densities do not determine their satisfiabilities. We use a deep convolutional neural network on a matrix representation of CSPs. Since it is NP-hard to solve CSPs, labeled data required for training are in general costly to produce and are thus scarce. We address this issue using the asymptotic behavior of generalized Model A, a new random CSP generation model, along with domain adaptation and data augmentation techniques for CSPs. We demonstrate the effectiveness of our deep learning techniques using experiments on random Boolean binary CSPs. While these CSPs are known to be in P, we use them for a proof of concept.
```
@inproceedings{xu2018c,
    author = "Xu, Hong and Koenig, Sven and Kumar, T. K. Satish",
    title = "Towards Effective Deep Learning for Constraint Satisfaction Problems",
    year = "2018",
    doi = "10.1007/978-3-319-98334-9\_38",
    pages = "588--597",
    booktitle = "Proceedings of the 24th International Conference on Principles and Practice of Constraint Programming (CP)",
    customlinkslides = "http://files.hong.me/papers/xu2018c-slides.pdf",
    customlinkposter = "http://files.hong.me/papers/xu2018c-poster.pdf"
}
```
Hong Xu, Kexuan Sun, Sven Koenig, and T. K. Satish Kumar. A warning propagation-based linear-time-and-space algorithm for the minimum vertex cover problem on giant graphs. In Proceedings of the 15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), 567–584. 2018. doi:10.1007/978-3-319-93031-2_41.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

A vertex cover (VC) of a graph \(G\) is a subset of vertices in \(G\) such that at least one endpoint vertex of each edge in \(G\) is in this subset. The minimum VC (MVC) problem is to identify a VC of minimum size (cardinality) and is known to be NP-hard. Although many local search algorithms have been developed to solve the MVC problem close-to-optimally, their applicability on giant graphs (with no less than 100,000 vertices) is limited. For such graphs, there are two reasons why it would be beneficial to have linear-time-and-space algorithms that produce small VCs. Such algorithms can: (a) serve as preprocessing steps to produce good starting states for local search algorithms and (b) also be useful for many applications that require finding small VCs quickly. In this paper, we develop a new linear-time-and-space algorithm, called MVC-WP, for solving the MVC problem on giant graphs based on the idea of warning propagation, which has so far only been used as a theoretical tool for studying properties of MVCs on infinite random graphs. We empirically show that it outperforms other known linear-time-and-space algorithms in terms of sizes of produced VCs.
```
@inproceedings{xu2018b,
    author = "Xu, Hong and Sun, Kexuan and Koenig, Sven and Kumar, T. K. Satish",
    title = "A Warning Propagation-Based Linear-Time-and-Space Algorithm for the Minimum Vertex Cover Problem on Giant Graphs",
    year = "2018",
    booktitle = "Proceedings of the 15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR)",
    customlinkslides = "http://files.hong.me/papers/xu2018b-slides.pdf",
    doi = "10.1007/978-3-319-93031-2\_41",
    pages = "567--584"
}
```
Hong Xu, Cheng Cheng, Sven Koenig, and T. K. Satish Kumar. Message passing algorithms for semiring-based and valued constraint satisfaction problems. In Proceedings of the 11th International Symposium on Combinatorial Search (SoCS), 115–123. 2018. URL: https://aaai.org/ocs/index.php/SOCS/SOCS18/paper/viewFile/17969/17107.pdf.
[abstract▼] [details] [full text] [BibTeX▼]

Local consistency algorithms, like arc consistency (AC) algorithms, are polynomial-time algorithms that prune the search space of constraint satisfaction problems (CSPs). In this paper, we present connections between message passing algorithms and AC for semiring-based CSPs (SCSPs) and valued CSPs (VCSPs), two well-established frameworks that generalize CSPs. Message passing algorithms are well known distributed search algorithms for solving many combinatorial problems in artificial intelligence, probabilistic reasoning, and information theory. However, the relationship between message passing algorithms and SCSPs or VCSPs still remains understudied. Towards this end, we propose the best-\(\odot\) message passing (BOMP) algorithm for SCSPs and VCSPs. We prove that, unlike other standard message passing algorithms which are in general not guaranteed to converge, the BOMP algorithm guarantees convergence for SCSPs and specific subclasses of VCSPs. We also theoretically study the relationship between the BOMP algorithm and AC on SCSPs, and empirically study the quality of the solutions produced by the BOMP algorithm for VCSPs.
```
@inproceedings{xu2018d,
    author = "Xu, Hong and Cheng, Cheng and Koenig, Sven and Kumar, T. K. Satish",
    title = "Message Passing Algorithms for Semiring-Based and Valued Constraint Satisfaction Problems",
    year = "2018",
    booktitle = "Proceedings of the 11th International Symposium on Combinatorial Search (SoCS)",
    pages = "115--123",
    url = "https://aaai.org/ocs/index.php/SOCS/SOCS18/paper/viewFile/17969/17107.pdf"
}
```
Masaru Nakajima*, Hong Xu*, Sven Koenig, and T. K. Satish Kumar. Towards understanding the min-sum message passing algorithm for the minimum weighted vertex cover problem: An analytical approach. In Proceedings of the 15th International Symposium on Artificial Intelligence and Mathematics (ISAIM). 2018. URL: http://isaim2018.cs.virginia.edu/papers/ISAIM2018_Nakajima_etal.pdf.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

Given a vertex-weighted undirected graph \(G=\langle V,E,w\rangle\), the minimum weighted vertex cover (MWVC) problem is to find a subset of vertices with minimum total weight such that every edge in the graph has at least one of its endpoints in it. The MWVC problem and its amenability to the min-sum message passing (MSMP) algorithm remain understudied despite the common occurrence of the MWVC problem and the common use of the MSMP algorithm in many areas of AI. In this paper, we first develop the MSMP algorithm for the MWVC problem that can be viewed as a generalization of the warning propagation algorithm. We then study properties of the MSMP algorithm for the MWVC problem on a special class of graphs, namely single loops. We compare our analytical results with experimental observations and argue that: (a) Our analytical framework is powerful in accurately predicting the behavior of the MSMP algorithm on the MWVC problem, and (b) for a given combinatorial optimization problem, it may be more effective to apply the MSMP algorithm on the MWVC problem that is equivalent to the given problem, instead of applying the MSMP algorithm on the given problem directly.
```
@inproceedings{nakajima2018,
    author = "Nakajima*, Masaru and Xu*, Hong and Koenig, Sven and Kumar, T. K. Satish",
    title = "Towards Understanding the Min-Sum Message Passing Algorithm for the Minimum Weighted Vertex Cover Problem: {An} Analytical Approach",
    booktitle = "Proceedings of the 15th International Symposium on Artificial Intelligence and Mathematics (ISAIM)",
    year = "2018",
    url = "http://isaim2018.cs.virginia.edu/papers/ISAIM2018\_Nakajima\_etal.pdf",
    customlinkslides = "http://files.hong.me/papers/nakajima2018-slides.pdf"
}
```
Ferdinando Fioretto, Hong Xu, Sven Koenig, and T. K. Satish Kumar. Solving multiagent constraint optimization problems on the constraint composite graph. In Proceedings of the 21st International Conference on Principles and Practice of Multi-Agent Systems (PRIMA), 106–122. 2018. doi:10.1007/978-3-030-03098-8_7.
[abstract▼] [details] [full text] [BibTeX▼]

We introduce the Constraint Composite Graph (CCG) for Distributed Constraint Optimization Problems (DCOPs), a popular paradigm used for the description and resolution of cooperative multi-agent problems. The CCG is a novel graphical representation of DCOPs on which agents can coordinate their assignments to solve the distributed problem suboptimally. By leveraging this representation, agents are able to reduce the size of the problem. We propose a novel variant of Max-Sum---a popular DCOP incomplete algorithm---called CCG-Max-Sum, which is applied to CCGs, and demonstrate its efficiency and effectiveness on DCOP benchmarks based on several network topologies.
```
@inproceedings{fioretto2018a,
    author = "Fioretto, Ferdinando and Xu, Hong and Koenig, Sven and Kumar, T. K. Satish",
    title = "Solving Multiagent Constraint Optimization Problems on the Constraint Composite Graph",
    year = "2018",
    pages = "106--122",
    doi = "10.1007/978-3-030-03098-8\_7",
    booktitle = "Proceedings of the 21st International Conference on Principles and Practice of Multi-Agent Systems (PRIMA)"
}
```
Ferdinando Fioretto, Hong Xu, Sven Koenig, and T. K. Satish Kumar. Constraint composite graph-based lifted message passing for distributed constraint optimization problems. In Proceedings of the 15th International Symposium on Artificial Intelligence and Mathematics (ISAIM). 2018. URL: http://isaim2018.cs.virginia.edu/papers/ISAIM2018_Fioretto_etal.pdf.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

The Distributed Constraint Optimization Problem (DCOP) offers a powerful approach for the description and resolution of cooperative multi-agent problems. In this model, a group of agents coordinates their actions to optimize a global objective function, taking into account their local preferences. In the majority of DCOP algorithms, agents operate on three main graphical representations of the problem: (a) the constraint graph, (b) the pseudo-tree, or (c) the factor graph. In this paper, we introduce the Constraint Composite Graph (CCG) for DCOPs, an alternative graphical representation on which agents can coordinate their assignments to solve the distributed problem suboptimally. By leveraging this representation, agents are able to reduce the size of the problem. We propose a novel variant of Max-Sum---a popular DCOP incomplete algorithm---called CCG-Max-Sum, which is applied to CCGs. We also demonstrate the efficiency and effectiveness of CCG-Max-Sum on DCOP benchmarks based on several network topologies.
```
@inproceedings{fioretto2018,
    author = "Fioretto, Ferdinando and Xu, Hong and Koenig, Sven and Kumar, T. K. Satish",
    title = "Constraint Composite Graph-Based Lifted Message Passing for Distributed Constraint Optimization Problems",
    year = "2018",
    booktitle = "Proceedings of the 15th International Symposium on Artificial Intelligence and Mathematics (ISAIM)",
    url = "http://isaim2018.cs.virginia.edu/papers/ISAIM2018\_Fioretto\_etal.pdf",
    customlinkslides = "http://files.hong.me/papers/fioretto2018-slides.pdf"
}
```
Hong Xu, Xin-Zeng Wu, Cheng Cheng, Sven Koenig, and T. K. Satish Kumar. The Buss reduction for the \(k\)-weighted vertex cover problem. In Proceedings of the 15th International Symposium on Artificial Intelligence and Mathematics (ISAIM). 2018. URL: http://isaim2018.cs.virginia.edu/papers/ISAIM2018_Xu_etal.pdf.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

The \(k\)-vertex cover (\(k\)-VC) problem is to find a VC of cardinality no more than \(k\) on a given undirected graph, and the \(k\)-weighted VC (\(k\)-WVC) problem is to find a VC of a weight no more than \(k\) on a given vertex-weighted undirected graph. In this paper, we generalize the Buss reduction, an important kernelization technique for the \(k\)-VC problem, to the \(k\)-WVC problem. We study its properties for the \(k\)-VC problem and the \(k\)-WVC problem on surrogates of large real-world graphs that are generated using the Erd\Hos-R\'enyi model and the Barab\'asi-Albert model. We also argue that our study of the Buss reduction bears important implications on the kernelization of combinatorial problems that have been shown to be reducible to WVC problems.
```
@inproceedings{xu2018,
    author = "Xu, Hong and Wu, Xin-Zeng and Cheng, Cheng and Koenig, Sven and Kumar, T. K. Satish",
    title = "The {Buss} Reduction for the \(k\)-Weighted Vertex Cover Problem",
    year = "2018",
    booktitle = "Proceedings of the 15th International Symposium on Artificial Intelligence and Mathematics (ISAIM)",
    url = "http://isaim2018.cs.virginia.edu/papers/ISAIM2018\_Xu\_etal.pdf",
    customlinkslides = "http://files.hong.me/papers/xu2018-slides.pdf"
}
```
T. K. Satish Kumar, Hong Xu, Zheng Tang, Anoop Kumar, Craig Milo Rogers, and Craig A. Knoblock. Alert generation in execution monitoring using resource envelopes. In Proceedings of the 31st International Florida Artificial Intelligence Research Society Conference (FLAIRS), 38–43. 2018. URL: https://aaai.org/ocs/index.php/FLAIRS/FLAIRS18/paper/view/17615/16853.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

A simple temporal network (STN) can often be used to represent the flexibility in the execution of a plan. Nodes represent the execution times of actions and directed edges represent constraints between them. An STN with resources (STNR) is an STN in which each node is associated with production or consumption levels of resources. The upper (lower) resource envelope of an STNR is the maximum (minimum) accumulated resource levels at every time instant over all possible executions. In this paper, we discuss the usefulness of resource envelopes in the context of execution monitoring. We show that they can be used in a tractable framework for forward projection of world states during plan execution. This allows an execution monitor to recognize depletion of resources early and to generate alerts with large look-aheads. It also supports retasking by enabling “what-if reasoning” during plan execution.
```
@inproceedings{kumar2018,
    author = "Kumar, T. K. Satish and Xu, Hong and Tang, Zheng and Kumar, Anoop and Rogers, Craig Milo and Knoblock, Craig A.",
    title = "Alert Generation in Execution Monitoring Using Resource Envelopes",
    booktitle = "Proceedings of the 31st International Florida Artificial Intelligence Research Society Conference (FLAIRS)",
    year = "2018",
    url = "https://aaai.org/ocs/index.php/FLAIRS/FLAIRS18/paper/view/17615/16853",
    customlinkslides = "http://files.hong.me/papers/kumar2018-slides.pdf",
    pages = "38--43"
}
```

2017

Hong Xu, T. K. Satish Kumar, and Sven Koenig. The Nemhauser-Trotter reduction and lifted message passing for the weighted CSP. In Proceedings of the 14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR), 387–402. 2017. doi:10.1007/978-3-319-59776-8_31.
[abstract▼] [details] [full text] [code] [slides] [BibTeX▼]

We study two important implications of the constraint composite graph (CCG) associated with the weighted constraint satisfaction problem (WCSP). First, we show that the Nemhauser-Trotter (NT) reduction popularly used for kernelization of the minimum weighted vertex cover (MWVC) problem can also be applied to the CCG of the WCSP. This leads to a polynomial-time preprocessing algorithm that fixes the optimal values of a large subset of the variables in the WCSP. Second, belief propagation (BP) is a well-known technique used for solving many combinatorial problems in probabilistic reasoning, artificial intelligence and information theory. The min-sum message passing (MSMP) algorithm is a simple variant of BP that has also been successfully employed in several research communities. Unfortunately, the MSMP algorithm has met with little success on the WCSP. We revive the MSMP algorithm for solving the WCSP by applying it on the CCG of a given WCSP instance instead of its original form. We refer to this new MSMP algorithm as the lifted MSMP algorithm for the WCSP. We demonstrate the effectiveness of our algorithms through experimental evaluations.
```
@inproceedings{xu2017,
    author = "Xu, Hong and Kumar, T. K. Satish and Koenig, Sven",
    title = "The {Nemhauser-Trotter} Reduction and Lifted Message Passing for the Weighted {CSP}",
    booktitle = "Proceedings of the 14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming ({CPAIOR})",
    year = "2017",
    pages = "387--402",
    doi = "10.1007/978-3-319-59776-8\_31",
    customlinkcode = "https://gitlab.com/xuphys/wcsp-solver",
    customlinkslides = "http://files.hong.me/papers/xu2017-slides.pdf"
}
```
Hong Xu, Sven Koenig, and T. K. Satish Kumar. A constraint composite graph-based ILP encoding of the Boolean weighted CSP. In Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming (CP), 630–638. 2017. doi:10.1007/978-3-319-66158-2_40.
[abstract▼] [details] [full text] [slides] [code] [BibTeX▼]

The weighted constraint satisfaction problem (WCSP) occurs in the crux of many real-world applications of operations research, artificial intelligence, bioinformatics, etc. Despite its importance as a combinatorial substrate, many attempts for building an efficient WCSP solver have been largely unsatisfactory. In this paper, we introduce a new method for encoding a (Boolean) WCSP instance as an integer linear program (ILP). This encoding is based on the idea of the constraint composite graph (CCG) associated with a WCSP instance. We show that our CCG-based ILP encoding of the Boolean WCSP is significantly more efficient than previously known ILP encodings. Theoretically, we show that the CCG-based ILP encoding has a number of interesting properties. Empirically, we show that it allows us to solve many hard Boolean WCSP instances that cannot be solved by ILP solvers with previously known ILP encodings.
```
@inproceedings{xu2017c,
    author = "Xu, Hong and Koenig, Sven and Kumar, T. K. Satish",
    title = "A Constraint Composite Graph-Based {ILP} Encoding of the {Boolean} Weighted {CSP}",
    booktitle = "Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming (CP)",
    year = "2017",
    doi = "10.1007/978-3-319-66158-2\_40",
    pages = "630--638",
    customlinkslides = "http://files.hong.me/papers/xu2017c-slides.pdf",
    customlinkcode = "https://gitlab.com/xuphys/wcsp-solver"
}
```
T. K. Satish Kumar, Hong Xu, Zheng Tang, Anoop Kumar, Craig Milo Rogers, and Craig A. Knoblock. A distributed logical filter for connected row convex constraints. In Proceedings of the 29th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 96–101. 2017. doi:10.1109/ICTAI.2017.00026.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

Filtering denotes any method whereby an agent updates its belief state---its knowledge of the state of the world---from a sequence of actions and observations. Popular filtering techniques like Kalman and particle filters maintain compact representations of the belief state at all times. However, these techniques cannot be applied to situations where the world is described using constraints instead of stochastic models. In such cases, the belief state is a logical formula describing all possible world states. In this paper, we first review a logical filtering algorithm for connected row convex (CRC) constraints. CRC constraints are representationally very powerful; and the filtering algorithm for CRC constraints is a logical equivalent of the Kalman filter. We later study the CRC filtering algorithm in distributed settings where nodes of a network are interested in different subsets of variables from a larger system. We deduce its reducibility to the problem of distributed path consistency (PC) and prove the compactness of the belief state representations maintained at each node at all times.
```
@inproceedings{kumar2017,
    author = "Kumar, T. K. Satish and Xu, Hong and Tang, Zheng and Kumar, Anoop and Rogers, Craig Milo and Knoblock, Craig A.",
    title = "A Distributed Logical Filter for Connected Row Convex Constraints",
    booktitle = "Proceedings of the 29th IEEE International Conference on Tools with Artificial Intelligence (ICTAI)",
    year = "2017",
    doi = "10.1109/ICTAI.2017.00026",
    pages = "96--101",
    customlinkslides = "http://files.hong.me/papers/kumar2017-slides.pdf"
}
```
Therese Anders, Hong Xu, Cheng Cheng, and T. K. Satish Kumar. Measuring territorial control in civil wars using hidden Markov models: A data informatics-based approach. In Proceedings of the NIPS 2017 Workshop on Machine Learning for the Developing World. 2017. arXiv:1711.06786.
[abstract▼] [details] [full text] [poster] [BibTeX▼]

Territorial control is a key aspect shaping the dynamics of civil war. Despite its importance, we lack data on territorial control that are fine-grained enough to account for subnational spatio-temporal variation and that cover a large set of conflicts. To resolve this issue, we propose a theoretical model of the relationship between territorial control and tactical choice in civil war and outline how Hidden Markov Models (HMMs) are suitable to capture theoretical intuitions and estimate levels of territorial control. We discuss challenges of using HMMs in this application and mitigation strategies for future work.
```
@inproceedings{anders2017,
    author = "Anders, Therese and Xu, Hong and Cheng, Cheng and Kumar, T. K. Satish",
    title = "Measuring Territorial Control in Civil Wars Using Hidden {Markov} Models: {A} Data Informatics-Based Approach",
    booktitle = "Proceedings of the NIPS 2017 Workshop on Machine Learning for the Developing World",
    year = "2017",
    eprint = "1711.06786",
    eprinttype = "arxiv",
    eprintclass = "stat.AP",
    customlinkposter = "http://files.hong.me/papers/anders2017-poster.pdf"
}
```
Hong Xu, T. K. Satish Kumar, and Sven Koenig. Min-max message passing and local consistency in constraint networks. In Proceedings of the 30th Australasian Joint Conference on Artificial Intelligence (AI), 340–352. 2017. doi:10.1007/978-3-319-63004-5_27.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

In this paper, we uncover some relationships between local consistency in constraint networks and message passing akin to belief propagation in probabilistic reasoning. We develop a new message passing algorithm, called the min-max message passing (MMMP) algorithm, for unifying the different notions of local consistency in constraint networks. In particular, we study its connection to arc consistency (AC) and path consistency. We show that AC-3 can be expressed more intuitively in the framework of message passing. We also show that the MMMP algorithm can be modified to enforce path consistency.
```
@inproceedings{xu2017b,
    author = "Xu, Hong and Kumar, T. K. Satish and Koenig, Sven",
    title = "Min-Max Message Passing and Local Consistency in Constraint Networks",
    booktitle = "Proceedings of the 30th Australasian Joint Conference on Artificial Intelligence (AI)",
    year = "2017",
    doi = "10.1007/978-3-319-63004-5\_27",
    pages = "340--352",
    customlinkslides = "http://files.hong.me/papers/xu2017b-slides.pdf"
}
```
Hang Ma, Wolfgang Hönig, Liron Cohen, Tansel Uras, Hong Xu, T. K. Satish Kumar, Nora Ayanian, and Sven Koenig. Overview: a hierarchical framework for plan generation and execution in multi-robot systems. IEEE Intelligent Systems, 32(6):6–12, 2017. doi:10.1109/MIS.2017.4531217.
[abstract▼] [details] [full text] [BibTeX▼]

The authors present an overview of a hierarchical framework for coordinating task- and motion-level operations in multirobot systems. Their framework is based on the idea of using simple temporal networks to simultaneously reason about precedence/causal constraints required for task-level coordination and simple temporal constraints required to take some kinematic constraints of robots into account. In the plan-generation phase, the framework provides a computationally scalable method for generating plans that achieve high-level tasks for groups of robots and take some of their kinematic constraints into account. In the plan-execution phase, the framework provides a method for absorbing an imperfect plan execution to avoid time-consuming re-planning in many cases. The authors use the multirobot path-planning problem as a case study to present the key ideas behind their framework for the long-term autonomy of multirobot systems.
```
@article{ma2017,
    author = "Ma, Hang and Hönig, Wolfgang and Cohen, Liron and Uras, Tansel and Xu, Hong and Kumar, T. K. Satish and Ayanian, Nora and Koenig, Sven",
    title = "Overview: A Hierarchical Framework for Plan Generation and Execution in Multi-Robot Systems",
    journal = "IEEE Intelligent Systems",
    year = "2017",
    volume = "32",
    number = "6",
    pages = "6--12",
    doi = "10.1109/MIS.2017.4531217"
}
```
Wolfgang Hönig, T. K. Satish Kumar, Liron Cohen, Hang Ma, Hong Xu, Nora Ayanian, and Sven Koenig. Summary: Multi-agent path finding with kinematic constraints. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 4869–4873. 2017. Sister conference best paper track. doi:10.24963/ijcai.2017/684.
[abstract▼] [details] [full text] [BibTeX▼]

Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and agents with assigned start and goal locations, MAPF solvers from AI find collision-free paths for hundreds of agents with user-provided sub-optimality guarantees. However, they ignore that actual robots are subject to kinematic constraints (such as velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST to postprocess the output of a MAPF solver in polynomial time to create a plan-execution schedule that can be executed on robots. This schedule works on non-holonomic robots, considers kinematic constraints, provides a guaranteed safety distance between robots, and exploits slack to avoid time-intensive replanning in many cases. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.
```
@inproceedings{honig2017,
    author = "Hönig, Wolfgang and Kumar, T. K. Satish and Cohen, Liron and Ma, Hang and Xu, Hong and Ayanian, Nora and Koenig, Sven",
    title = "Summary: {M}ulti-Agent Path Finding with Kinematic Constraints",
    booktitle = "Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI)",
    year = "2017",
    doi = "10.24963/ijcai.2017/684",
    pages = "4869--4873",
    note = "Sister conference best paper track"
}
```
Hong Xu, T. K. Satish Kumar, and Sven Koenig. A linear-time and linear-space algorithm for the minimum vertex cover problem on giant graphs. In Proceedings of the 10th International Symposium on Combinatorial Search (SoCS), 173–174. 2017. extended abstract. URL: https://aaai.org/ocs/index.php/SOCS/SOCS17/paper/viewFile/15789/15080.
[abstract▼] [details] [full text] [poster] [BibTeX▼]

In this paper, we develop the message passing based linear-time and linear-space MVC algorithm (MVC-MPL) for solving the minimum vertex cover (MVC) problem. MVC-MPL is based on heuristics derived from a theoretical analysis of message passing algorithms in the context of belief propagation. We show that MVC-MPL produces smaller vertex covers than other linear-time and linear-space algorithms.
```
@inproceedings{xu2017a,
    author = "Xu, Hong and Kumar, T. K. Satish and Koenig, Sven",
    title = "A Linear-Time and Linear-Space Algorithm for the Minimum Vertex Cover Problem on Giant Graphs",
    booktitle = "Proceedings of the 10th International Symposium on Combinatorial Search (SoCS)",
    year = "2017",
    url = "https://aaai.org/ocs/index.php/SOCS/SOCS17/paper/viewFile/15789/15080",
    pages = "173--174",
    customlinkposter = "http://files.hong.me/papers/xu2017a-poster.pdf",
    note = "extended abstract"
}
```

2016

Hong Xu, T. K. Satish Kumar, and Sven Koenig. A new solver for the minimum weighted vertex cover problem. In Proceedings of the 13th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR), 392–405. 2016. doi:10.1007/978-3-319-33954-2_28.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

Given a vertex-weighted graph \(G = \langle V, E \rangle\), the minimum weighted vertex cover (MWVC) problem is to choose a subset of vertices with minimum total weight such that every edge in the graph has at least one of its endpoints chosen. While there are good solvers for the unweighted version of this NP-hard problem, the weighted version---i.e., the MWVC problem---remains understudied despite its common occurrence in many areas of AI---like combinatorial auctions, weighted constraint satisfaction, and probabilistic reasoning. In this paper, we present a new solver for the MWVC problem based on a novel reformulation to a series of SAT instances using a primal-dual approximation algorithm as a starting point. We show that our SAT-based MWVC solver (SBMS) significantly outperforms other methods.
```
@inproceedings{xu2016,
    author = "Xu, Hong and Kumar, T. K. Satish and Koenig, Sven",
    title = "A New Solver for the Minimum Weighted Vertex Cover Problem",
    booktitle = "Proceedings of the 13th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming ({CPAIOR})",
    year = "2016",
    pages = "392--405",
    doi = "10.1007/978-3-319-33954-2\_28",
    customlinkslides = "http://files.hong.me/papers/xu2016-slides.pdf"
}
```
Hong Xu, T. K. Satish Kumar, Dylan Johnke, Nora Ayanian, and Sven Koenig. SAGL: a new heuristic for multi-robot routing with complex tasks. In Proceedings of the 28th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 530–535. 2016. doi:10.1109/ICTAI.2016.0087.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

In this paper, we study the Complex Routing Problem (CRP), where several homogeneous robots need to visit given task locations to accomplish complex tasks in a cooperative setting. Each task location hosts a task. The complexity level of a task is defined as the number of robots that need to be simultaneously present at its location to accomplish it. The robots need to be routed so that all tasks get accomplished with minimal makespan. We present a new centralized algorithm, called SAGL, for solving the CRP heuristically. SAGL is inspired by the application of linear programming duality to the Steiner Forest Problem. It makes less restrictive assumptions than the state-of-the-art distributed Approach with Reaction Functions and scales better in both the complexity levels of tasks and the number of complex tasks (whose complexity levels are greater than one), although it results in somewhat larger makespans.
```
@inproceedings{xu2016a,
    author = "Xu, Hong and Kumar, T. K. Satish and Johnke, Dylan and Ayanian, Nora and Koenig, Sven",
    title = "{SAGL}: A New Heuristic for Multi-Robot Routing with Complex Tasks",
    booktitle = "Proceedings of the 28th IEEE International Conference on Tools with Artificial Intelligence ({ICTAI})",
    year = "2016",
    pages = "530--535",
    doi = "10.1109/ICTAI.2016.0087",
    customlinkslides = "http://files.hong.me/papers/xu2016a-slides.pdf"
}
```
Liron Cohen, Tansel Uras, T. K. Satish Kumar, Hong Xu, Nora Ayanian, and Sven Koenig. Improved solvers for bounded-suboptimal multi-agent path finding. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), 3067–3074. 2016. URL: http://www.ijcai.org/Abstract/16/435.
[abstract▼] [details] [full text] [slides] [BibTeX▼]

Multi-Agent Path Finding (MAPF) with the objective to minimize the sum of the travel times of the agents along their paths is a hard combinatorial problem. Recent work has shown that bounded-suboptimal MAPF solvers, such as Enhanced Conflict-Based Search or ECBS(\(w_1\)) for short, run often faster than optimal MAPF solvers at the cost of incurring a suboptimality factor \(w_1\), that is due to using focal search. Other recent work has used experience graphs to guide the search of ECBS(\(w_1\)) and speed it up, at the cost of incurring a separate suboptimality factor \(w_2\), that is due to inflating the heuristic values. Thus, the combination has suboptimality factor \(w_1 w_2\). In this first feasibility study, we develop a bounded-suboptimal MAPF solver, Improved-ECBS or iECBS(\(w_1\)) for short, that has suboptimality factor \(w_1\) rather than \(w_1 w_2\) (because it uses experience graphs to guide its search without inflating the heuristic values) and can run faster than ECBS(\(w_1\)). We also develop two first approaches for automatically generating experience graphs for a given MAPF instance. Finally, we observe heavy-tailed behavior in the runtimes of these MAPF solvers and develop a simple rapid randomized restart strategy that can increase the success rate of iECBS(\(w_1\)) within a given runtime limit.
```
@inproceedings{cohen2016,
    author = "Cohen, Liron and Uras, Tansel and Kumar, T. K. Satish and Xu, Hong and Ayanian, Nora and Koenig, Sven",
    title = "Improved Solvers for Bounded-Suboptimal Multi-Agent Path Finding",
    booktitle = "Proceedings of the 25th International Joint Conference on Artificial Intelligence ({IJCAI})",
    year = "2016",
    pages = "3067--3074",
    url = "http://www.ijcai.org/Abstract/16/435",
    customlinkslides = "https://dl.dropboxusercontent.com/u/6251260/IJCAI16.pdf"
}
```
Wolfgang Hönig, T. K. Satish Kumar, Liron Cohen, Hang Ma, Hong Xu, Nora Ayanian, and Sven Koenig. Multi-agent path finding with kinematic contraints. In Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS), 477–485. 2016. Outstanding paper award in the robotics track. URL: https://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13183/12711.
[abstract▼] [details] [full text] [video] [BibTeX▼]

Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and agents with assigned start and goal locations, MAPF solvers from AI find collision-free paths for hundreds of agents with user-provided sub-optimality guarantees. However, they ignore that actual robots are subject to kinematic constraints (such as finite maximum velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST, a novel approach that makes use of a simple temporal network to postprocess the output of a MAPF solver in polynomial time to create a plan-execution schedule that can be executed on robots. This schedule works on non-holonomic robots, takes their maximum translational and rotational velocities into account, provides a guaranteed safety distance between them, and exploits slack to absorb imperfect plan executions and avoid time-intensive replanning in many cases. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.
```
@inproceedings{honig2016,
    author = "Hönig, Wolfgang and Kumar, T. K. Satish and Cohen, Liron and Ma, Hang and Xu, Hong and Ayanian, Nora and Koenig, Sven",
    title = "Multi-Agent Path Finding with Kinematic Contraints",
    booktitle = "Proceedings of the 26th International Conference on Automated Planning and Scheduling ({ICAPS})",
    year = "2016",
    pages = "477--485",
    note = "Outstanding paper award in the robotics track",
    url = "https://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13183/12711",
    customlinkvideo = "https://youtu.be/mV3BqnelqDU"
}
```
Hang Ma, Sven Koenig, Nora Ayanian, Liron Cohen, Wolfgang Hoenig, T.K. Satish Kumar, Tansel Uras, Hong Xu, Craig Tovey, and Guni Sharon. Overview: generalizations of multi-agent path finding to real-world scenarios. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI) Workshop on Multi-Agent Path Finding. 2016. URL: https://www.andrew.cmu.edu/user/gswagner/workshop/IJCAI_2016_WOMPF_paper_6.pdf.
[abstract▼] [details] [full text] [BibTeX▼]

Multi-agent path finding (MAPF) is well-studied in artificial intelligence, robotics, theoretical computer science and operations research. We discuss issues that arise when generalizing MAPF methods to real-world scenarios and four research directions that address them. We emphasize the importance of addressing these issues as opposed to developing faster methods for the standard formulation of the MAPF problem.
```
@inproceedings{ma2016,
    author = "Ma, Hang and Koenig, Sven and Ayanian, Nora and Cohen, Liron and Hoenig, Wolfgang and Kumar, T.K. Satish and Uras, Tansel and Xu, Hong and Tovey, Craig and Sharon, Guni",
    title = "Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios",
    year = "2016",
    url = "https://www.andrew.cmu.edu/user/gswagner/workshop/IJCAI\_2016\_WOMPF\_paper\_6.pdf",
    booktitle = "Proceedings of the 25th International Joint Conference on Artificial Intelligence ({IJCAI}) Workshop on Multi-Agent Path Finding"
}
```