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 2 of 2 — ← Prev page 1 [2]

#202264

Am 15.02.2016 um 05:13 schrieb Thomas Heger:
> 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?

Im ersten Schritt soll hat er nur eine digitale Karte. Wie man auf 
unbekannte Hindernisse reagiert ist noch nicht geklärt.

> 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.

Richtig.

> 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.

Richtig. Da muss sicher gestellt sein, dass solche Wege nicht vorkommen.

> 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.

Die Form der Hindernisse ist egal, es ist sogar wahrscheinlich, dass 
diese rechteckig sind. Aber es ist richtig, dass sie nie näher zusammen 
stehen dürfen, als der Roboter breit ist. Dazu könnte der Algorithmus 
zunächst virtuelle Linien einfügen, also eng nebeneinder liegende Linien 
bzw. Punkte mit zusätzlichen Linien verbinden.

> 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.

Der Punkt C liegt an einer Kante. Ich stell mir das so vor, dass ich 
zunächst die Karte aufnehme indem der Roboter das Labyrinth abfährt. Das 
macht er nicht autark sondern per Fernsteuerung. Damit ist dann auch 
gleich sicher gestellt, dass der Roboter überall durch kommt.

Damit habe ich dann auch gleich den Fahrweg an einer gedachen Linie, 
deren Abstand von den Hindernissen der halben Breite des Roboters 
entspricht. Ich kann dann die Breite des Roboters als 0 annehmen. Die 
anzufahrenden Punkte befinden sich dann nicht auf der tatsächlichen 
Außenkontur sondern auf einer Linie im Abstand der halben Roboterbreite 
zur echten Außenkontur bzw. den Hindernissen. Damit werden dann 
automatisch Bereiche, die zu eng sind gesperrt.

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

Richtig



> TH

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

#202226

Thomas Heger schrieb:

> 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.

Was mich zu der Frage führt, ob bei Deinem Vorschlag sichergestellt ist, 
daß für eine optimale Lösung jeder Schritt optimal sein muß.

IMO ist nicht absehbar, ob ein Weg mit einmaligem Abknicken mit größerer 
Abweichung nicht kürzer ist als einer, der nach dem ersten (optimalen) 
Schritt öfters abknickt. Jetzt mal ganz abgesehen von den Kosten für 
jeden Richtungswechsel, aber unter Beachtung der Abstände, die das 
Fahrzeug von jedem Hindernis einhalten muß.


Ich weiß nicht, ob das irgendwie zum konkreten Fall paßt, aber ein Blick 
auf "Roman Chariots" könnte eventuell hilfreich sein.

DoDi

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web