The Collaboratory for Algorithmic Techniques and Artificial Intelligence (CATAI) is an interdisciplinary lab at USCâ€™s Information Sciences Institute led by Dr. Satish Kumar Thittamaranahalli (T. K. Satish Kumar). The lab focuses on the design and implementation of efficient algorithmic techniques for solving combinatorial problems in Artificial Intelligence.
The following is a list of research topics that are of current interest in the lab.
The following is a list of the lab’s peerreviewed publications.

T. K. Satish Kumar, Zhi Wang, Anoop Kumar, Craig Rogers and Craig Knoblock (2018). Load Scheduling of Simple Temporal Networks Under Dynamic Resource Pricing. Proceedings of the ThirtySecond AAAI Conference on Artificial Intelligence (AAAI2018).

Liron Cohen, Tansel Uras, Shiva Jahangiri, Aliyah Arunasalam, Sven Koenig and T. K. Satish Kumar (2018). The FastMap Algorithm for Shortest Path Computations. Proceedings of the Fifteenth International Symposium on Artificial Intelligence and Mathematics (ISAIM2018).

Masaru Nakajima, Hong Xu, Sven Koenig and T. K. Satish Kumar (2018). Towards Understanding the MinSum Message Passing Algorithm for the Minimum Weighted Vertex Cover Problem: An Analytical Approach. Proceedings of the Fifteenth International Symposium on Artificial Intelligence and Mathematics (ISAIM2018).

Ferdinando Fioretto, Hong Xu, Sven Koenig and T. K. Satish Kumar (2018). Constraint Composite GraphBased Lifted Message Passing for Distributed Constraint Optimization Problems. Proceedings of the Fifteenth International Symposium on Artificial Intelligence and Mathematics (ISAIM2018).

T. K. Satish Kumar, Zhi Wang, Anoop Kumar, Craig Rogers and Craig Knoblock (2018). On the Linear Programming Duals of Temporal Reasoning Problems. Proceedings of the Fifteenth International Symposium on Artificial Intelligence and Mathematics (ISAIM2018).

Hong Xu, XinZeng Wu, Cheng Cheng, Sven Koenig and T. K. Satish Kumar (2018). The Buss Reduction for the kWeighted Vertex Cover Problem. Proceedings of the Fifteenth International Symposium on Artificial Intelligence and Mathematics (ISAIM2018).

Hong Xu, Kexuan Sun, Sven Koenig and T. K. Satish Kumar (2018). A Warning PropagationBased LinearTimeandSpace Algorithm for the Minimum Vertex Cover Problem on Giant Graphs. Proceedings of the Fifteenth International Symposium on Artificial Intelligence and Mathematics (ISAIM2018).

Therese Anders, Hong Xu, Cheng Cheng and T. K. Satish Kumar (2017). Measuring Territorial Control in Civil Wars Using Hidden Markov Models: A Data InformaticsBased Approach. Proceedings of the NIPS2017 Workshop on Machine Learning for the Developing World.

Nitin Kamra, T. K. Satish Kumar and Nora Ayanian (2017). Combinatorial Problems in MultiRobot Battery Exchange Systems. IEEE Transactions on Automation Science and Engineering (TASE2017).

T. K. Satish Kumar, Hong Xu, Zheng Tang, Anoop Kumar, Craig Rogers and Craig Knoblock (2017). A Distributed Logical Filter for Connected Row Convex Constraints. Proceedings of the TwentyNinth International Conference on Tools with Artificial Intelligence (ICTAI2017).

Wolfgang Hoenig, T. K. Satish Kumar, Hang Ma, Liron Cohen, Hong Xu, Sven Koenig and Nora Ayanian (2017). Path Finding for MultiRobot Systems with Kinematic Constraints in Occluded Environments. Journal of Artificial Intelligence Research (JAIR2017).

Hang Ma, Jingxing Yang, Liron Cohen, T. K. Satish Kumar and Sven Koenig (2017). Feasibility Study: Moving NonHomogeneous Teams in Congested Video Game Environments. Proceedings of the Thirteenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE2017).

Hong Xu, Sven Koenig and T. K. Satish Kumar (2017). A Constraint Composite GraphBased ILP Encoding of the Boolean Weighted CSP. Proceedings of the TwentyThird International Conference on Principles and Practice of Constraint Programming (CP2017).

Hang Ma, Wolfgang Hoenig, Liron Cohen, Tansel Uras, Hong Xu, T. K. Satish Kumar, Nora Ayanian and Sven Koenig (2017). Overview: A Hierarchical Framework for Plan Generation and Execution in MultiRobot Systems. IEEE Intelligent Systems, 2017.

Hong Xu, T. K. Satish Kumar and Sven Koenig (2017). MinMax Message Passing and Local Consistency in Constraint Networks. Proceedings of the Thirtieth Australasian Joint Conference on Artificial Intelligence (AI2017).

Hong Xu, T. K. Satish Kumar and Sven Koenig (2017). A LinearTime and LinearSpace Algorithm for the Minimum Vertex Cover Problem on Giant Graphs. Proceedings of the Tenth Annual Symposium on Combinatorial Search (SOCS2017).

Sven Koenig and T. K. Satish Kumar (2017). A Case for Collaborative Construction as Testbed for Cooperative MultiAgent Planning. Proceedings of the ICAPS2017 Scheduling and Planning Applications Workshop (SPARK2017).

Wolfgang Hoenig, T. K. Satish Kumar, Liron Cohen, Hang Ma, Hong Xu, Nora Ayanian and Sven Koenig (2017). Summary: MultiAgent Path Finding with Kinematic Constraints. Proceedings of the IJCAI2017 Sister Conference Best Paper Track.

Hang Ma, Jiaoyang Li, T. K. Satish Kumar and Sven Koenig (2017). Lifelong MultiAgent Path Finding for Online Pickup and Delivery Tasks. Proceedings of the Sixteenth International Conference on Autonomous Agents and MultiAgent Systems (AAMAS2017).

Hong Xu, T. K. Satish Kumar and Sven Koenig (2017). The NemhauserTrotter Reduction and Lifted Message Passing for the Weighted CSP. Proceedings of the Fourteenth International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR2017).

Hang Ma, T. K. Satish Kumar and Sven Koenig (2017). MultiAgent Path Finding with Delay Probabilities. Proceedings of the ThirtyFirst AAAI Conference on Artificial Intelligence (AAAI2017).

Hong Xu, T. K. Satish Kumar, Dylan Johnke, Nora Ayanian and Sven Koenig (2016). SAGL: A New Heuristic for MultiRobot Routing with Complex Tasks. Proceedings of the TwentyEighth International Conference on Tools with Artificial Intelligence (ICTAI2016).

Wolfgang Hoenig, T. K. Satish Kumar, Hang Ma, Sven Koenig and Nora Ayanian (2016). Formation Change for Robot Groups in Occluded Environments. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS2016).

Hang Ma, Sven Koenig, Nora Ayanian, Liron Cohen, Wolfgang Hoenig, T. K. Satish Kumar, Tansel Uras, Hong Xu, Craig Tovey and Guni Sharon (2016). Overview: Generalizations of MultiAgent Path Finding to RealWorld Scenarios. Proceedings of the IJCAI2016 Workshop on MultiAgent Path Finding.

Tathagata Chakraborti, Sarath Sreedharan, Sailik Sengupta, T. K. Satish Kumar and Subbarao Kambhampati (2016). Compliant Conditions for Polynomial Time Approximation of Operator Counts. Proceedings of the Ninth International Symposium on Combinatorial Search (SOCS2016).

Liron Cohen, Tansel Uras, T. K. Satish Kumar, Hong Xu, Nora Ayanian and Sven Koenig (2016). Improved Solvers for BoundedSuboptimal MultiAgent Path Finding. Proceedings of the TwentyFifth International Joint Conference on Artificial Intelligence (IJCAI2016). Also: Proceedings of the Ninth International Symposium on Combinatorial Search (SOCS2016).

Wolfgang Hoenig, T. K. Satish Kumar, Liron Cohen, Hang Ma, Sven Koenig and Nora Ayanian (2016). Path Planning with Kinematic Constraints for Robot Groups. Proceedings of the 2016 Southern California Robotics Symposium (SCR2016).

[Best Robotics Paper Award] Wolfgang Hoenig, T. K. Satish Kumar, Liron Cohen, Hang Ma, Hong Xu, Nora Ayanian and Sven Koenig (2016). MultiAgent Path Finding with Kinematic Constraints. Proceedings of the TwentySixth International Conference on Automated Planning and Scheduling (ICAPS2016). Also: Proceedings of the IJCAI2016 Workshop on MultiAgent Path Finding.

Trevor Cai, David Zhang, T. K. Satish Kumar, Sven Koenig and Nora Ayanian (2016). Local Search on Trees and a Framework for Automated Construction Using Multiple Identical Robots. Proceedings of the Fifteenth International Conference on Autonomous Agents and MultiAgent Systems (AAMAS2016).

Hong Xu, T. K. Satish Kumar and Sven Koenig (2016). A New Solver for the Minimum Weighted Vertex Cover Problem. Proceedings of the Thirteenth International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR2016).

T. K. Satish Kumar (2016). Kernelization, Generation of Bounds, and the Scope of Incremental Computation for Weighted Constraint Satisfaction Problems. Proceedings of the Fourteenth International Symposium on Artificial Intelligence and Mathematics (ISAIM2016).

Robert Morris, Corina Pasareanu, Kasper Luckow, Waqar Malik, Hang Ma, T. K. Satish Kumar and Sven Koenig (2016). Planning, Scheduling and Monitoring for Airport Surface Operations. Proceedings of the AAAI2016 Workshop on Planning for Hybrid Systems (PlanHS2016).

Hang Ma, Craig Tovey, Guni Sharon, T. K. Satish Kumar and Sven Koenig (2016). MultiAgent Path Finding with Payload Transfers and the PackageExchange RobotRouting Problem. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI2016). Also: Proceedings of the Eighth International Symposium on Combinatorial Search (SOCS2016). Also: Proceedings of the IJCAI2016 Workshop on MultiAgent Path Finding.

T. K. Satish Kumar, Duc Thien Nguyen, William Yeoh and Sven Koenig (2014). A Simple PolynomialTime Randomized Distributed Algorithm for Connected Row Convex Constraints. Proceedings of the TwentyEighth AAAI Conference on Artificial Intelligence (AAAI2014). Also: Proceedings of the AAMAS2014 International Joint Workshop on Optimization in MultiAgent Systems and Distributed Constraint Reasoning (OPTMASDCR2014).

T. K. Satish Kumar, Sangmook Jung and Sven Koenig (2014). A TreeBased Algorithm for Construction Robots. Proceedings of the TwentyFourth International Conference on Automated Planning and Scheduling (ICAPS2014). Also: Proceedings of the AAAI2014 Workshop on Artificial Intelligence and Robotics (AIRob2014).

T. K. Satish Kumar, Marcello Cirillo and Sven Koenig (2013). Simple Temporal Problems with Taboo Regions. Proceedings of the TwentySeventh AAAI Conference on Artificial Intelligence (AAAI2013).

T. K. Satish Kumar, Marcello Cirillo and Sven Koenig (2013). On the Traveling Salesman Problem with Simple Temporal Constraints. Proceedings of the Tenth International Symposium on Abstraction, Reformulation and Approximation (SARA2013). Also: Proceedings of the Planning and Robotics Workshop at ICAPS2013.

T. K. Satish Kumar, Liron Cohen and Sven Koenig (2013). Submodular Constraints and Planar Constraint Networks: New Results. Proceedings of the Tenth International Symposium on Abstraction, Reformulation and Approximation (SARA2013).

T. K. Satish Kumar, Liron Cohen and Sven Koenig (2013). Incorrect Lower Bounds for PathConsistency and More. Proceedings of the Tenth International Symposium on Abstraction, Reformulation and Approximation (SARA2013).

T. K. Satish Kumar (2008). A Framework for Hybrid Tractability Results in Boolean Weighted Constraint Satisfaction Problems. Proceedings of the Fourteenth International Conference on Principles and Practice of Constraint Programming (CP2008).

Blaine Nelson and T. K. Satish Kumar (2008). CircuitTSAT: A Solver for Large Instances of the Disjunctive Temporal Problem. Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling (ICAPS2008).

T. K. Satish Kumar (2008). Lifting Techniques for Weighted Constraint Satisfaction Problems. Proceedings of the Tenth International Symposium on Artificial Intelligence and Mathematics (ISAIM2008).

T. K. Satish Kumar (2007). Fast (Incremental) Algorithms for Useful Classes of Simple Temporal Problems with Preferences. Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI2007).

T. K. Satish Kumar (2006). Simple Randomized Algorithms for Tractable Row and Tree Convex Constraints. Proceedings of the TwentyFirst AAAI National Conference on Artificial Intelligence (AAAI2006).

T. K. Satish Kumar (2006). Tractable Classes of Metric Temporal Problems with Domain Rules. Proceedings of the TwentyFirst AAAI National Conference on Artificial Intelligence (AAAI2006).

T. K. Satish Kumar and Stuart Russell (2006). On Some Tractable Cases of Logical Filtering. Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling (ICAPS2006).

T. K. Satish Kumar (2005). Contributions to Algorithmic Techniques in Automated Reasoning about Physical Systems. Ph.D. Thesis, Computer Science Department, Stanford University, March 2005.

T. K. Satish Kumar (2005). On the Tractability of Smooth Constraint Satisfaction Problems. Proceedings of the Second International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR2005).

[Best Student Paper Award] T. K. Satish Kumar (2005). On the Tractability of Restricted Disjunctive Temporal Problems. Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling (ICAPS2005).

T. K. Satish Kumar (2004). Differential AntiChain Algorithms for the Generalized ResourceEnvelope Problem. Proceedings of the ECAI2004 Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems. Also: Planning and Scheduling: Frontiers in Artificial Intelligence and Applications. Vol. 117, IOS Press, L. Castillo, D. Borrajo, M. A. Salido & A. Oddi Editors.

T. K. Satish Kumar (2004). On Geometric CSPs with (Near)Linear Domains and MaxDistance Constraints. Proceedings of the ECAI2004 Workshop on Modeling and Solving Problems with Constraints.

T. K. Satish Kumar (2004). A PolynomialTime Algorithm for Simple Temporal Problems with Piecewise Constant Domain Preference Functions. Proceedings of the Nineteenth AAAI National Conference on Artificial Intelligence (AAAI2004).

T. K. Satish Kumar (2004). On Disjunctive Representations of Distributions and Randomization. Proceedings of the TwentyFourth SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence (AI2004).

T. K. Satish Kumar (2003). Incremental Computation of ResourceEnvelopes in ProducerConsumer Models. Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP2003).

T. K. Satish Kumar (2002). SATBased Algorithms for Bayesian Network Inference. Proceedings of the TwentySecond SGAI International Conference on Knowledge Based Systems and Applied Artificial Intelligence (ES2002).

T. K. Satish Kumar (2002). An InformationTheoretic Characterization of Abstraction in Diagnosis and Hypothesis Selection. Proceedings of the Fifth International Symposium on Abstraction, Reformulation and Approximation (SARA2002).

T. K. Satish Kumar and Richard Dearden (2002). The Oracular Constraints Method. Proceedings of the Fifth International Symposium on Abstraction, Reformulation and Approximation (SARA2002).

T. K. Satish Kumar (2002). HCBFS: Combining StructureBased and TMSBased Approaches in ModelBased Diagnosis. Proceedings of the Thirteenth International Workshop on Principles of Diagnosis (DX2002).

T. K. Satish Kumar (2002). A Model Counting Characterization of Diagnoses. Proceedings of the Thirteenth International Workshop on Principles of Diagnosis (DX2002).

T. K. Satish Kumar (2001). QCBFS: Leveraging Qualitative Knowledge in SimulationBased Diagnosis. Proceedings of the Fifteenth International Workshop on Qualitative Reasoning (QR2001).

T. K. Satish Kumar (2001). FairCoverage Monte Carlo Generation of Monotonic Functions within Envelopes. Proceedings of the Fifteenth International Workshop on Qualitative Reasoning (QR2001).

T. K. Satish Kumar (2000). A Compositional Approach to Causality. Proceedings of the Fourth International Symposium on Abstraction, Reformulation and Approximation (SARA2000).

T. K. Satish Kumar (2000). Reinterpretation of Causal Order Graphs Towards Effective Explanation Generation Using Compositional Modeling. Proceedings of the Fourteenth International Workshop on Qualitative Reasoning (QR2000).