Identyfikacja terenu za pomocą autonomicznego robota

• Autorzy: Aleksińska A. , Kosowski A. , Małafiejski M.

Warianty tytułu

EN

Terrain layout identification using autonomous robot units

• Konferencja: XV Krajowa Konferencja Automatyzacji Procesów Dyskretnych, Zakopane, 20-23 września 2006r.
• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

robot autonomiczny; identyfikacja terenu; model matematyczny

EN

autonomous robot unit; terrain layout; mathematical model

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2006
• Tom: z. 145
• Strony: 11--18
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Aleksińska A.

autor

Kosowski A.

autor

Małafiejski M.

• Katedra Algorytmów i Modelowania Systemów Politechniki Gdańskiej, 80-952 Gdańsk Wrzeszcz, ul. Gabriela Narutowicza 11/12, tel.: [phone],

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.