PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Efektywność algorytmów identyfikacji nieznanego terenu przy użyciu autonomicznego robota mobilnego

Autorzy
Identyfikatory
Warianty tytułu
EN
A note on lower bound for competitive factor for terrian identification by autonomous robot
Języki publikacji
PL
Abstrakty
PL
Praca dotyczy identyfikacji nieznanego terenu autonomicznym robotem mobilnym z ograniczonym zasięgiem widoczności. W pracy zakłada się, ze środowisko, w którym porusza się robot jest wielokątem ortogonalnym podzielonym na kwadraty (pola) o boku jeden. Przyjęto także, że robot widzi tylko cztery pola przylegające do pola, na którym się znajduje. Zadaniem robota jest odwiedzenie każdego pola i powrót do startu w jak najkrótszym czasie. W pracy wykażemy, ze nie istnieje strategia minimalizacji długości trasy robota o współczynniku konkurencyjności mniejszym niż 20/17 , tzn. strategia powalającą wyznaczyć trasę robota stanowiącą co najwyżej 20/l7 długości optymalnej trasy offline. Poprawia to najlepsze dolne oszacowanie współczynnika konkurencyjności, które wynosi 7/6.
EN
We consider the problem of identification an unknown orthogonal polygon by an autonomous mobile robot with a bounded line of sight. We give lower bound on the competitive factor for the considered problem. We show that there is no online algorithm that find robots paths shorter than 20/17 of length of the optimal online path.
Twórcy
  • Katedra Algorytmów i Modelowania Systemów, Politechnika Gdańska
Bibliografia
  • [1] Agnieszka Aleksińska, Adrian Kosowski, Michał Małafiejski, Identyfikacja terenu za pomocą autonomicznego robota. Zeszyty Naukowe Politechniki Śląskiej, 1728: 11-18, 2006.
  • [2] Esther M. Arkin, Sandor P. Fekete, Joseph S. B. Mitchell. Approximation algorithms for lawn mowing and milling. Computational Geometry: Theory and Applications, 17:25-50,2000.
  • [3] Sanjeev Arora. Polynomial time approximation schemes for Euc1idean traveling salesman and other geometric problems. Journal of the A CM, 45(5):753-782, 1998.
  • [4] Yoav Gabriely and Elon Rimon. Competitive on-line coverage of grid environments by a mobile robot. Computational Geometry: Theory and Applications, 24(3): 197-224, April 2004.
  • [5] Michelangelo Grigni, Elias Koutsoupias, and Christos Papadimitriou. An approximation scheme for planar graph TSP. Proceedings of the Thirty-Sixth Annual IEEE Symposium on the Foundations of Computer Science(FOCS '95), s. 387-411, 1995.
  • [6] Christian Icking, Thomas Kamphans, Rolf Klein, and Elmar Langetepe. Exploring an unknown cellular environment. Abstracts 16th European Workshop Comput. Geom., s. 140-143, 2000.
  • [7] Christian Icking, Thomas Kamphans, Rolf Klein, and Elmar Langetepe. Exploring simple grid polygons. Lecture Notes in Computer Science, 3595:524-533, 2005.
  • [8] Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter. Hamilton paths in grid graphs. SIAM Journal on Computing, 11(4):676-686, 1983.
  • [9] Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journalon Computing, 28(4):1298-1309,1999.
  • [10] Simeon C. Ntafos. Watchman routes under limited visibility. Computational Geometry: Theory and Applications, 1(3):149-170, 1993.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BPG5-0030-0009
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.