Padplanning voor volledige dekking: de hele vloer

Een ander probleem dan “ergens komen”

A* vindt één route naar één doel. Een dekkingsplanner moet elke bereikbare tegel aanraken, en dat verandert het doel volledig: er is geen doel om in de buurt van te komen, geen heuristiek die je de weg wijst, en succes is niet binair.

De maat die daarvoor in de plaats komt, is de afstand per bestreken vierkante meter. Met vloeroppervlak A en een gereedschap van breedte w veegt een perfecte robot elke vierkante meter één keer en nooit opnieuw:

d_optimal = A / w

Een kamer van 20 m² met een borstel van 250 mm vraagt 80 m. Elk getal hieronder is een veelvoud daarvan, want een veelvoud is de enige vergelijking die een veranderde kamer overleeft.

De wet die het vegen zonder kaart bepaalt

Een robot die geen idee heeft waar hij is geweest, bestrijkt nieuwe vloer naar evenredigheid van de hoeveelheid vloer die er nog onbestreekt is. Dat is een differentiaalvergelijking met één antwoord:

covered(d) ≈ 1 − e^(−d / d_optimal)

Lees er drie punten vanaf en de vorm van het hele probleem doet zich voor:

De laatste 9% kost meer dan de eerste 90%. Dit is het couponverzamelprobleem met een borstel eraan vastgemaakt, en het is dat ene feit dat elke robotstofzuiger verklaart die je ooit hebt zien rondrijden.

Wat er werkelijk gebeurt

Theorie neemt aan dat elke meter op vloer terechtkomt die onafhankelijk van de vorige is gekozen. Een echte robot rijdt in rechte lijnen, dus opeenvolgende meters zijn gecorreleerd — hij veegt steeds opnieuw het stuk waar hij al staat. Gemeten over vijf kamers in de coverage simulator:

Drie dingen in die tabel zijn belangrijker dan de rest van deze pagina.

Voor de eerste helft van de vloer maakt niets uit. Alle drie de strategieën liggen bij 50% binnen 20% van elkaar. Een robot zonder waarneming en zonder geheugen is voor de eerste helft van de klus werkelijk even goed als een planner — en dat is precies waarom de goedkope aanpak commercieel haalbaar is, en waarom losse waarneming het verschil nooit aan het licht brengt.

Willekeurig presteert slechter dan de eigen theorie. 6,76× tegen een voorspelde 4,61× bij 99%, omdat een stuiterende rechte lijn steeds vloer opnieuw bezoekt die hij zojuist heeft gedaan. Behandel 1 − e^(−d) als de optimistische bovengrens, niet als de schatting.

De planner maakt nooit af. Hij stopt op 90,4% en blijft daar, en dat is geen bug.

Waarom de planner een tiende van de vloer laat liggen

Een dekkingsplanner moet het lichaam van de robot vrij houden van elke muur en elke tafelpoot, dus hij blaast elk obstakel op met de straal van de robot plus een marge en plant binnen wat overblijft. Wat erbuiten valt, is vloer waar de robot nooit kan komen.

In de gemeten run lagen 130 van de 133 tegels die de planner miste binnen twee cellen van een muur of een stuk meubilair. Slechts drie daarvan waren open vloer. De missers zijn niet verspreid — ze vormen een ring rond elk obstakel in de kamer.

Dat verklaart twee eigenschappen van elke commerciële machine:

• De zijborstel die over het chassis uitsteekt. De borstel is breder dan het deel dat botst, dus hij bereikt vloer waar de wielen nooit komen.
• De muurvolgrondgang. Dat is een apart gedrag, apart uitgevoerd, omdat de systematische veging dat structureel niet kan.

Willekeurig stuiteren bereikt die randen uiteindelijk, bij toeval, en dat is het enige waarin het beter is.

Rijafstanden kiezen

Voor een systematische veging is de enige echte parameter de rijafstand.

Plaats de rijen op precies één borstelbreedte van elkaar en elke richtingsafwijking laat een ongereinigde strook ertussen staan — en niets later vindt die, want het plan gelooft dat die vloer klaar is. Laat ze 10–20% overlappen en de stroken sluiten, voor een prijs van precies dat percentage in afstand.

Die overlap, plus de verplaatsingsafstand om meubilair heen, is waar de 1,35× van de planner vandaan komt. Het is geen verspilling; het is de prijs van een plan dat overeind blijft in contact met een echte robot.

Nog twee keuzes die belangrijker zijn dan ze lijken:

• Rij langs de lange as van de kamer. Elke bocht kost tijd en bestrijkt geen nieuwe vloer, dus halveren van het aantal rijen halveert de bochtoverhead.
• Route tussen de stukken, niet ertussen rijden. Als meubilair een rij in twee stukken verdeelt, moet de robot er omheen. Dat verplaatsen te plannen als een kortste pad door vrije ruimte is het verschil tussen een plan en een wens.

De waarneming die elke strategie vraagt

Dit is de echte reden dat ze er alle drie zijn.

Willekeurig stuiteren heeft één bit nodig. Heb ik iets geraakt. Twee bumpschakelaars en een willekeurgetalgenerator is de hele robot. Geen encoders, geen kaart, geen lokalisatie, en niets dat kan driften.

Spiraalbeweging moet weten hoe ver het is sinds het middelpunt van de huidige spiraal, en dat is een grove odometrie — goed genoeg om een straal te laten groeien, niet goed genoeg om een lus te sluiten.

Een geplande veging moet weten waar hij is. Rechte rijen, bekende bochthoeken en een zijwaartse stap van één borstelbreedte zijn allemaal claims van de odometrie, en odometrie drijft. Na tien rijen zijn de rijen niet meer evenwijdig. Daarom voeren commerciële machines die plannen ook een gyro, een plafondcamera of een beacon mee — de planner is goedkoop, de lokalisatie die hij aanneemt niet.

Dus de strategie wordt gekozen op basis van het waarnemingsbudget, niet op basis van de elegantie van het algoritme. Bouw eerst de willekeurige: hij werkt, hij is twintig regels, en hij geeft je een basislijn die de planner moet verslaan.

Wat het in minuten kost

Neem die kamer van 20 m², een borstel van 250 mm en een robot die 0,25 m/s rijdt:

Een accu is een afstandbudget. Een bedrijfstijd van een uur bij 0,25 m/s is 900 m, wat één kamer ruim willekeurig dekt en drie niet — en dat, en niet enig algoritmisch inzicht, is wat de markt naar mappingsrobots heeft geduwd.

Wanneer het misgaat

Draai alle drie tegen dezelfde kamer in de coverage simulator — sleep het meubilair terwijl ze draaien en de getallen bewegen mee. Bouw daarna de room coverage robot, die begint met de strategie die niets nodig heeft en alleen waarneming toevoegt waar de meting zegt dat het loont.