6 Search Results for "Chiang, Yi-Jen"

Document
Short Paper
DOI: 10.4230/LIPIcs.COSIT.2024.21
An Ontology and Geospatial Knowledge Graph for Reasoning About Cascading Failures (Short Paper)

Authors: Torsten Hahmann and David K. Kedrowski

Published in: LIPIcs, Volume 315, 16th International Conference on Spatial Information Theory (COSIT 2024)

Abstract
During a natural disaster such as flooding, the failure of a single asset in the complex and interconnected web of critical urban infrastructure can trigger a cascade of failures within and across multiple systems with potentially life-threatening consequences. To help emergency management effectively and efficiently assess such failures, we design the Utility Connection Ontology Design Pattern to represent utility services and model connections within and across those services. The pattern is encoded as an OWL ontology and instantiated with utility data in a geospatial knowledge graph. We demonstrate how it facilitates reasoning to identify cascading service failures due to flooding for producing maps and other summaries for situational awareness.
Cite as

Torsten Hahmann and David K. Kedrowski. An Ontology and Geospatial Knowledge Graph for Reasoning About Cascading Failures (Short Paper). In 16th International Conference on Spatial Information Theory (COSIT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 315, pp. 21:1-21:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hahmann_et_al:LIPIcs.COSIT.2024.21,
  author =	{Hahmann, Torsten and Kedrowski, David K.},
  title =	{{An Ontology and Geospatial Knowledge Graph for Reasoning About Cascading Failures}},
  booktitle =	{16th International Conference on Spatial Information Theory (COSIT 2024)},
  pages =	{21:1--21:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-330-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{315},
  editor =	{Adams, Benjamin and Griffin, Amy L. and Scheider, Simon and McKenzie, Grant},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2024.21},
  URN =		{urn:nbn:de:0030-drops-208364},
  doi =		{10.4230/LIPIcs.COSIT.2024.21},
  annote =	{Keywords: knowledge graph, ontology, OWL, spatial reasoning, cascading failures, urban infrastructure}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.COSIT.2024.28
Evaluating the Ability of Large Language Models to Reason About Cardinal Directions (Short Paper)

Authors: Anthony G Cohn and Robert E Blackwell

Published in: LIPIcs, Volume 315, 16th International Conference on Spatial Information Theory (COSIT 2024)

Abstract
We investigate the abilities of a representative set of Large language Models (LLMs) to reason about cardinal directions (CDs). To do so, we create two datasets: the first, co-created with ChatGPT, focuses largely on recall of world knowledge about CDs; the second is generated from a set of templates, comprehensively testing an LLM’s ability to determine the correct CD given a particular scenario. The templates allow for a number of degrees of variation such as means of locomotion of the agent involved, and whether set in the first , second or third person. Even with a temperature setting of zero, Our experiments show that although LLMs are able to perform well in the simpler dataset, in the second more complex dataset no LLM is able to reliably determine the correct CD, even with a temperature setting of zero.
Cite as

Anthony G Cohn and Robert E Blackwell. Evaluating the Ability of Large Language Models to Reason About Cardinal Directions (Short Paper). In 16th International Conference on Spatial Information Theory (COSIT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 315, pp. 28:1-28:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cohn_et_al:LIPIcs.COSIT.2024.28,
  author =	{Cohn, Anthony G and Blackwell, Robert E},
  title =	{{Evaluating the Ability of Large Language Models to Reason About Cardinal Directions}},
  booktitle =	{16th International Conference on Spatial Information Theory (COSIT 2024)},
  pages =	{28:1--28:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-330-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{315},
  editor =	{Adams, Benjamin and Griffin, Amy L. and Scheider, Simon and McKenzie, Grant},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2024.28},
  URN =		{urn:nbn:de:0030-drops-208432},
  doi =		{10.4230/LIPIcs.COSIT.2024.28},
  annote =	{Keywords: Large Language Models, Spatial Reasoning, Cardinal Directions}
}
Document
DOI: 10.4230/LIPIcs.CP.2024.25
Combining Constraint Programming Reasoning with Large Language Model Predictions

Authors: Florian Régin, Elisabetta De Maria, and Alexandre Bonlarron

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
Constraint Programming (CP) and Machine Learning (ML) face challenges in text generation due to CP’s struggle with implementing "meaning" and ML’s difficulty with structural constraints. This paper proposes a solution by combining both approaches and embedding a Large Language Model (LLM) in CP. The LLM handles word generation and meaning, while CP manages structural constraints. This approach builds on GenCP, an improved version of On-the-fly Constraint Programming Search (OTFS) using LLM-generated domains. Compared to Beam Search (BS), a standard NLP method, this combined approach (GenCP with LLM) is faster and produces better results, ensuring all constraints are satisfied. This fusion of CP and ML presents new possibilities for enhancing text generation under constraints.
Cite as

Florian Régin, Elisabetta De Maria, and Alexandre Bonlarron. Combining Constraint Programming Reasoning with Large Language Model Predictions. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{regin_et_al:LIPIcs.CP.2024.25,
  author =	{R\'{e}gin, Florian and De Maria, Elisabetta and Bonlarron, Alexandre},
  title =	{{Combining Constraint Programming Reasoning with Large Language Model Predictions}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{25:1--25:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.25},
  URN =		{urn:nbn:de:0030-drops-207109},
  doi =		{10.4230/LIPIcs.CP.2024.25},
  annote =	{Keywords: Solver and Tools, ML-augmented CP, Constrained Text Generation, ML alongside CO}
}
Document
DOI: 10.4230/LIPIcs.WABI.2024.3
An Efficient Algorithm for the Reconciliation of a Gene Network and Species Tree

Authors: Yao-ban Chan

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract
The phylogenies of species and the genes they contain are similar but distinct, due to evolutionary events that affect genes but do not create new species. These events include gene duplication and loss, but also paralog exchange (non-allelic homologous recombination), where duplicate copies of a gene recombine. To account for paralog exchange, the evolutionary history of the genes must be represented in the form of a phylogenetic network. We reconstruct the interlinked evolution of the genes and species with reconciliations, which map the gene network into the species tree by explicitly accounting for these events. In previous work, we proposed the problem of reconciling a gene network and a species tree, but did not find an efficient solution for a general gene network. In this paper, we develop such a solution, and prove that it solves the most parsimonious reconciliation problem. Our algorithm is exponential only in the level of the gene network (with a base of 2), and we demonstrate that it is a practical solution through simulations. This allows, for the first time, a fine-grained study of the paralogy/orthology relationship between genes along their sequences.
Cite as

Yao-ban Chan. An Efficient Algorithm for the Reconciliation of a Gene Network and Species Tree. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chan:LIPIcs.WABI.2024.3,
  author =	{Chan, Yao-ban},
  title =	{{An Efficient Algorithm for the Reconciliation of a Gene Network and Species Tree}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.3},
  URN =		{urn:nbn:de:0030-drops-206472},
  doi =		{10.4230/LIPIcs.WABI.2024.3},
  annote =	{Keywords: Reconciliation, recombination, paralog exchange, phylogenetic network, gene duplication, gene loss}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.43
Rods and Rings: Soft Subdivision Planner for R^3 x S^2

Authors: Ching-Hsiang Hsu, Yi-Jen Chiang, and Chee Yap

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We consider path planning for a rigid spatial robot moving amidst polyhedral obstacles. Our robot is either a rod or a ring. Being axially-symmetric, their configuration space is R^3 x S^2 with 5 degrees of freedom (DOF). Correct, complete and practical path planning for such robots is a long standing challenge in robotics. While the rod is one of the most widely studied spatial robots in path planning, the ring seems to be new, and a rare example of a non-simply-connected robot. This work provides rigorous and complete algorithms for these robots with theoretical guarantees. We implemented the algorithms in our open-source Core Library. Experiments show that they are practical, achieving near real-time performance. We compared our planner to state-of-the-art sampling planners in OMPL [Sucan et al., 2012]. Our subdivision path planner is based on the twin foundations of epsilon-exactness and soft predicates. Correct implementation is relatively easy. The technical innovations include subdivision atlases for S^2, introduction of Sigma_2 representations for footprints, and extensions of our feature-based technique for "opening up the blackbox of collision detection".
Cite as

Ching-Hsiang Hsu, Yi-Jen Chiang, and Chee Yap. Rods and Rings: Soft Subdivision Planner for R^3 x S^2. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{hsu_et_al:LIPIcs.SoCG.2019.43,
  author =	{Hsu, Ching-Hsiang and Chiang, Yi-Jen and Yap, Chee},
  title =	{{Rods and Rings: Soft Subdivision Planner for R^3 x S^2}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.43},
  URN =		{urn:nbn:de:0030-drops-104477},
  doi =		{10.4230/LIPIcs.SoCG.2019.43},
  annote =	{Keywords: Algorithmic Motion Planning, Subdivision Methods, Resolution-Exact Algorithms, Soft Predicates, Spatial Rod Robots, Spatial Ring Robots}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.73
Soft Subdivision Motion Planning for Complex Planar Robots

Authors: Bo Zhou, Yi-Jen Chiang, and Chee Yap

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
The design and implementation of theoretically-sound robot motion planning algorithms is challenging. Within the framework of resolution-exact algorithms, it is possible to exploit soft predicates for collision detection. The design of soft predicates is a balancing act between easily implementable predicates and their accuracy/effectivity. In this paper, we focus on the class of planar polygonal rigid robots with arbitrarily complex geometry. We exploit the remarkable decomposability property of soft collision-detection predicates of such robots. We introduce a general technique to produce such a decomposition. If the robot is an m-gon, the complexity of this approach scales linearly in m. This contrasts with the O(m^3) complexity known for exact planners. It follows that we can now routinely produce soft predicates for any rigid polygonal robot. This results in resolution-exact planners for such robots within the general Soft Subdivision Search (SSS) framework. This is a significant advancement in the theory of sound and complete planners for planar robots. We implemented such decomposed predicates in our open-source Core Library. The experiments show that our algorithms are effective, perform in real time on non-trivial environments, and can outperform many sampling-based methods.
Cite as

Bo Zhou, Yi-Jen Chiang, and Chee Yap. Soft Subdivision Motion Planning for Complex Planar Robots. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{zhou_et_al:LIPIcs.ESA.2018.73,
  author =	{Zhou, Bo and Chiang, Yi-Jen and Yap, Chee},
  title =	{{Soft Subdivision Motion Planning for Complex Planar Robots}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{73:1--73:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.73},
  URN =		{urn:nbn:de:0030-drops-95361},
  doi =		{10.4230/LIPIcs.ESA.2018.73},
  annote =	{Keywords: Computational Geometry, Algorithmic Motion Planning, Resolution-Exact Algorithms, Soft Predicates, Planar Robots with Complex Geometry}
}
  • Refine by Author
  • 2 Chiang, Yi-Jen
  • 2 Yap, Chee
  • 1 Blackwell, Robert E
  • 1 Bonlarron, Alexandre
  • 1 Chan, Yao-ban
  • Show More...

  • Refine by Classification
  • 2 Computing methodologies → Robotic planning
  • 2 Computing methodologies → Spatial and physical reasoning
  • 2 Theory of computation → Computational geometry
  • 1 Applied computing → Computational biology
  • 1 Computing methodologies → Ontology engineering
  • Show More...

  • Refine by Keyword
  • 2 Algorithmic Motion Planning
  • 2 Resolution-Exact Algorithms
  • 2 Soft Predicates
  • 1 Cardinal Directions
  • 1 Computational Geometry
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 4 2024
  • 1 2018
  • 1 2019

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