How to Navigate Through Obstacles?

Authors Eduard Eiben , Iyad Kanj



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.48.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Eduard Eiben
  • Department of Informatics, University of Bergen, Bergen, Norway
Iyad Kanj
  • School of Computing, DePaul University, Chicago, USA

Cite AsGet BibTex

Eduard Eiben and Iyad Kanj. How to Navigate Through Obstacles?. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.48

Abstract

Given a set of obstacles and two points in the plane, is there a path between the two points that does not cross more than k different obstacles? This is a fundamental problem that has undergone a tremendous amount of work by researchers in various areas, including computational geometry, graph theory, wireless computing, and motion planning. It is known to be NP-hard, even when the obstacles are very simple geometric shapes (e.g., unit-length line segments). The problem can be formulated and generalized into the following graph problem: Given a planar graph G whose vertices are colored by color sets, two designated vertices s, t in V(G), and k in N, is there an s-t path in G that uses at most k colors? If each obstacle is connected, the resulting graph satisfies the color-connectivity property, namely that each color induces a connected subgraph. We study the complexity and design algorithms for the above graph problem with an eye on its geometric applications. We prove a set of hardness results, among which a result showing that the color-connectivity property is crucial for any hope for fixed-parameter tractable (FPT) algorithms, as without it, the problem is W[SAT]-hard parameterized by k. Previous results only implied that the problem is W[2]-hard. A corollary of this result is that, unless W[2] = FPT, the problem cannot be approximated in FPT time to within a factor that is a function of k. By describing a generic plane embedding of the graph instances, we show that our hardness results translate to the geometric instances of the problem. We then focus on graphs satisfying the color-connectivity property. By exploiting the planarity of the graph and the connectivity of the colors, we develop topological results that allow us to prove that, for any vertex v, there exists a set of paths whose cardinality is upper bounded by a function of k, that "represents" the valid s-t paths containing subsets of colors from v. We employ these structural results to design an FPT algorithm for the problem parameterized by both k and the treewidth of the graph, and extend this result further to obtain an FPT algorithm for the parameterization by both k and the length of the path. The latter result generalizes and explains previous FPT results for various obstacle shapes, such as unit disks and fat regions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Computational geometry
  • Mathematics of computing → Graph algorithms
Keywords
  • parameterized complexity and algorithms
  • motion planning
  • barrier coverage
  • barrier resilience
  • colored path
  • minimum constraint removal
  • planar graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. H. Alt, S. Cabello, P. Giannopoulos, and C. Knauer. Minimum cell connection in line segment arrangements. International Journal of Computational Geometry and Applications, 27(3):159-176, 2017. Google Scholar
  2. S. Bereg and D. Kirkpatrick. Approximating barrier resilience in wireless sensor networks. In Proceedings of ALGOSENSORS, pages 29-40, 2009. Google Scholar
  3. R. Carr, S. Doddi, G. Konjevod, and M. Marathe. On the red-blue set cover problem. In Proceedings of SODA, pages 345-353, 2000. Google Scholar
  4. D. Chan and D. Kirkpatrick. Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience. Theoretical Computer Science, 553:74-90, 2014. Google Scholar
  5. R. Diestel. Graph Theory, 4th Edition. Springer, 2012. Google Scholar
  6. R. Downey and M. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin, Heidelberg, 2013. Google Scholar
  7. E. Eiben, J. Gemmell, I. Kanj, and A. Youngdahl. Improved results for minimum constraint removal. In Proceedings of AAAI. AAAI Press, 2018. Google Scholar
  8. E. Eiben and I. Kanj. How to navigate through obstacles? CoRR, abs/1712.04043v1, 2017. URL: http://arxiv.org/abs/1712.04043.
  9. L. Erickson and S. LaValle. A simple, but NP-hard, motion planning problem. In Proceedings of AAAI. AAAI Press, 2013. Google Scholar
  10. A. Gorbenko and V. Popov. The discrete minimum constraint removal motion planning problem. In Proceedings of the American Institute of Physics, volume 1648. AIP Press, 2015. Google Scholar
  11. K. Hauser. The minimum constraint removal problem with three robotics applications. International Journal of Robotics Research, 33(1):5-17, 2014. Google Scholar
  12. M. Korman, M. Löffler, R. Silveira, and D. Strash. On the complexity of barrier resilience for fat regions and bounded ply. Computational Geometry, 72:34-51, 2018. Google Scholar
  13. S. Kumar, T. Lai, and A. Arora. Barrier coverage with wireless sensors. In Proceedings of MOBICOM, pages 284-298. ACM, 2005. Google Scholar
  14. N. Robertson and P. Seymour. Graph minors. III. planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49-64, 1984. Google Scholar
  15. K. Tseng and D. Kirkpatrick. On barrier resilience of sensor networks. In Proceedings of ALGOSENSORS, pages 130-144, 2012. Google Scholar
  16. S. Yang. Some Path Planning Algorithms in Computational Geometry and Air Traffic Management. PhD thesis, University of New Yort at Stony Brook. Available at: https://dspace.sunyconnect.suny.edu/handle 59927, 2012. Google Scholar
  17. S. Yuan, S. Varma, and J. Jue. Minimum-color path problems for reliability in mesh networks. In Proceedings of INFOCOM, pages 2658-2669, 2005. Google Scholar
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