The Collaboratory for Algorithmic Techniques and Artificial Intelligence (CATAI) is a virtual 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.

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, Nora Ayanian, Liron Cohen, Sven Koenig, T. K. Satish Kumar, Tansel Uras and Hong Xu (2017). Overview: A Hierarchical Framework for Plan Generation and Execution Monitoring in MultiRobot Systems. IEEE Intelligent Systems.

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).