Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
Terrain layout identification using autonomous robot units
Konferencja
XV Krajowa Konferencja Automatyzacji Procesów Dyskretnych, Zakopane, 20-23 września 2006r.
Języki publikacji
Abstrakty
W pracy rozważane jest zagadnienie identyfikacji nieznanego terenu za pomocą autonomicznego robota o ograniczonym zasięgu widzialności. Przyjęty model matematyczny zakłada, że teren ma postać ograniczonej dwuwymiarowej mapy podzielonej na identyczne kwadratowe obszary (pola) przylegające do siebie bokami. Zadaniem autonomicznego robota, którego zasięg widzialności ogranicza się do pól przylegających do miejsca, w którym się znajduje, jest identyfikacja całej mapy, poprzez odwiedzenie wszystkich jej pól w możliwie najmniejszej liczbie ruchów robota. Ponieważ problem w wersji on-line nie posiada dokładnego rozwiązania, autorzy skoncentrowali się na konstrukcji algorytmu przybliżonego dla szczególnych typów map z gwarantowaną dokładnością C, gdzie C jest liczbą pól całej mapy.
We consider the problem of identifying an unknown terrain layout using an autonomous mobile robot with a bounded line of sight. Since in the general case there does not exist an exact on-line algorithm for the considered problem, we restrict our considerations to the construction of an approximation algorithm for special classes of maps, proving an upper bound of C moves for the proposed approach, where C denotes the area of the map measured in squares.
Rocznik
Tom
Strony
11--18
Opis fizyczny
Bibliogr. 8 poz.
Twórcy
autor
autor
autor
- Katedra Algorytmów i Modelowania Systemów Politechniki Gdańskiej, 80-952 Gdańsk Wrzeszcz, ul. Gabriela Narutowicza 11/12, tel.: (058) 347-19-56, kosowski@eti.pg.gda.pl
Bibliografia
- 1. Arkin E.M., Fekete S.P, Mitchell J.S.B.: Approximation algorithms for lawn mowing and milling. Mathematisches Institut, Universität zu Köln 1997.
- 2. Deng X., Kameda T., Papadimitriou O: How to learn an unknown environment I: The rectilinear case. J.ACM, 45(2), 1998, p. 215-245.
- 3. Fuszara M., Kosowski A., Małafiejski M.: Outline of an environment for the simulation of autonomous military units. Zesz. Nauk. Pol. Gd., Ser. Technologie Informacyjne, No. 5, 2004, p. 755-764.
- 4. Gabriely Y., Rimon E.: Competitive on-line coverage of grid environments by a mobile robot. Comput. Geom. Theory Appl., 24, 2003, p. 197-224.
- 5. Grigni M., Koutsoupias E., Papadimitriou C.H.: An approximation scheme for planar graph TSP. Proc. 36th Annu. IEEE Sympos. Found. Comput. Sci. (1995), p. 640-645.
- 6. Hoffmann F., Icking G, Klein R., Kriegel K.: The polygon exploration problem. SLAM J. Comput, 31, 2001, p. 577-600.
- 7. Icking C, Kamphans T., Klein R., Langetepe E.: Exploring Simple Grid Polygons. LNCS (2005) 3595, p. 524-533.
- 8. Icking C, Klein R., Langetepe E., Scliuierer S., Semrau I.: An optimal competitive strategy for walking in streets. SIAM J. Comput., 33, 2004, p. 462- 486.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL2-0013-0023