Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > de.sci.electronics > #201396 > unrolled thread

Kleines mathematisches Problem

Back to article view | Back to de.sci.electronics

Contents

  Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-04 17:49 +0100
    Re: Kleines mathematisches Problem Bernd Nebendahl <Bernd_Nebendahl@web.de> - 2016-02-04 17:54 +0100
      Re: Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-04 18:37 +0100
    Re: Kleines mathematisches Problem "MaWin" <me@private.net> - 2016-02-04 18:03 +0100
      Re: Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-04 18:23 +0100
        Re: Kleines mathematisches Problem "MaWin" <me@private.net> - 2016-02-04 18:36 +0100
          Re: Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-04 19:00 +0100
      Re: Kleines mathematisches Problem Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2016-02-04 22:32 +0100
      Re: Kleines mathematisches Problem Robin Koch <robin.koch@t-online.de> - 2016-02-05 02:57 +0100
    Re: Kleines mathematisches Problem Marc Santhoff <m.santhoff@t-online.de> - 2016-02-04 18:20 +0100
    Re: Kleines mathematisches Problem Thomas Prufer <prufer.public@mnet-online.de.invalid> - 2016-02-04 18:23 +0100
      Re: Kleines mathematisches Problem Robin Koch <robin.koch@t-online.de> - 2016-02-05 03:08 +0100
    Re: Kleines mathematisches Problem Lutz Schulze <lschulze@netzwerkseite.de> - 2016-02-04 18:59 +0100
      Re: Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-05 08:11 +0100
        Re: Kleines mathematisches Problem Christian Müller <spamalottomat@yahoo.de> - 2016-02-05 16:11 +0100
          Re: Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-05 17:13 +0100
    Re: Kleines mathematisches Problem Eric Brücklmeier <usenet@nerdcraft.de> - 2016-02-05 11:05 +0100
    Re: Kleines mathematisches Problem Thomas Heger <ttt_heg@web.de> - 2016-02-14 18:53 +0100
      Re: Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-14 20:04 +0100
        Re: Kleines mathematisches Problem Thomas Heger <ttt_heg@web.de> - 2016-02-15 05:13 +0100
          Re: Kleines mathematisches Problem Stefan <df9bi@arcor.de> - 2016-02-16 14:08 +0100
      Re: Kleines mathematisches Problem Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2016-02-15 18:33 +0100

Page 1 of 2  [1] 2  Next page →

#201396 — Kleines mathematisches Problem

Hallo,

vieleicht fehlt mir nur ein Schlüsselwort um was passendes zu finden.

Folgendes Problem:

Ein Roboter befindet sich an der Position (X1,Y1) auf einer Fläche. Er 
soll auf kürzestem Weg die Position (X2,Y2) anfahren.

Problem dabei, es gibt auf dem Weg diverse Hindernisse, also Bereiche, 
die umfahren werden müssen.

Ich stell mir das jetzt so vor, dass ich die Fläche in Kästchen 
aufteile, z.B. 100 Kästchen in X-Richtung und 100 Kästchen in 
Y-Richtung. Jedes Kästchen wird entweder mit 0 oder 1 markiert. Die 
erlaubten Kästen haben den Wert 0, die verbotenen den Wert 1.

Die Position der Hindernisse ist fest, ebenso die Position des Ziels 
(x2,y2). Lediglich die Startposition des Roboters (x1,y1) ist variabel.

Wie finde ich jetzt den kürzesten Weg von (x1,y1) nach (x2,y2)?

Eine Idee, die mir gerade kommt geht so: Ich definiere eine Anzahl 
zusätzlicher Fixpunkte auf der Fläche, die so angeordnet sind, dass 
jeder Punkt auf der Fläche einen dieser Fixpunkte direkt, d.h. auf 
geradem Weg anfahren kann. Für jeden dieser Fixpunkte gibt es einen fest 
programmierten Weg zum Ziel. Jetzt muss ich nur noch den Fixpunkt 
finden, den ich in gerader Linie erreichen kann und der dem Ziel am 
nächsten liegt.

Den kann ich dann noch optimieren.

Ich habe so die Vermutung, dass wenn ich diese Fixpunkte geschickt wähle 
damit schon den optimalen Weg gefunden habe...

Vieleicht kann man die Fixpunkte auch automatisch festlegen...

Hat noch jemand andere Ideen dazu?

Gruß

Stefan

[toc] | [next] | [standalone]

#201397

Am 2016-02-04 um 17:49 schrieb Stefan:
> Hallo,
>
> vieleicht fehlt mir nur ein Schlüsselwort um was passendes zu finden.
>
> Folgendes Problem:
>
> Ein Roboter befindet sich an der Position (X1,Y1) auf einer Fläche. Er
> soll auf kürzestem Weg die Position (X2,Y2) anfahren.
>
> Problem dabei, es gibt auf dem Weg diverse Hindernisse, also Bereiche,
> die umfahren werden müssen.
>
> Ich stell mir das jetzt so vor, dass ich die Fläche in Kästchen
> aufteile, z.B. 100 Kästchen in X-Richtung und 100 Kästchen in
> Y-Richtung. Jedes Kästchen wird entweder mit 0 oder 1 markiert. Die
> erlaubten Kästen haben den Wert 0, die verbotenen den Wert 1.
>
> Die Position der Hindernisse ist fest, ebenso die Position des Ziels
> (x2,y2). Lediglich die Startposition des Roboters (x1,y1) ist variabel.
>
> Wie finde ich jetzt den kürzesten Weg von (x1,y1) nach (x2,y2)?
>
> Eine Idee, die mir gerade kommt geht so: Ich definiere eine Anzahl
> zusätzlicher Fixpunkte auf der Fläche, die so angeordnet sind, dass
> jeder Punkt auf der Fläche einen dieser Fixpunkte direkt, d.h. auf
> geradem Weg anfahren kann. Für jeden dieser Fixpunkte gibt es einen fest
> programmierten Weg zum Ziel. Jetzt muss ich nur noch den Fixpunkt
> finden, den ich in gerader Linie erreichen kann und der dem Ziel am
> nächsten liegt.
>
> Den kann ich dann noch optimieren.
>
> Ich habe so die Vermutung, dass wenn ich diese Fixpunkte geschickt wähle
> damit schon den optimalen Weg gefunden habe...
>
> Vieleicht kann man die Fixpunkte auch automatisch festlegen...
>
> Hat noch jemand andere Ideen dazu?

Ohne das genau analysiert zu haben. Ich denke dass man dein Problem wie 
das "Problem des Handlungsreisenden" behandeln kann (siehe z.B. 
<https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden>)

Dazu existiert umfassendes wissenschaftliches Material.

Bernd

[toc] | [prev] | [next] | [standalone]

#201405

Am 04.02.2016 um 17:54 schrieb Bernd Nebendahl:
> Am 2016-02-04 um 17:49 schrieb Stefan:
>> Hallo,
>>
>> vieleicht fehlt mir nur ein Schlüsselwort um was passendes zu finden.
>>

>
> Ohne das genau analysiert zu haben. Ich denke dass man dein Problem wie
> das "Problem des Handlungsreisenden" behandeln kann (siehe z.B.
> <https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden>)
>
> Dazu existiert umfassendes wissenschaftliches Material.

Der Begriff ist bekannt, aber das Problem ist ein anderes. Beim 
Handlungsreisenden geht es darum, den kürzesten Weg zu bestimmen, auf 
dem der Handlungsreisende alle Ziele ansteuert. Bei meinem Problem geht 
es nur darum, den kürzesten Weg von einem Startpunkt zu einem Zielpunkt 
zu finden. MaWins Vorschlag passt da schon ganz gut.

Problem dabei ist der hohe Speicherbedarf. Bei einer Fläche von 200x200 
Kästchen komme ich da schon auf 40.000 Speicherstellen. Geht man da von 
16 Bit aus, ist man schon bei 80 kB. Das wäre für meine Anwendung noch 
so halbwegs akzeptabel, geht aber schon an die Grenze...

Gruß

Stefan

[toc] | [prev] | [next] | [standalone]

#201399

"Stefan" <df9bi@arcor.de> schrieb im Newsbeitrag 
news:n8vvfc$nqq$1@news.albasani.net...

> Wie finde ich jetzt den kürzesten Weg von (x1,y1) nach (x2,y2)?

Du füllst alle erlaubten Felder um x1,y1 mit 2
Dann füllst du alle erlaubten um die Felder auf denen 2 steht
mit 3, dann füllst du alle erlaubten um die Felder auf denen
3 steht mit 4 usw. bis du das Feld x2,y2 füllen musst.

Der Algorithmus heisst Lee's maze algorithmus

Den Weg zurück findet man durch Nachbarschaftssuche nach dem
nächstkleineren. Letztlich reichen auch 4 Zahlenwerte (nach 4
kommt wieder 2), dann weisst du aber nicht so schnell, wie weit
es war.
-- 
MaWin, Manfred Winterhoff, mawin at gmx dot net
Homepage http://www.oocities.org/mwinterhoff/
dse-FAQ: http://dse-faq.elektronik-kompendium.de/ 

[toc] | [prev] | [next] | [standalone]

#201401

Am 04.02.2016 um 18:03 schrieb MaWin:
> "Stefan" <df9bi@arcor.de> schrieb im Newsbeitrag
> news:n8vvfc$nqq$1@news.albasani.net...
>
>> Wie finde ich jetzt den kürzesten Weg von (x1,y1) nach (x2,y2)?
>
> Du füllst alle erlaubten Felder um x1,y1 mit 2
> Dann füllst du alle erlaubten um die Felder auf denen 2 steht
> mit 3, dann füllst du alle erlaubten um die Felder auf denen
> 3 steht mit 4 usw. bis du das Feld x2,y2 füllen musst.
>
> Der Algorithmus heisst Lee's maze algorithmus
>
> Den Weg zurück findet man durch Nachbarschaftssuche nach dem
> nächstkleineren. Letztlich reichen auch 4 Zahlenwerte (nach 4
> kommt wieder 2), dann weisst du aber nicht so schnell, wie weit
> es war.

Klingt gut, ich glaube, das ist genau das, wonach ich gesucht habe.

Wobei, ich glaube nicht, dass bei menem Problem die 4 Werte reichen. Das 
wäre nur dann der Fall, wenn es nur einen Weg gibt, also das typische 
Labyrinth. Ich habe aber kein Labyrinth sondern eine Fläche mit 
verbotenen Zonen. Das können auch Inseln sein.

In dem Moment, wo es alternative Wege gibt, kann ich aber nicht 
entscheiden, welches der kürzeste ist wenn ich nur 2 Bit habe.

Ich überlege noch, wie das mit der Diagonalen ist. Wäre es nicht 
eventuell sinnvoller, den Wert der Felder, wo eine der Koordinaten 
gleich bleibt um 2 zu erhöhen und die, wo sich x und y ändern um 3 zu 
erhöhen? Zwei und drei weil 1,5 ungefähr Wurzel aus 2 ist und ich so den 
Diagonalen Weg entsprechend länger bewerte.

Gruß

Stefan

[toc] | [prev] | [next] | [standalone]

#201404

"Stefan" <df9bi@arcor.de> schrieb im Newsbeitrag 
news:n901e1$rqu$1@news.albasani.net...

> Wobei, ich glaube nicht, dass bei menem Problem die 4 Werte reichen. Das 
> wäre nur dann der Fall, wenn es nur einen Weg gibt, also das typische 
> Labyrinth. Ich habe aber kein Labyrinth sondern eine Fläche mit verbotenen 
> Zonen. Das können auch Inseln sein.
> In dem Moment, wo es alternative Wege gibt, kann ich aber nicht 
> entscheiden, welches der kürzeste ist wenn ich nur 2 Bit habe.

Lies einfach mal, wie Lee funktioniert...
Natürlich ergibt der den kürzesten Weg.

> Ich überlege noch, wie das mit der Diagonalen ist. Wäre es nicht eventuell 
> sinnvoller, den Wert der Felder, wo eine der Koordinaten gleich bleibt um 
> 2 zu erhöhen und die, wo sich x und y ändern um 3 zu erhöhen? Zwei und 
> drei weil 1,5 ungefähr Wurzel aus 2 ist und ich so den Diagonalen Weg 
> entsprechend länger bewerte.

Im Prinzip ja. Lee in grundform verwendet city block Metrik.

Wenn Lee erst die orthoganalen Felder mit i+2 und dann die
diagonalen mit i+3 füllt (Bewertung 1.5 statt 1.4141) gibt
es einen leichten Vorzug für Diagonalen. Insgesamt reichen
dann 8 Werte (einschliesslich der 0 für unbelegtes aber noch
erlaubtes Feld)
-- 
MaWin, Manfred Winterhoff, mawin at gmx dot net
Homepage http://www.oocities.org/mwinterhoff/
dse-FAQ: http://dse-faq.elektronik-kompendium.de/

[toc] | [prev] | [next] | [standalone]

#201408

Am 04.02.2016 um 18:36 schrieb MaWin:
> "Stefan" <df9bi@arcor.de> schrieb im Newsbeitrag
> news:n901e1$rqu$1@news.albasani.net...
>
>> Wobei, ich glaube nicht, dass bei menem Problem die 4 Werte reichen.
>> Das wäre nur dann der Fall, wenn es nur einen Weg gibt, also das
>> typische Labyrinth. Ich habe aber kein Labyrinth sondern eine Fläche
>> mit verbotenen Zonen. Das können auch Inseln sein.
>> In dem Moment, wo es alternative Wege gibt, kann ich aber nicht
>> entscheiden, welches der kürzeste ist wenn ich nur 2 Bit habe.
>
> Lies einfach mal, wie Lee funktioniert...

Muss ich mal machen.

[toc] | [prev] | [next] | [standalone]

#201439

MaWin schrieb:
> "Stefan" <df9bi@arcor.de> schrieb im Newsbeitrag 
> news:n8vvfc$nqq$1@news.albasani.net...
> 
>> Wie finde ich jetzt den kürzesten Weg von (x1,y1) nach (x2,y2)?
> 
> Du füllst alle erlaubten Felder um x1,y1 mit 2
> Dann füllst du alle erlaubten um die Felder auf denen 2 steht
> mit 3, dann füllst du alle erlaubten um die Felder auf denen
> 3 steht mit 4 usw. bis du das Feld x2,y2 füllen musst.

Diesen Algorithmus habe ich in einem Layout-Programm für Leiterkarten 
(Autorouter) schon mal verwendet. Nur
> Der Algorithmus heisst Lee's maze algorithmus
das wußte ich noch nicht.

> Den Weg zurück findet man durch Nachbarschaftssuche nach dem
> nächstkleineren. Letztlich reichen auch 4 Zahlenwerte (nach 4
> kommt wieder 2), dann weisst du aber nicht so schnell, wie weit
> es war.

Das Finden des Rückwegs wird etwas knifflig, wenn man den geometrischen 
Abstand statt der Manhatten-Distanz nutzen möchte. Beim Layout ist das 
weniger tragisch, wenn man die Richtung der Leitungen auf 45° oder gar 
90° beschränkt, bei einer freien Bewegung sollte man prüfen, wo 
signifikante Richtungswechsel (um die Ecke eines Hindernisses herum) 
auftauchen, und ob sich auf der direkten Verbindung zwischen zwei 
solchen Punkten Hindernisse befinden, die eine gerade Bahn unmöglich machen.

Eventuell könnte auch ein Verfahren zur Konstruktion einer "konvexen 
Hülle" helfen. Dort könnte man die Punkte mit der größten Abweichung von 
der geraden Verbindung rauswerfen, bis man die schlankste Hülle gefunden 
hat. Dumm nur, wenn die Hindernisse nicht punktförmig sind...

Ein Graph mit gewichteten Kanten könnte auch hilfreich sein. Nur müssen 
dann (wie bei der konvexen Hülle) erst mal alle Tangenten zwischen den 
Objekten berechnet werden, um die Knoten und Kanten insgesamt zu finden. 
Dabei sollte die Größe des Roboters berücksichtigt werden, einmal um die 
Punkte zu finden, an dem der Roboter ein Hindernis gerade mal streift, 
und um andererseits zu enge Passagen auszuschließen, durch die der 
Roboter nicht durchpaßt.


Der Hinweis von Lutz ist auch interessant, wenn man die mögliche 
Beschleunigung und die Zeit für Drehungen des Roboters einbezieht, d.h. 
auf minimale Fahrzeit statt auf minimale Strecke optimiert.

DoDi

[toc] | [prev] | [next] | [standalone]

#201454

Am 04.02.2016 um 18:03 schrieb MaWin:
> "Stefan" <df9bi@arcor.de> schrieb im Newsbeitrag
> news:n8vvfc$nqq$1@news.albasani.net...
>
>> Wie finde ich jetzt den kürzesten Weg von (x1,y1) nach (x2,y2)?
>
> Du füllst alle erlaubten Felder um x1,y1 mit 2
> Dann füllst du alle erlaubten um die Felder auf denen 2 steht
> mit 3, dann füllst du alle erlaubten um die Felder auf denen
> 3 steht mit 4 usw. bis du das Feld x2,y2 füllen musst.
>
> Der Algorithmus heisst Lee's maze algorithmus

Klingt sehr nach Dijkstra.
So habe ich es auch mal gemacht. Nur um hinterher festzustellen, dass es 
das (natürlich) schon gab. ;-)

-- 
Robin Koch

[toc] | [prev] | [next] | [standalone]

#201400

Stefan <df9bi@arcor.de> schrieb:

> Hallo,
> 
> vieleicht fehlt mir nur ein Schlüsselwort um was passendes zu finden.

Das kommt auf das Problem an. Im Prinzip hast Du ein *Labyrinth*. Wenn
es um "realistische" Szenerien geht, wird mit zunehmendem Freiraum und
Wegen bzw. Flächen ohne blockierende Hindernisse der Begriff
aufgeweicht.

> Folgendes Problem:
> 
> Ein Roboter befindet sich an der Position (X1,Y1) auf einer Fläche.
> Er soll auf kürzestem Weg die Position (X2,Y2) anfahren.
> 
> Problem dabei, es gibt auf dem Weg diverse Hindernisse, also
> Bereiche, die umfahren werden müssen.
> 
> Ich stell mir das jetzt so vor, dass ich die Fläche in Kästchen
> aufteile, z.B. 100 Kästchen in X-Richtung und 100 Kästchen in
> Y-Richtung. Jedes Kästchen wird entweder mit 0 oder 1 markiert. Die
> erlaubten Kästen haben den Wert 0, die verbotenen den Wert 1.

Ich nehme mal an, daß der zu befahrende Raum und die Hinderniskarte
bereits vorliegt und die 100 Kästchen einigermaßen problemorientiert
sind, also eine realistische Größe. Es gibt natürlich ca. so viele
Ansätze wie es Gehirne gibt.

- Floodfill, mit jeder Wellenfront eine Bewertung (Färbung) der neu zu
  untersuchenden Rasterpunkte vornehmen mit der Entfernung zum Ziel als
  Hauptkriterium, bewertet mit der zu fahrenden Strecke.

- Die freien Rasterfelder zu einem Graphen verbinden und die bekannten
  Suchalgorithmen (Tiefensuche, Breitensuche, ...) ausprobieren,
  ggf. anpassen.

HTH irgendwie,
Marc

[toc] | [prev] | [next] | [standalone]

#201402

On Thu, 4 Feb 2016 17:49:49 +0100, Stefan <df9bi@arcor.de> wrote:

>Wie finde ich jetzt den kürzesten Weg von (x1,y1) nach (x2,y2)?

z.B.

https://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus


Thomas Prufer

[toc] | [prev] | [next] | [standalone]

#201455

Am 04.02.2016 um 18:23 schrieb Thomas Prufer:
> On Thu, 4 Feb 2016 17:49:49 +0100, Stefan <df9bi@arcor.de> wrote:
>
>> Wie finde ich jetzt den kürzesten Weg von (x1,y1) nach (x2,y2)?
>
> z.B.
>
> https://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus

Negative Gewichte? Ich glaube Dijkstra würde hier reichen.

@OP: Der funktioniert im Prinzip wie Manfred (und andere) ihn 
beschrieben hat. Man füllt vom Ziel aus die freien Felder des Rasters 
sukzessive mit aufsteigenden Zahlen bis man am Start angekommen ist.
Dann geht man einfach einen Pfad absteigender Zahlen entlang zum Ziel.

.....Z
..#...
..#...
...#..
#.....
S.....

54321Z
65#321
76#432
878#43
#87654
S98765

Optimieren kann man indem man die Zahl der Richtungsänderungen minimiert 
oder ggfls. Diagonalschritte zulässt.

-- 
Robin Koch

[toc] | [prev] | [next] | [standalone]

#201407

Am Thu, 4 Feb 2016 17:49:49 +0100 schrieb Stefan:

> Hallo,
> 
> vieleicht fehlt mir nur ein Schlüsselwort um was passendes zu finden.
> 
> Folgendes Problem:
> 
> Ein Roboter befindet sich an der Position (X1,Y1) auf einer Fläche. Er 
> soll auf kürzestem Weg die Position (X2,Y2) anfahren.
> 
> Problem dabei, es gibt auf dem Weg diverse Hindernisse, also Bereiche, 
> die umfahren werden müssen.
> 
> Ich stell mir das jetzt so vor, dass ich die Fläche in Kästchen 
> aufteile, z.B. 100 Kästchen in X-Richtung und 100 Kästchen in 
> Y-Richtung. Jedes Kästchen wird entweder mit 0 oder 1 markiert. Die 
> erlaubten Kästen haben den Wert 0, die verbotenen den Wert 1.
> 
> Die Position der Hindernisse ist fest, ebenso die Position des Ziels 
> (x2,y2). Lediglich die Startposition des Roboters (x1,y1) ist variabel.
> 
> Wie finde ich jetzt den kürzesten Weg von (x1,y1) nach (x2,y2)?

Der kürzeste Weg muss nicht der beste sein. Als ich vor ca. 30 Jahren mal
was über Industrieroboter lernte hatten die für so etwas Feinpunkte, die
dann letztendlich mit hoher Genauigkeit angefahren wurden, und Grobpunkte,
die mit einer tolerierten Ungenauigkeit dazwischen nur ungefähr
überschliffen werden mussten. Das diente einfach dazu dass die Bewegung in
der Summe am schnellsten war.

Vorgegeben wurden die Zwischenpunkte damals allerdings von Hand, so weit war
die Rechentechnik dann doch nicht.

Lutz

-- 
Mit unseren Sensoren ist der Administrator informiert, bevor es Probleme im 
Serverraum gibt: preiswerte Monitoring Hard- und Software-kostenloses Plugin 
auch für Nagios - Nachricht per e-mail,SMS und SNMP: http://www.messpc.de
Messwerte nachträgliche Wärmedämmung http://www.messpc.de/waermedaemmung.php

[toc] | [prev] | [next] | [standalone]

#201462

Am 04.02.2016 um 18:59 schrieb Lutz Schulze:
> Am Thu, 4 Feb 2016 17:49:49 +0100 schrieb Stefan:
>
>> Hallo,
>>
>> vieleicht fehlt mir nur ein Schlüsselwort um was passendes zu finden.
>>
>> Folgendes Problem:
>>
>> Ein Roboter befindet sich an der Position (X1,Y1) auf einer Fläche. Er
>> soll auf kürzestem Weg die Position (X2,Y2) anfahren.
>>
>> Problem dabei, es gibt auf dem Weg diverse Hindernisse, also Bereiche,
>> die umfahren werden müssen.
>>
>> Ich stell mir das jetzt so vor, dass ich die Fläche in Kästchen
>> aufteile, z.B. 100 Kästchen in X-Richtung und 100 Kästchen in
>> Y-Richtung. Jedes Kästchen wird entweder mit 0 oder 1 markiert. Die
>> erlaubten Kästen haben den Wert 0, die verbotenen den Wert 1.
>>
>> Die Position der Hindernisse ist fest, ebenso die Position des Ziels
>> (x2,y2). Lediglich die Startposition des Roboters (x1,y1) ist variabel.
>>
>> Wie finde ich jetzt den kürzesten Weg von (x1,y1) nach (x2,y2)?
>
> Der kürzeste Weg muss nicht der beste sein. Als ich vor ca. 30 Jahren mal
> was über Industrieroboter lernte hatten die für so etwas Feinpunkte, die
> dann letztendlich mit hoher Genauigkeit angefahren wurden, und Grobpunkte,
> die mit einer tolerierten Ungenauigkeit dazwischen nur ungefähr
> überschliffen werden mussten. Das diente einfach dazu dass die Bewegung in
> der Summe am schnellsten war.

Das ist bei meiner Anwendung nicht das Problem. Es geht mit jetzt auch 
nicht um die mathematisch beste Lösung.

Mit meinen Überlegungen bin ich jetzt wieder bei meiner Anfangsidee mit 
den Fixpunkten und zwar wegen dem Speicherbedarf und der programmierung 
der Fläche bzw. dem Anlernen des Roboters.

Deshalb überlege ich momentan, die Fixpunkte manuell zu erfassen, d.h. 
mit dem Roboter die Punkte anzufahren, Position speichern und fertig.

Ich denke mal, ich komme mit maximal 20 Fixpunkten aus. Da ist der 
Speicherbedarf doch um einiges geringer als bei einem Raster von 100x100 
bzw. 200x200 Rasterpunkten.

Gruß

Stefan

[toc] | [prev] | [next] | [standalone]

#201484

Stefan schrieb:

> Mit meinen Überlegungen bin ich jetzt wieder bei meiner Anfangsidee mit den Fixpunkten und zwar wegen dem Speicherbedarf und der 
> programmierung der Fläche bzw. dem Anlernen des Roboters.
>
> Deshalb überlege ich momentan, die Fixpunkte manuell zu erfassen, d.h. mit dem Roboter die Punkte anzufahren, Position speichern 
> und fertig.

Wäre es dann nicht einfacher, statt der verbotenen Positionen die erlaubte
Route zu definieren?
Oder sind Start- und Endpunkt dynamisch und der Roboter muss dasselbe
Grid an verbotenen Punkten mehrfach mit unterschiedlichen Routen durchlaufen?


Gruß Christian 

[toc] | [prev] | [next] | [standalone]

#201486

Am 05.02.2016 um 16:11 schrieb Christian Müller:
> Stefan schrieb:
>
>> Mit meinen Überlegungen bin ich jetzt wieder bei meiner Anfangsidee
>> mit den Fixpunkten und zwar wegen dem Speicherbedarf und der
>> programmierung der Fläche bzw. dem Anlernen des Roboters.
>>
>> Deshalb überlege ich momentan, die Fixpunkte manuell zu erfassen, d.h.
>> mit dem Roboter die Punkte anzufahren, Position speichern und fertig.
>
> Wäre es dann nicht einfacher, statt der verbotenen Positionen die erlaubte
> Route zu definieren?
> Oder sind Start- und Endpunkt dynamisch und der Roboter muss dasselbe
> Grid an verbotenen Punkten mehrfach mit unterschiedlichen Routen
> durchlaufen?
>
>
> Gruß Christian

Das Ziel ist immer dasselbe. Der Startpunkt verschiebt sich.

Das mit den Fixpunkten ist im Prinzip eine Beschreibung der erlaubten Route.

Jeder Fixpunkt hat eine Position und eine Entfernung zum Ziel. Ich muss 
jetzt nur noch einen Fixpunkt finden, den ich auf gerader Linie anfahren 
kann. Habe ich mehrere Fixpunkte zur Auswahl, nehme ich den Fixpunkt, 
der dem Ziel am nächsten ist. während ich zu diesem Fixpunkt fahre prüfe 
ich, ob es einen anderen Fixpunkt gibt, der in direkter Linie angefahren 
werden kann und näher am Ziel liegt. Wenn ich einen solchen Fixpunkt 
finde, bewege ich mich dorthin.

Ich benötige dazu eine Beschreibung der Außenkontur meiner Fläche und 
eventuell vorhandener Inseln und die besagten Fixpunkte. Für meine 
Anwendung bedeutet das, dass ich dann statt 10.000 Feldern nur noch ca. 
20-100 Punkte für die Außenkontur und 5-10 Fixpunkte habe. Die Fixpunkte 
lege ich nach Gefühl fest, vermutlich lassen sich diese auch anhand der 
Außenkontur automatisch festlegen.

Da das Problem von einem Microcontroller gelöst werden soll, macht es 
schon einen Unterschied, ob ich 10.000 Felder oder 100 Punkte verwalten 
muss.

Gruß

Stefan

[toc] | [prev] | [next] | [standalone]

#201468

Am 04.02.2016 um 17:49 schrieb Stefan:
> Hallo,
>
> vieleicht fehlt mir nur ein Schlüsselwort um was passendes zu finden.
>
> Folgendes Problem:
>
> Ein Roboter befindet sich an der Position (X1,Y1) auf einer Fläche. Er
> soll auf kürzestem Weg die Position (X2,Y2) anfahren.
>
> Problem dabei, es gibt auf dem Weg diverse Hindernisse, also Bereiche,
> die umfahren werden müssen.
>
> Ich stell mir das jetzt so vor, dass ich die Fläche in Kästchen
> aufteile, z.B. 100 Kästchen in X-Richtung und 100 Kästchen in
> Y-Richtung. Jedes Kästchen wird entweder mit 0 oder 1 markiert. Die
> erlaubten Kästen haben den Wert 0, die verbotenen den Wert 1.
>
> Die Position der Hindernisse ist fest, ebenso die Position des Ziels
> (x2,y2). Lediglich die Startposition des Roboters (x1,y1) ist variabel.
>
> Wie finde ich jetzt den kürzesten Weg von (x1,y1) nach (x2,y2)?
>
> Eine Idee, die mir gerade kommt geht so: Ich definiere eine Anzahl
> zusätzlicher Fixpunkte auf der Fläche, die so angeordnet sind, dass
> jeder Punkt auf der Fläche einen dieser Fixpunkte direkt, d.h. auf
> geradem Weg anfahren kann. Für jeden dieser Fixpunkte gibt es einen fest
> programmierten Weg zum Ziel. Jetzt muss ich nur noch den Fixpunkt
> finden, den ich in gerader Linie erreichen kann und der dem Ziel am
> nächsten liegt.
>
> Den kann ich dann noch optimieren.
>
> Ich habe so die Vermutung, dass wenn ich diese Fixpunkte geschickt wähle
> damit schon den optimalen Weg gefunden habe...
>
> Vieleicht kann man die Fixpunkte auch automatisch festlegen...
>
> Hat noch jemand andere Ideen dazu?

Such mal nach Uniform Cost Search Algorithmus.

Grüße

Eric.


-- 
www.headless-brewing.com

[toc] | [prev] | [next] | [standalone]

#202156

Am 04.02.2016 17:49, schrieb Stefan:
> Hallo,
>
> vieleicht fehlt mir nur ein Schlüsselwort um was passendes zu finden.
>
> Folgendes Problem:
>
> Ein Roboter befindet sich an der Position (X1,Y1) auf einer Fläche. Er
> soll auf kürzestem Weg die Position (X2,Y2) anfahren.
>
> Problem dabei, es gibt auf dem Weg diverse Hindernisse, also Bereiche,
> die umfahren werden müssen.
>
> Ich stell mir das jetzt so vor, dass ich die Fläche in Kästchen
> aufteile, z.B. 100 Kästchen in X-Richtung und 100 Kästchen in
> Y-Richtung. Jedes Kästchen wird entweder mit 0 oder 1 markiert. Die
> erlaubten Kästen haben den Wert 0, die verbotenen den Wert 1.
>
> Die Position der Hindernisse ist fest, ebenso die Position des Ziels
> (x2,y2). Lediglich die Startposition des Roboters (x1,y1) ist variabel.
>
> Wie finde ich jetzt den kürzesten Weg von (x1,y1) nach (x2,y2)?
>
> Eine Idee, die mir gerade kommt geht so: Ich definiere eine Anzahl
> zusätzlicher Fixpunkte auf der Fläche, die so angeordnet sind, dass
> jeder Punkt auf der Fläche einen dieser Fixpunkte direkt, d.h. auf
> geradem Weg anfahren kann. Für jeden dieser Fixpunkte gibt es einen fest
> programmierten Weg zum Ziel. Jetzt muss ich nur noch den Fixpunkt
> finden, den ich in gerader Linie erreichen kann und der dem Ziel am
> nächsten liegt.
>
> Den kann ich dann noch optimieren.
>
> Ich habe so die Vermutung, dass wenn ich diese Fixpunkte geschickt wähle
> damit schon den optimalen Weg gefunden habe...
>
> Vieleicht kann man die Fixpunkte auch automatisch festlegen...
>
> Hat noch jemand andere Ideen dazu?
>
Meiner Ansicht nach beziehen sich die bisherigen Vorschläge auf sowas 
wie das 'travelling sales man Problem'. Das ist die Frage nach der 
Reihenfolge, in der zu besuchende Punkte angefahren werden sollen.

Du suchst aber nach der kürzesten Strecke, die der Roboter von A (x1,y1) 
nach Punkt B (x2, y2) auf einer Ebene fahren soll, ohne gegen 
Hindernisse zu stoßen.

Ich nehme nun den einfachsten Fall und es gibt genau ein Hindernis. Der 
weg von A nach B auf einer Geraden durch beide Punkte wäre der kürzeste, 
sollte dort kein Hindernis sein.

Ist dort aber eines, dann muß der Roboter ausweichen und zwar zu der 
Seite, wo er weniger von dieser Geraden abweichen muß. Er muß dann 
soweit ausweichen, daß er an dem Hindernis gerade vorbeikommt.

Jetzt kann man diesen Punkt bestimmen ( C an (x3, y3)  ) und die Strecke 
in zwei Teile Teilen und das ganze wiederholen für A->C und C->B.

Das macht man dann solange, bis kein Hindernis mehr auf dem Fahrweg ist.


TH

[toc] | [prev] | [next] | [standalone]

#202163

Am 14.02.2016 um 18:53 schrieb Thomas Heger:
> Am 04.02.2016 17:49, schrieb Stefan:
>> Hallo,
>>
>> vieleicht fehlt mir nur ein Schlüsselwort um was passendes zu finden.
>>
>> Folgendes Problem:
>>
>> Ein Roboter befindet sich an der Position (X1,Y1) auf einer Fläche. Er
>> soll auf kürzestem Weg die Position (X2,Y2) anfahren.

> Meiner Ansicht nach beziehen sich die bisherigen Vorschläge auf sowas
> wie das 'travelling sales man Problem'. Das ist die Frage nach der
> Reihenfolge, in der zu besuchende Punkte angefahren werden sollen.

Nein, das war nur einer der Vorschläge. Die anderen beschrieben schon 
die gesuchten Lösungen. Die Flutungsverfahren haben nur den Nachteil, 
dass dafür relativ viel Speicher benötigt wird.

> Du suchst aber nach der kürzesten Strecke, die der Roboter von A (x1,y1)
> nach Punkt B (x2, y2) auf einer Ebene fahren soll, ohne gegen
> Hindernisse zu stoßen.

Richtig

> Ich nehme nun den einfachsten Fall und es gibt genau ein Hindernis. Der
> weg von A nach B auf einer Geraden durch beide Punkte wäre der kürzeste,
> sollte dort kein Hindernis sein.

Auch richtig.

> Ist dort aber eines, dann muß der Roboter ausweichen und zwar zu der
> Seite, wo er weniger von dieser Geraden abweichen muß. Er muß dann
> soweit ausweichen, daß er an dem Hindernis gerade vorbeikommt.

> Jetzt kann man diesen Punkt bestimmen ( C an (x3, y3)  ) und die Strecke
> in zwei Teile Teilen und das ganze wiederholen für A->C und C->B.

Richtig, aber du kannst so die Stelle C nicht eindeutig bestimmen.

> Das macht man dann solange, bis kein Hindernis mehr auf dem Fahrweg ist.

Ist im Prinzip korrekt.

Mein Lösungsansatz sieht folgendermaßen aus:

Ich habe eine Anzahl von Geradenstücken, die jeweils durch 2 Punkte 
beschrieben werden, also (x1,y1) und (x2,y2). Die Geradenstücke bilden 
die Außenlinie, d.h. den Umriss der Fläche und die Umrisse der 
Hindernisse ab. Wenn zwei Linien miteinander verbundene sind, stimmt 
einer der beiden Punkte überein. Kreuzungen gibt es nicht, wobei das ist 
glaube ich egal.

Ich habe jetzt zwei Array, einmal die Liste der Geraden und eine Liste 
der Punkte.

Die Punkte ergeben sich aus den Koordinaten der Geraden, wobei 
Doubletten eliminiert werden.

Jeder Punkt hat 3 Parameter, x,y und die Distanz zum Ziel. Die Punkte 
und Geraden sind bekannt.

Die Distanzen sind zunächst unbekannt.

Jetzt teste ich jeden Punkt darauf, ob ich eine gerade Linie zwischen 
diesem Punkt P und dem Ziel Z ziehen kann. Es darf also keine Kreuzung 
mit einer Linie geben. Bei jedem Punkt wo das gegeben ist, trage ich die 
Länge der Geraden von diesem Punkt zum Ziel ein.

Anschließend teste ich die Punkte mit unbekannter Distanz darauf, ob ich 
eine Linie zu dem Punkt Px der die geringsten bekannten Distanz zu Z hat 
ziehen kann. Ist das gegeben, trage ich bei diesem Punkt dessen Distanz 
zu Z ein. Das ist die Summe aus der Distanz zwischen diesem Punkt P und 
Px und der bei Px eingetragenen Distanz zu Z ein.

Das wiederhole ich mit dem Punkt der die 2. kleinste bekannte Distanz zu 
Z hat, usw. Das wiederhole ich solange, bis die Distanz aller Punkte zu 
Z bekannt ist.

Das muss ich einmal machen und speichern. Die Berechnung muss auch nicht 
auf dem Roboter ausgeführt werden, z.B. auf einem PC auf dem der 
Lageplan erstellt wird.

Wenn der Roboter jetzt den kürzesten Weg von einem beliebigen Punkt 
(x,y) zum Ziel sucht, berechnet er für jeden Punkt Px den er von P aus 
direkt anfahren kann die Summe aus der Distanz von Px zu P und der 
Distanz von P zu Z. Dann fährt der Roboter den Punkt an, für den sich 
die kürzeste Summe ergibt.

Während der Fahrt kann er die Rechnung ständig wiederholen und so unter 
Umständen die Richtung ängdern. Momentan gehe ich aber davon aus, dass 
das nichts bringt.

Jedenfalls wenn ich den Punkt Px erreicht habe, suche ich wieder den 
direkt erreichbaren Punkt mit der geringsten Distanz zum Ziel usw. bis 
ich das Ziel erreicht habe, wobei Z einer der Punkte ist, d.h. wenn ich 
Z "sehen" kann, fahre ich direkt darauf zu.

Diese Lösung hat den Vorteil, dass ich wesentlich weniger 
Speicherstellen benötige als bei den Flutungsmethoden.

Gruß

Stefan

[toc] | [prev] | [next] | [standalone]

#202182

Am 14.02.2016 20:04, schrieb Stefan:

>> Du suchst aber nach der kürzesten Strecke, die der Roboter von A (x1,y1)
>> nach Punkt B (x2, y2) auf einer Ebene fahren soll, ohne gegen
>> Hindernisse zu stoßen.
>
> Richtig
>
>> Ich nehme nun den einfachsten Fall und es gibt genau ein Hindernis. Der
>> weg von A nach B auf einer Geraden durch beide Punkte wäre der kürzeste,
>> sollte dort kein Hindernis sein.
>
> Auch richtig.
>
>> Ist dort aber eines, dann muß der Roboter ausweichen und zwar zu der
>> Seite, wo er weniger von dieser Geraden abweichen muß. Er muß dann
>> soweit ausweichen, daß er an dem Hindernis gerade vorbeikommt.
>
>> Jetzt kann man diesen Punkt bestimmen ( C an (x3, y3) ) und die Strecke
>> in zwei Teile Teilen und das ganze wiederholen für A->C und C->B.
>
> Richtig, aber du kannst so die Stelle C nicht eindeutig bestimmen.

Mir ist nicht ganz klar, wie der Roboter die Hindernisse erkennen soll. 
Wenn der Roboter eine Art digitaler Karte gespeichert hat, dann soll der 
Algorithmus den Weg in dieser Karte finden?

Andere Variante: der Roboter soll den Weg 'in echt' auf sowas wie einem 
großen Brett finden, wozu er Sensoren (Kameras o. ä.) besitzt.

Im ersten Fall braucht man ein Programm, welches einen möglichst kurzen 
Weg in den ansonsten bekannten Daten findet.

Im zweiten Fall weiß man nicht, ob der gewählte Weg überhaupt möglich 
ist. Denkbar wäre nämlich ein Labyrinth oder so schmale Wege, daß der 
Roboter zwischen den Hindernissen stecken bleibt.

Ich gehe also von folgenden Annahmen aus (für Fall zwei):

die Hindernisse sollen (angenähert) kreisförmig sein und nie näher 
zusammen stehen als der Roboter breit ist.

der Roboter hat keine vollständige Karte

der Roboter kann außer den Konturen der Hindernisse nur das Hindernis 
sehen, das nicht von anderen verdeckt ist.

der Roboter weiß immer, in welcher Richtung er fährt und wo er ist

er weiß, wo das Ziel ist und in welcher Richtung

dann kann der Roboter den Mittelpunkt eines Hindernisses erkennen und 
dessen Ausdehnung.


Daraus kann der Roboter die Umrisslinie berechnen und die halbe eigne 
Breite (plus den minimalen Seitenabstand) hinzu addieren und so den 
gesuchten Punkt C berechnen.

Dann fährt er dort hin und macht das gleiche noch mal von dort.

TH

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | de.sci.electronics

csiph-web