Coverage over grid-kort - Coverage - et "traveling salesman" problem

Katarina  Deylami

Jeg er din kontaktperson

Skriv til mig

Indtast venligst et validt navn
Eller dit telefonnummer
Sender besked
Tak for din besked
Vi beklager

På grund af en teknisk fejl kan din henvendelse desværre ikke modtages i øjeblikket. Du er velkommen til at skrive en mail til Send e-mail eller ringe til +45 72 20 28 87.

Coverage over grid-kort - Coverage - et "traveling salesman" problem

En anden måde at se på coverage problemet over et gitterkort er som et netværk med relationer mellem de enkelte felter i kortet. Hvert felt har op til otte nabofelter det er muligt at bevæge sig til. Ved at definere en såkaldt "cost" funktion er det muligt at programmere en søgealgoritme, der ud fra de definerede parametre vil planlægge en optimal bane gennem kortet.

Grid-kort og den træstruktur der repræsenterer kortet

Problemet er dog meget kompliceret og løsningen langt fra triviel. De senere år er computerkraften på de mobile robotter dog steget så meget at det har været muligt at benytte de såkaldte Spanning-tree algoritmer til at beregne en bane over kortet i polynomisk tid [1]. Algoritmen har siden da været udsat for megen forskning og algoritmer til at lave coverage med flere robotter der deler et område, er blevet muligt [2,3,4]. Et eksempel på hvordan et coverage-problem løst med spanning-tree algoritmen kunne se ud ses herunder.

Grafisk repræsenteret spanning-tree coverage

Fordele, ulemper og forbedringer

Denne algoritme har fordel af at kunne løse coverage-problemet uden at skabe lokale minimumspunkter som potentialefunktionerne risikerer. Derudover muliggør algoritmen struktureret coverage med mere end en robot. Algoritmerne der benytter inddelingen i felter har en stor ulempe nemlig at felterne er kvadratiske, hvilket gør at de passer dårligt sammen med en mobil robots bløde drejebevægelser og forhindringernes sjældent geometrisk korrekte udformning. Det kan derfor være nødvendigt at køre tæt rundt om forhindringer og de steder robotten har skullet dreje, for at øge kvaliteten af arbejdet. 

Referencer:

[1] Y.Gabriely and E.Rimon. Spanning-tree based coverage of continuous areas by a mobile robot. Annals of Mathematics and Artificial Intelligence, 31:77-98, 2001

[2] X.Zheng, S.Jain, S. Koinig and D.Kempe. Multi-Robot Forest Coverage. Department of Computer Science - University of California, 2006

[3] N.Agmon, N.Hazon and G.A.Kaminka. Constructing Spanning Trees for Efficient Multi-Robot Coverage. Department of Computer Science - Bar Ilan University, 2006

[4] N.Hazon and G.A.Kaminka. Redundancy, Efficiency and Robustness in Multi-Robot Coverage. Department of Computer Science - Bar Ilan University, 2005