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

• Autorzy: Aleksińska A.

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.

Słowa kluczowe

PL

identyfikacja terenu; robot mobilny autonomiczny; współczynnik konkurencyjności; dolne oszacowanie współczynnika konkurencyjności

EN

terrian identification; autonomous mobile robot; competitive factor; lower bound on the competitive factor

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2007
• Tom: T. 13
• Strony: 523--530
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Aleksińska A.

• 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.