2 Search Results for "Zhou, Bo"

Document
DOI: 10.4230/LIPIcs.SAT.2023.29
LS-DTKMS: A Local Search Algorithm for Diversified Top-k MaxSAT Problem

Authors: Junping Zhou, Jiaxin Liang, Minghao Yin, and Bo He

Published in: LIPIcs, Volume 271, 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)

Abstract
The Maximum Satisfiability (MaxSAT), an important optimization problem, has a range of applications, including network routing, planning and scheduling, and combinatorial auctions. Among these applications, one usually benefits from having not just one single solution, but k diverse solutions. Motivated by this, we study an extension of MaxSAT, named Diversified Top-k MaxSAT (DTKMS) problem, which is to find k feasible assignments of a given formula such that each assignment satisfies all hard clauses and all of them together satisfy the maximum number of soft clauses. This paper presents a local search algorithm, LS-DTKMS, for DTKMS problem, which exploits novel scoring functions to select variables and assignments. Experiments demonstrate that LS-DTKMS outperforms the top-k MaxSAT based DTKMS solvers and state-of-the-art solvers for diversified top-k clique problem.
Cite as

Junping Zhou, Jiaxin Liang, Minghao Yin, and Bo He. LS-DTKMS: A Local Search Algorithm for Diversified Top-k MaxSAT Problem. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 271, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{zhou_et_al:LIPIcs.SAT.2023.29,
  author =	{Zhou, Junping and Liang, Jiaxin and Yin, Minghao and He, Bo},
  title =	{{LS-DTKMS: A Local Search Algorithm for Diversified Top-k MaxSAT Problem}},
  booktitle =	{26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-286-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{271},
  editor =	{Mahajan, Meena and Slivovsky, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2023.29},
  URN =		{urn:nbn:de:0030-drops-184912},
  doi =		{10.4230/LIPIcs.SAT.2023.29},
  annote =	{Keywords: Top-k, MaxSAT, local search}
}
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-dev.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
  • 1 Chiang, Yi-Jen
  • 1 He, Bo
  • 1 Liang, Jiaxin
  • 1 Yap, Chee
  • 1 Yin, Minghao
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Robotic planning
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Constraint and logic programming
  • 1 Theory of computation → Random search heuristics

  • Refine by Keyword
  • 1 Algorithmic Motion Planning
  • 1 Computational Geometry
  • 1 MaxSAT
  • 1 Planar Robots with Complex Geometry
  • 1 Resolution-Exact Algorithms
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 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