3 Search Results for "Kumar, T. K. Satish"

Document
DOI: 10.4230/LIPIcs.CP.2023.40
FastMapSVM for Predicting CSP Satisfiability

Authors: Kexin Zheng, Ang Li, Han Zhang, and T. K. Satish Kumar

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
Recognizing the satisfiability of Constraint Satisfaction Problems (CSPs) is NP-hard. Although several Machine Learning (ML) approaches have attempted this task by casting it as a binary classification problem, they have had only limited success for a variety of challenging reasons. First, the NP-hardness of the task does not make it amenable to straightforward approaches. Second, CSPs come in various forms and sizes while many ML algorithms impose the same form and size on their training and test instances. Third, the representation of a CSP instance is not unique since the variables and their domain values are unordered. In this paper, we propose FastMapSVM, a recently developed ML framework that leverages a distance function between pairs of objects. We define a novel distance function between two CSP instances using maxflow computations. This distance function is well defined for CSPs of different sizes. It is also invariant to the ordering on the variables and their domain values. Therefore, our framework has broader applicability compared to other approaches. We discuss various representational and combinatorial advantages of FastMapSVM. Through experiments, we also show that it outperforms other state-of-the-art ML approaches.
Cite as

Kexin Zheng, Ang Li, Han Zhang, and T. K. Satish Kumar. FastMapSVM for Predicting CSP Satisfiability. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{zheng_et_al:LIPIcs.CP.2023.40,
  author =	{Zheng, Kexin and Li, Ang and Zhang, Han and Kumar, T. K. Satish},
  title =	{{FastMapSVM for Predicting CSP Satisfiability}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{40:1--40:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.40},
  URN =		{urn:nbn:de:0030-drops-190775},
  doi =		{10.4230/LIPIcs.CP.2023.40},
  annote =	{Keywords: Constraint Satisfaction Problems, Machine Learning, FastMapSVM}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.5
Trajectory Optimization for Safe Navigation in Maritime Traffic Using Historical Data

Authors: Chaithanya Basrur, Arambam James Singh, Arunesh Sinha, Akshat Kumar, and T. K. Satish Kumar

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
Increasing maritime trade often results in congestion in busy ports, thereby necessitating planning methods to avoid close quarter risky situations among vessels. Rapid digitization and automation of port operations and vessel navigation provide unique opportunities for significantly improving navigation safety. Our key contributions are as follows. First, given a set of future candidate trajectories for vessels in a traffic hotspot zone, we develop a multiagent trajectory optimization method to choose trajectories that result in the best overall close quarter risk reduction. Our novel MILP-based optimization method is more than an order-of-magnitude faster than a standard MILP for this problem, and runs in near real-time. Second, although automation has improved in maritime operations, current vessel traffic systems (in our case study of a busy Asian port) predict only a single future trajectory of a vessel based on linear extrapolation. Therefore, using historical data we learn a generative model that predicts multiple possible future trajectories of each vessel in a given traffic hotspot, reflecting past vessel movement patterns, and integrate it with our trajectory optimizer. Third, we validate our trajectory optimization and generative model extensively using a real world maritime traffic dataset containing 6 million Automated Identification System (AIS) data records detailing vessel movements over 1.5 years from one of the world’s busiest ports, demonstrating effective risk reduction.
Cite as

Chaithanya Basrur, Arambam James Singh, Arunesh Sinha, Akshat Kumar, and T. K. Satish Kumar. Trajectory Optimization for Safe Navigation in Maritime Traffic Using Historical Data. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{basrur_et_al:LIPIcs.CP.2022.5,
  author =	{Basrur, Chaithanya and Singh, Arambam James and Sinha, Arunesh and Kumar, Akshat and Kumar, T. K. Satish},
  title =	{{Trajectory Optimization for Safe Navigation in Maritime Traffic Using Historical Data}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.5},
  URN =		{urn:nbn:de:0030-drops-166341},
  doi =		{10.4230/LIPIcs.CP.2022.5},
  annote =	{Keywords: Multi-Agent Path Coordination, Maritime Traffic Control}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.53
Differential Programming via OR Methods

Authors: Shannon Sweitzer and T. K. Satish Kumar

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
Systems of ordinary differential equations (ODEs) and partial differential equations (PDEs) are extensively used in many fields of science, including physics, biochemistry, nonlinear control, and dynamical systems. On the one hand, analytical methods for solving systems of ODEs/PDEs mostly remain an art and are largely insufficient for complex systems. On the other hand, numerical approximation methods do not yield a viable analytical form of the solution that is often required for downstream tasks. In this paper, we present an approximate approach for solving systems of ODEs/PDEs analytically using solvers like Gurobi developed in Operations Research (OR). Our main idea is to represent entire functions as Bézier curves/surfaces with to-be-determined control points. The ODEs/PDEs as well as their boundary conditions can then be reformulated as constraints on these control points. In many cases, this reformulation yields quadratic programming problems (QPPs) that can be solved in polynomial time. It also allows us to reason about inequalities. We demonstrate the success of our approach on several interesting classes of ODEs/PDEs.
Cite as

Shannon Sweitzer and T. K. Satish Kumar. Differential Programming via OR Methods. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sweitzer_et_al:LIPIcs.CP.2021.53,
  author =	{Sweitzer, Shannon and Kumar, T. K. Satish},
  title =	{{Differential Programming via OR Methods}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{53:1--53:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.53},
  URN =		{urn:nbn:de:0030-drops-153445},
  doi =		{10.4230/LIPIcs.CP.2021.53},
  annote =	{Keywords: Differential Programming, Operations Research, B\'{e}zier Curves}
}
  • Refine by Author
  • 3 Kumar, T. K. Satish
  • 1 Basrur, Chaithanya
  • 1 Kumar, Akshat
  • 1 Li, Ang
  • 1 Singh, Arambam James
  • Show More...

  • Refine by Classification
  • 1 Applied computing
  • 1 Computing methodologies → Machine learning
  • 1 Computing methodologies → Multi-agent planning

  • Refine by Keyword
  • 1 Bézier Curves
  • 1 Constraint Satisfaction Problems
  • 1 Differential Programming
  • 1 FastMapSVM
  • 1 Machine Learning
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2021
  • 1 2022
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact