ďťż
Przejrzyj wiadomości
aaaaAlgorytm wychodzenia z labiryntuaaaa



kots - 17-06-2007 01:20
Algorytm wychodzenia z labiryntu
  Witam

Czy zetknal kto sie moze z TAKIM schematem blokowym algorytmu wychodznie
z labiryntu.
A mianowice
Mamy do dyspozycji azymut ktory nakierowuje nasz na wyjscie, sciany moga
byc dowolne, pod wolonymi katami, dowolne petlne, duze puste
przestrzenie itp. (taka jaskinia). Dysponujemy tylko czyjnikiem
zblizzenia do sciany (mozemy sprawdzic czy przed nami jest sciana).
Wszelkie obroty wykonujemy w stopniach o 360 o 180 itp.
Moze ktos ma takowe rozwiazanie to bylbym wdzieczy.

pozdrawiam




Kopia Nowy folder (4) - 17-06-2007 01:20

  Chyba najprostszym sposobem byloby stworzenie algorytmu sledzenia np.
prawej (lub lewej- ale ustalone na stale) sciany- jesli bedzie sie
poruszal ciagle przy prawej scianie to na pewno wyjdzie z labiryntu.

Musi tylko co pewien czas sprawdzac, czy ciagle znajduje sie przy
scianie. Jesli nie- skreca w prawo, dochodzi do sciany, skreca w lewo i
idzie dalej.

pozdr.
--
Guru,
hohohoho
hihihihihihihi :) :) :) :) :)
<ROTFL2> :* :))




kots - 17-06-2007 01:20

  Kopia Nowy folder (4) pisze:
> Chyba najprostszym sposobem byloby stworzenie algorytmu sledzenia np.
> prawej (lub lewej- ale ustalone na stale) sciany- jesli bedzie sie
> poruszal ciagle przy prawej scianie to na pewno wyjdzie z labiryntu.
>
> Musi tylko co pewien czas sprawdzac, czy ciagle znajduje sie przy
> scianie. Jesli nie- skreca w prawo, dochodzi do sciany, skreca w lewo i
> idzie dalej.
>
Wlasnie nie jest tak latwo - podana przez ciebie metoda to mozna sobie z
prostego labityntu wyjsc gdzie sa proste sciany, jak masz juz jakas
jaskinie a po sordku okragly filar, a ruszysz z miejsca przy filarze to
bedzie, pozniej jakies petle to bedziesz sie krecil. Dlatego konieczne
jest tu wykorzystanie azymmutu (zakladajac ze nie mozly zapmaietywac
drogi przebytej)




slomek - 18-06-2007 00:02

  On 16 Cze, 09:46, kots <k...@gmail.com> wrote:
> Witam
>
> Czy zetknal kto sie moze z TAKIM schematem blokowym algorytmu wychodznie
> z labiryntu.
> A mianowice
> Mamy do dyspozycji azymut ktory nakierowuje nasz na wyjscie, sciany moga
> byc dowolne, pod wolonymi katami, dowolne petlne, duze puste
> przestrzenie itp. (taka jaskinia). Dysponujemy tylko czyjnikiem
> zblizzenia do sciany (mozemy sprawdzic czy przed nami jest sciana).
> Wszelkie obroty wykonujemy w stopniach o 360 o 180 itp.
> Moze ktos ma takowe rozwiazanie to bylbym wdzieczy.
>
> pozdrawiam

Metoda potencjalowa. Brakuje co prawda odleglosci od celu, ale moze
udaloby sie jakos to obejsc (moze stala sila...).
Ogolnie- powinno byc troche na sieci na ten temat. W skrocie: robot
jest ladunkiem +, sciany sa ladunkiem +, wyjscie jest ladunkiem -.
CZyli wyjscie przyciaga robota, sciany odpychaja. Algorytm bylbyu mw
taki:
-rozgladasz sie w kolko z pewnym skokiem (np co 18stopni) mierzac
odleglosc od scian w kazdym kierunku
-pod uwage bierzesz tylko odleglosci ponizej jakiegos progu (zeby sie
pierdolami nie zajmowac)
-obliczasz sily dzialajace na robota ze strony scian (im blizej, tym
wieksza-konkretnych wzorow poszukaj albo wymysl...)
-obliczasz sile oddzialywania wyjscia na robota (jak wyzej)
-obliczasz sile wypadkowa
-na podstawie sily wypadkowej podejmujesz ruch: masz wyliczony
kierunek i zwrot, a wartosc sily wplywa na odleglosc/czas ruchu w
danym kroku
-rozgladasz sie w kolo...
i tak w kolko

Ten algorytm tez moze sie zakleszczyc (w zwezajacych sie tunelach),
ale lepszego raczej nie znajdziesz. Moga byc pewne modyfikacje
uodparniajace go na takie sytuacje- moze Google dopomoze. ;)




Jakub Debski - 18-06-2007 00:02

  > Moze ktos ma takowe rozwiazanie to bylbym wdzieczy.

Czy to co?, co projektujesz jest maszyn? stanow?? Je?eli tak, jak?
pami?ci? dysponuje?

pozdrawiam
Jakub




kots - 19-06-2007 00:06

  slomek pisze:

>
> Metoda potencjalowa. Brakuje co prawda odleglosci od celu, ale moze
> udaloby sie jakos to obejsc (moze stala sila...).
> Ogolnie- powinno byc troche na sieci na ten temat. W skrocie: robot
> jest ladunkiem +, sciany sa ladunkiem +, wyjscie jest ladunkiem -.
> CZyli wyjscie przyciaga robota, sciany odpychaja. Algorytm bylbyu mw
> taki:
>[cut]
Nie dysponuje takimi czujnikami zeby byla możliwa taka implemetnacja jak
twoja.
Jes tylko JEDEN czujnik ktory oresla czy przed toba jest sciana czy tez
nie (wyciagnieta reka do przodu) + czujnik ktory ZAWSZE moze mnie
ustawic na wyjscie (azymut).
Ale twoja propozycja jest ciekawa, jednak wymagala by conajmniej
czujnika odleglosci.




slomek - 19-06-2007 00:06

  On 18 Cze, 17:02, kots <k...@gmail.com> wrote:

>Dysponujemy tylko czyjnikiem zblizzenia do sciany

To zabrzmia o jak "czujnik zbli eniowy"
W takiej sytuacji to poza trzymaniem sielewej/prawej ciany wiele nie
wskórasz.
Mo e co na wzór metody grafu widzialno ci: jedziesz prosto na cel az
napotkasz sciane. Wtedy jedziesz przy scianie(zawsze w lewa/prawa
strone) do momentu, az bedziesz mogl znowu pojechac prosto na cel. To
chyba idealne rozwiazanie nie jest, ale ma pewien sens...




kots - 19-06-2007 00:06

  slomek pisze:
> On 18 Cze, 17:02, kots <k...@gmail.com> wrote:
>
Wtedy jedziesz przy scianie(zawsze w lewa/prawa
> strone) do momentu, az bedziesz mogl znowu pojechac prosto na cel. To
> chyba idealne rozwiazanie nie jest, ale ma pewien sens...
>

Przy prostym labiryncie to jest metoda....Ale w dowolnie "zakreconym" to
juz sie nie sprawdza dlatego jest azymut... Tylko ze nie znam w pelni
funncjonalnego chocby schematu blokowego...A napewno mozna to zrobic i
na 95% trzeba wykorzystac azymut bo inaczej bediemy sie zapetlac.




Marcin Biegan - 20-06-2007 00:04

  kots napisał(a):
> slomek pisze:
>> On 18 Cze, 17:02, kots <k...@gmail.com> wrote:
>>
> Wtedy jedziesz przy scianie(zawsze w lewa/prawa
>> strone) do momentu, az bedziesz mogl znowu pojechac prosto na cel. To
>> chyba idealne rozwiazanie nie jest, ale ma pewien sens...
>>
> Przy prostym labiryncie to jest metoda....Ale w dowolnie "zakreconym" to
> juz sie nie sprawdza dlatego jest azymut... Tylko ze nie znam w pelni
> funncjonalnego chocby schematu blokowego...A napewno mozna to zrobic i
> na 95% trzeba wykorzystac azymut bo inaczej bediemy sie zapetlac.

http://en.wikipedia.org/wiki/A*_search_algorithm
Ale brzmisz, jakbyś miał pojedynczego robota, czy coś w tym stylu, więc raczej
A* nie będzie pasować.

--
pozdrawiam
Marcin Biegan




kots - 20-06-2007 00:04

  Marcin Biegan pisze:

> Ale brzmisz, jakbyś miał pojedynczego robota, czy coś w tym stylu, więc
> raczej A* nie będzie pasować.

Dokladnie jest tak jak piszesz :) - ale bydle jest bardzo oporne, i nie
moge znalezc skutecznego algorytmu.




Radoslaw Jocz - 20-06-2007 00:04

  kots wrote:
> Witam
>
> Czy zetknal kto sie moze z TAKIM schematem blokowym algorytmu wychodznie
> z labiryntu.
> A mianowice
> Mamy do dyspozycji azymut ktory nakierowuje nasz na wyjscie, sciany moga
> byc dowolne, pod wolonymi katami, dowolne petlne, duze puste
> przestrzenie itp. (taka jaskinia). Dysponujemy tylko czyjnikiem
> zblizzenia do sciany (mozemy sprawdzic czy przed nami jest sciana).
> Wszelkie obroty wykonujemy w stopniach o 360 o 180 itp.
> Moze ktos ma takowe rozwiazanie to bylbym wdzieczy.
>
> pozdrawiam

z pewnoscia musisz rozwazyc kilka typow algorytmow wychodzenia z
labirytnu (i inne alborytmy) a im wiecej tym lepiej i wybrac odpowiedni
dla swoich zalozen, ewentualnie zmodyfikowac jeden z nich, lub
wykorzystac wiecej niz jeden na raz, (lub zmodyfikowac wlasne zalozenia
w najgorszym przypadku)

dosc latwe w implementacji z ktorymi sie spotkalem:
- algoryzm wychodzenia z labirytnu z nawrotami, wykorzystuje pamiec
przegadajac kolejne wezly grafu reprezentujacym labirynt i zapamietujac
gdzie juz byl

- ponumerowanie pol (drogi wyjscia z labirytntu labirynt w postaci
planszy) od wyjscia rosnaco do obiektu ktory ma z niego wyjsc,
obiekt poprostu bedzie wchodzil na kolejne pola o nizszym numerze
przesuwajac sie coraz blizej wyjscia
ponumerowane pola beda czyms w rodzaju drzewa a wyjscie to korzen,
obiekt znajduje sie na lisciu wiec musi tylk przejsc do korzenia co jest
banalne, wyznaczenie drzewa tez jest latwe

linki
http://www.ii.uni.wroc.pl/~wzychla/maze.html
http://www.google.com/search?hl=en&r...birynt&spell=1




Kamil Burzynski - 20-06-2007 00:04

  On Sat, 16 Jun 2007 09:46:03 +0200
kots <kots@gmail.com> wrote:

> Witam
>
> Czy zetknal kto sie moze z TAKIM schematem blokowym algorytmu wychodznie
> z labiryntu.
> A mianowice
> Mamy do dyspozycji azymut ktory nakierowuje nasz na wyjscie, sciany moga
> byc dowolne, pod wolonymi katami, dowolne petlne, duze puste
> przestrzenie itp. (taka jaskinia). Dysponujemy tylko czyjnikiem
> zblizzenia do sciany (mozemy sprawdzic czy przed nami jest sciana).
> Wszelkie obroty wykonujemy w stopniach o 360 o 180 itp.
> Moze ktos ma takowe rozwiazanie to bylbym wdzieczy.

Nie opisales jak porusza sie robot. Pojedynczy krok robota jest liczba
calkowita, czy tez wartosci rzeczywiste tez wchodza w gre? Teoretycznie
gdy sciany sa nieskonczenie blisko siebie - robot przejdzie czy nie?
Czy tez sciany nie sa az tak dowolne - bo maja jakies ograniczenia na
pozycje/katy? Obracasz sie zawsze w pelnych katach czy tez w ulamkach?

Ogolnie jest tak ze jak masz azymut, to mierzac kat z 2 roznych
pozycji, znajac odleglosc miedzy pozycjami jestes w stanie dokladnie
wyliczyc gdzie i w jakiej odleglosci jest wyjscie. Potem trzeba
tylko narysowac mape :)

Czujnik odleglosci od sciany mozesz zasymulowac (w
dosc nieoptymalny sposob) - poruszasz sie do przodu (pamietajac o ile
sie poruszyles) az trafisz na sciane, wtedy cofasz sie o tyle ile sie
poruszyles. Obracasz sie o kat delta, i znowu ruch w przod, tyl. W ten
sposob zbadasz odleglosc scian dookola. Stad algorytmy opisane w innych
postach w tym watku beda mialy wieksza szanse zadzialania.

--
Best regards from
Kamil Burzynski




Kamil Burzynski - 20-06-2007 00:04

  On Tue, 19 Jun 2007 12:48:02 +0200
Kamil Burzynski <K.Burzynski@usunto.adbglobal.com> wrote:

> Nie opisales jak porusza sie robot. Pojedynczy krok robota jest liczba
> calkowita, czy tez wartosci rzeczywiste tez wchodza w gre? Teoretycznie
> gdy sciany sa nieskonczenie blisko siebie - robot przejdzie czy nie?
> Czy tez sciany nie sa az tak dowolne - bo maja jakies ograniczenia na
> pozycje/katy? Obracasz sie zawsze w pelnych katach czy tez w ulamkach?

I jeszcze: labirynt jest skonczony czy nie? Jest ograniczony czy nie?
Moze jest zawsze np. prostokatem poza ktory nie mozna wyjsc?

--
Best regards from
Kamil Burzynski




Marcin 'Qrczak' Kowalczyk - 20-06-2007 00:04

  Dnia 16-06-2007, So o godzinie 09:46 +0200, kots napisał(a):

> Mamy do dyspozycji azymut ktory nakierowuje nasz na wyjscie, sciany moga
> byc dowolne, pod wolonymi katami, dowolne petlne, duze puste
> przestrzenie itp. (taka jaskinia). Dysponujemy tylko czyjnikiem
> zblizzenia do sciany (mozemy sprawdzic czy przed nami jest sciana).
> Wszelkie obroty wykonujemy w stopniach o 360 o 180 itp.

Robot musi tworzyć w pamięci mapę labiryntu. Tylko w ten sposób będzie
wiedział, gdzie warto próbować iść.

--
__("< Marcin Kowalczyk
\__/ qrczak@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/

infinity69 Tylko ja i moja przestrzeń.