Laden...

Suche Denkanstoß: Rasenmäherproblem

Erstellt von Levion vor 10 Jahren Letzter Beitrag vor 10 Jahren 1.723 Views
Levion Themenstarter:in
114 Beiträge seit 2009
vor 10 Jahren
Suche Denkanstoß: Rasenmäherproblem

Hallo,

ich habe ich recht grundlegendes Problem bei dem ich nicht so recht weiterkomme. Ich möchte gerne einen Algorithmus entwerfen, der auf einer vordefinierten Flächen eine Route berechnet um möglichst 100% der Fläche "abzuschreiten". Am Besten kann man sich das wie einen Rasenmäher vorstellen, der möglichst nicht über bereits gemähten Flächen fahren soll, weil durch mehrfaches Fahren der Rasen kaputt geht und eine gewisse Spannbreite hat. Außerhalb des Bereichs sollte er sich aber auch nicht bewegen.

Mich erinnert das ganze an das Problem, wo der Springer auf jedes Feld des Schachbretts springen soll aber kein Feld doppelt besuchen sollte. Deshalb ist mein erster Ansatz auch mein Polygon in Quadrate und Polygone zu zerteilen und durch Ziehen und Backtracking die richtige Route zu finden.

D.h. ich setzen ein Quadrat vor das Nächste und wenn das Quadrat weniger als 50% des Quadrats belegt, dann muss nach rechts oder links gewendet werden.

Hat jemand sowas schonmal entworfen? Gibt es da einen besseren/schlaueren Weg?

Gruß

Levion

771 Beiträge seit 2009
vor 10 Jahren

Hi Levion,

dies ist ein bekanntes Problem aus der Landwirtschaft für automatisches Lenken mit GPS (GPS steering autopilot). Dabei wird üblicherweise eine sog. Referenzlinie benötigt, anhand deren dann der Rest des Feldes abgefahren wird.
Ich denke aber nicht, daß du einen einfachen Algorithmus dafür finden wirst (soweit ich weiß wird das meiste mit Simulationsprogrammen à la MATLAB/Simulink o.ä. umgesetzt, d.h. dort ist jahrelange Entwicklung drin).

799 Beiträge seit 2007
vor 10 Jahren

Folgender Versuch fällt mir da spontan ein: Du teilst deine Fläche in Zonen ein die klein genug sind, dass der Rasenmäher beim darüber fahren alles erwischt.

Du baust dir einen Graphen wobei eine jede Zone ein Knoten ist und mit allen anderen liegenden Knoten/Zonen verbunden ist. Die Kanten bewertest du anhand der Distanz. Dann suchst du dir einen effizienten Travelling Sales Man Algorithmus und hoffst auf das Beste 🙂

Ich denke aber nicht, daß du einen einfachen Algorithmus dafür finden wirst

Wo kämen wir hin, wenn jeder sagte, wo kämen wir hin und keiner ginge, um zu sehen, wohin wir kämen, wenn wir gingen. 😉

As a man thinketh in his heart, so he is.

  • Jun Fan
    Es gibt nichts Gutes, außer man tut es.
  • Erich Kästner
    Krawutzi-Kaputzi
  • Kasperl
16.825 Beiträge seit 2008
vor 10 Jahren

Bei Landwirtschaft und Co gehen die Algorithmen aber eher in die Richtung, dass zB eine Fläche zwar mehfach geerntet wird, aber insgesamt die Abarbeitungszeit am schnellsten >> effizientesten ist. Bei der Saat nimmt man in Kauf, dass manche Bereiche mehr Samen bekommen oder es werden gewisse Teile ausgelassen.
Man muss auch immer abwägen, ob die Berechnungszeit eine Rolle spielt. Da würde man dann in Richtung Ameisenalgorithmus gehen.

Ich würde an dieser Stelle versuchen möglichst lange in eine Richtung zu fahren, da Richtungswechsel (in der Realität) immer Zeit kosten.
Aus diesem Grund fahren Gärtner oder auch Präperatoren von Eishallen mit ihren Maschinen auch meist im Kreis.
Es wird aber immer einen Punkt geben, an dem man dann evtl. auf eine andere Methode umschenken muss um die Restfläche effizienter zu bearbeiten - gerade bei unnatürlichen Formen.

Einen 100%tigen Weg wirds selten geben.

5.658 Beiträge seit 2006
vor 10 Jahren

Hi Levion,

fährt man mit einem Rasenmäher nicht meistens zuerst die Ränder ab, um sich dann "spiralförmig" dem Zentrum zu nähern? Dadurch wird das Polygon mit jeder Umrundung ein bißchen kleiner. Oder man unterteilt das eine, große Polygon in mehrere kleinere (konvexe) Polygone und geht bei jedem davon so vor. Dann könnte der Algorithmus auf dem Straight Skeleton des Polygons (oder der Teilpolygone) aufbauen.

Alternativ kann man die Fläche in Streifen unterteilen und immer einen Streifen nach dem anderen abmähen. Bei beiden Varianten dürfte jeder Polygonbereich nur einmal befahren werden.

Christian

Weeks of programming can save you hours of planning

1.361 Beiträge seit 2007
vor 10 Jahren

Ich greife auch mal die Idee von "der-schlingel" auf.
Als "minimale Zonen" würde ich Kreise nehmen, deren Durchmesser gerade deine Spannbreite ist. Mit diesen Kreisen baust du nun eine überlappende Parkettierung auf, analog zu einem hexagonalen Waben-Raster.
Der entsprechende Zonengraph muss nun traversiert werden.
Dann fügst du noch einen Knoten für "außen" ein und du kannst nach Rundreisen suchen.

Entweder verbindest du alle Zonen mit allen und suchst nach einer TSP Route wie vom Schlingel vorgeschlagen.
Mir fiele aber noch ein, nur benachbarte Zonen zu verbinden. Dann ist der Graph nur nicht mehr vollständig, was manchmal bedeuten kann, dass es keine TSP-Route gibt, weil man manche Felder zwangsläufig mehrfach besuchen muss.
Aber auch dafür gibts natürlich ne "Abwandlung" von TSP. Nennt sich dann "shortest closed spanning walk", manchmal auch "hamiltonian walk". Also die kürzeste Rundreise, die jeden Knoten mindestens einmal besucht. Um eben alle Stellen des Rases zu mähen, muss man manchmal an einer Stelle zweimal vorbeifahren.

Und für Hamiltonian Walks gibt es sogar eine polynomielle Heuristik, genau für maximale planare Graphen (wie hier gegeben), die maximal 50% vom Optimum entfernt ist.
[Paper (PDF): An Approximation Algorithm for the Hamiltonian Walk Problem on Maximal Planar Graphs]

Der von Abt erwähnten Tatsache, dass Richtungswechsel (in der Realität) immer Zeit kosten, wird hierbei natürlich keineswegs Rechnung getragen.

beste Grüße
zommi