Skocz do zawartości

[Teoria] Liczby losowe - generowanie i wykorzystanie w robotyce amatorskiej.


Kaytec

Pomocna odpowiedź

Liczby losowe.

Możecie zapytać, po co komu liczby losowe w robotyce? W dziedzinie, w której wszystko ma być z założenia precyzyjnie wykonane, wydawać by się mogło że liczby losowe nie mają racji bytu. Jednak jeżeli ktoś da robotowi do wykonania zadanie w którym robot ma losowo wybrać drogę lub jakąś rzecz (np. do kontroli jakości), wtedy zaczyna nam brakować magicznej liczby która podejmuje tą decyzję. Kolejnym przykładem jest sytuacja w której robot w losowym czasie ( najczęściej w danym zakresie czasu), ma zacząć działać. Jako przykład można podać np robota pilnującego jakiegoś obiektu, bądź urządzenia sprawdzającego refleks, czyli różnego rodzaju bramki startowe, czy światła wyścigowe, ale to już przykłady bardziej z automatyki. W robotyce amatorskiej liczba losowa przydatna jest w wyborze drogi przez robota typu micromouse. Zakładając że w algorytmie chcemy mieć pewien element losowości.

Opiszę tutaj trzy proste algorytmy generowania liczb losowych które każdy bez większego wysiłku może zastosować w swoich projektach.

1. Państwa - miasta

Każdy z nas na pewno grał kiedyś w grę pod tytułem państwa-miasta, niestety nie jest to łupanka typu GTA, ale ma pewien interesujący nas element. Gracz musiał w myślach mówić po kolei alfabet, czekając kiedy drugi gracz powie stop. Po wypowiedzeniu słowa, pierwszy gracz zatrzymywał się na ostatnio pomyślanej literze. W ten sposób uzyskiwano element losowy potrzebny do gry.

Algorytm jest prosty

-myśl kolejne litery

-jeśli będzie ostatnia litera alfabetu wróć do pierwszej (A)

-sprawdź czy został powiedziany stop

-podaj literę

To samo przenieśmy do jednego z najprostszych języków programowania AVR - Bascom AVR

'------------------------------------
Sub Losowo                                                  'nazwa podprogramu
X = X + 1                                                   'Zwieksz zmienną x o 1
If X = 25 Then X = 1                                        'Jeśli x wyniesie 25 zmień x na 1
Cls                                                         'wyczyść lcd
Lcd ; X ;                                                   'Wyświetl liczbę X na wyświetlaczu

Waitms 10                                                   'poczekaj 10 milisekund

End Sub
'--------------------------------------

Efekt przypomina działanie stopera.

To jest oczywiście tylko sam podprogram zwiększający o jeden liczbę x, oraz zmieniający ją na jedynkę gdy wyniesie 25. Należy do powyższego programu dodać jeszcze funkcję sprawdzającą czy "został wypowiedziany stop", czyli sprawdzenie czy przycisk jest naciśnięty. W tym przypadku jest to główna pętla programu.

Glowna:
Do
      If Pinb.0 = 1 Then
         Gosub Losowo
      Elseif Pinb.0 = 0 Then
         Gosub Stopp
End If

Waitms 5
Loop

End

Dwa proste warunki, jeżeli przycisk nie jest naciśnięty, dodaj kolejną liczbę. Jeżeli został naciśnięty, wyświetl tą liczbę na wyświetlaczu - podprogram stopp. Przedział liczb możemy dowolnie zmieniać zmieniając warunki do ilu podprogram ma liczyć, ile dodawać po każdym cyklu. Wynik możemy dowolnie pomnożyć o jakąś stałą. Wszystko zależy od tego do czego zamierzamy wykorzystać losowanie, a zatem jakie przedziały liczb są nam potrzebne. Pełny program dla atmegi8 z obsługą wyświetlacza znajduje się w załączniku.

Tego typu losowanie sprawdza się idealnie tam gdzie sygnał stop jest aktywowany przez zewnętrzny sygnał. Cała sztuczka polega na tym żeby liczyć na tyle szybko że aktywując stop dzieje się to w praktycznie losowym momencie. Jeśli każemy liczyć programowi do 10000 co 10ms, to klikając w pierwszej sekundzie otrzymamy wynik z przedziału 0-100. Dlatego powyższy sposób nadaje się tylko do liczenia małych wartości np od zera do 100 i następnie ich edytowania (mp. mnożenia x 100). Jednak do wielu zastosowań jest to zupełnie wystarczające.

2. RND

Bascomowa funkcja RND, zwraca pseudolosową liczbę z określonego przedziału.

zmienna = RND(zakres)

Funkcja może wydawać się idealna, ale nie jest tak różowo z jednego powodu. Przy każdym resecie procesora, sekwencja liczb powtarza się.

Podprogram przy RND wygląda tak:

Sub Losowo
X = Rnd(100)                                                'generuj liczbę od 0 do 100
Cls                                                         'wyczyść lcd
Lcd ; X ;                                                   'Wyświetl liczbę X na lcd

End Sub

Ratunkiem jest tutaj zmiana podstawy liczenia liczby psudolosowej czyli zmiennej __rseed. Aby za każdym razem uzyskiwać inne liczby należało by zmieniać podstawę. Według mnie funkcję można uznać za ciekawostkę, lub wykorzystać do generowania liczby losowej, ale za każdym razem należy pamiętać o zmianie podstawy __rseed.

3. Szum biały

Kolejna metoda uzyskiwania losowych liczb oparta jest o wykorzystanie białego szumu. Szum akustyczny jest to sygnał o przypadkowo (czyli losowo) zmieniających się w czasie parametrach. Właśnie o losowość parametrów nam chodzi. Idea jest prosta, zmierzyć w nieokreślonym momencie wartość napięcia białego szumu i mamy podstawę do liczby losowej. Metoda ta wymaga użycia zewnętrznego generatora szumów. W internecie jest mnóstwo opisów jak zrobić generator szumów, osobiście polecam ten generator.

Po podłączeniu wyjścia generatora do wejścia ADC mikrokontrolera, teoretycznie przy każdym pomiarze otrzymujemy losową wartość z przedziału 0-255. W rzeczywistości ze względu na dość płaską charakterystykę białego szumu jest on w przedziale 200-255. Tyle udało mi się uzyskać z podlinkowanego generatora szumu przy napięciu zasilania 7V.

Podprogram odczytujący wartość ADC wygląda standardowo:

Sub Losowo
X = Getadc(0)
Cls
Lcd ; X ;

Waitms 20

End Sub

Jednak jak wspominałem wcześniej odebrane wartości wahają się w dość nieużytecznym zakresie liczbowym. Z pomocą przychodzi wspomniana funkcja RND. Można wykorzystać odebraną wartość jako podstawę RND czyli __rseed. Otrzymujemy wtedy liczby w użytecznym zakresie. W tej metodzie sztuka polega na zrobieniu odpowiedniego generatora szumu białego w zakresie napięcia 0-5V.

Podsumowanie.

Każda z przedstawionych metod ma zarówno wady i zalety. Sposób pierwszy jest idealny gdy nie mamy miejsca na dodatkowe układy, a problem musimy rozwiązać tylko modyfikując program lub potrzebujemy tylko kilkunastu losowych liczb. Metoda druga jest niejako sposobem na zmianę liczb na bardziej użyteczny zakres. W trzeciej metodzie pojawia się trudność zrobienia dobrego generatora, ale efekt nie pozostawia żadnych wątpliwości co do przypadkowości wyniku.

Dziękuje, pozdrawiam i zapraszam do głosowania.

Listing w załączniku.

os.txt

Link do komentarza
Share on other sites

Z grubsza ok, ale sam generator na przycisku jest dośćprosty - wystarczy albo w pętli głównej zwiększać jakiś licznik na okrągło, albo w przerwaniu od licznika. Wynik dzielić modulo aby uzyskać liczbę losową.

Jeśli chodzi o sam generator, to wydaje mi się, że najprostszym rozwiązaniem jest zostawienie wiszącej ścieżki od jednego ADC, albo ew. podłączenie przez kondesnator np. do Vcc, aby mierzyć wartość zmienną napięcia. A konkretnie 1 lub 2 najmłodsze bity, którymi uzupełniamy jakąś zmienną - uzyskamy losowy sygnał.

Link do komentarza
Share on other sites

Zarejestruj się lub zaloguj, aby ukryć tę reklamę.
Zarejestruj się lub zaloguj, aby ukryć tę reklamę.

jlcpcb.jpg

jlcpcb.jpg

Produkcja i montaż PCB - wybierz sprawdzone PCBWay!
   • Darmowe płytki dla studentów i projektów non-profit
   • Tylko 5$ za 10 prototypów PCB w 24 godziny
   • Usługa projektowania PCB na zlecenie
   • Montaż PCB od 30$ + bezpłatna dostawa i szablony
   • Darmowe narzędzie do podglądu plików Gerber
Zobacz również » Film z fabryki PCBWay

Szkoda, że pisząc o liczbach losowych autor nic nie wspomniał o matematyce - rachunku prawdopodobieństwa i statystyce. Warto wspomnieć jakie cechy powinien mieć dobry generator liczb. Nie każde źródło liczb pozornie losowych spełnia wymogi generatora.

Np. wciskanie jednego przycisku wcale nie jest tak bardzo losowe - ludzie mają dość przewidywalny refleks i rozkład prawdopodobieństwa wcale nie jest jednostajny.

Nawet dodawanie liczb "modulo" należałoby podeprzeć pewną dawką matematyki. Wybór podstawy dla działań modulo ma znaczenie. Przykładowo wybranie naturalnej dla timera i informatyki liczby 256 jest bardzo złym pomysłem. Podstawa działań modulo powinna być liczbą pierwszą - tego autor nie wspomniał, ani tym bardziej nie napisał dlaczego.

Link do komentarza
Share on other sites

Ewentualnie kupić licznik Geigera, trochę materiału promieniotwórczego z ruskiego złomu i zliczać sobie rozpady. A jeszcze lepiej stworzyć barierę potencjału o prawdopodobieństwie tuelowania 0.5 i wtedy gotowa liczba losowa 🙂 A jako ciekawostka, można kupić sobie gotowy generator liczb losowych oparty na izyce kwantowej.

Link do komentarza
Share on other sites

@Timonek: nie udowodnię, to trzeba przetestować, przesłać UARTem na kompa kilka milionów takich liczb (np. 6.5M liczb, wymagających 26M pomiarów, czyli kilka godzin) i sprawdzić histogram oraz widmo. Metodę można zawsze zmodyfikować, poprzez uzupełnianie jakiejś tablicy czy czegoś. Można też sprawdzać po prostu rozkład poszczeqólnych liczb 1-2 bitowych, jeśli będzie jednostajny (zarówno histogram jak i widmo), to liczby 16b też będą losowe.

Link do komentarza
Share on other sites

Kombinujecie panowie... Generator liczb pseudolosowych jak RND w bascomie, albo rand() w C + zegar czasu rzeczywistego zasilany osobno coby za ziarno generatora użyć czasu w us i mamy problem rozwiązany tak samo jak w PC.

Link do komentarza
Share on other sites

Nie do końca kombinujemy 😉 Może trochę. A zegar czasu rzeczywistego to już osobny układ (albo dokładanie baterii dla układu posiadającego zegar). Koniec końców można do układu po prostu wpisać tablicę liczb (pseudo)losowych, nawet parę tysięcy liczb 8b, wybieranie liczby z takiej tablicy właśnie na podstawie zegara.

Link do komentarza
Share on other sites

@Timonek: nie udowodnię, to trzeba przetestować, przesłać UARTem na kompa kilka milionów takich liczb (np. 6.5M liczb, wymagających 26M pomiarów, czyli kilka godzin) i sprawdzić histogram oraz widmo. Metodę można zawsze zmodyfikować, poprzez uzupełnianie jakiejś tablicy czy czegoś. Można też sprawdzać po prostu rozkład poszczeqólnych liczb 1-2 bitowych, jeśli będzie jednostajny (zarówno histogram jak i widmo), to liczby 16b też będą losowe.

Jeżeli użyjesz zwykłej sumy, to o ile dobrze pamiętam uzyskasz w ten sposób rozkład normalny 🙂

Link do komentarza
Share on other sites

Z pamięcią to nie problem, w mega16 zwykle nie wykorzystuje się sporej części, a nawet jesli, to m32 kosztuje może 2zł drożej obecnie. W m128 zwykle wolne jest większość pamięci. Generator da nam liczbę, ale pytanie jak często? Co jeśli potrzebujemy np. większe ilości liczb losowych?

Link do komentarza
Share on other sites

Panie, tak często jak chcesz! wywołujesz srand(TIME) na poczaątku programu, gdzie TIME jest czasem systemowym, a później rand() za kazdym razem jak chcesz wartość losową. każde kolejne wywołanie rand() zwróci inna wartość, niezależnie od tego jak często będzie rand() wywoływać. Każde uruchomienie programu da inną sekwencję liczb, bo będzie inny czas do srand() podany. tak to działa na PC i nie widze powodów, żeby nie robić tak samo na uC. Poczytaj sobie jak działają generatory liczb losowych.

Link do komentarza
Share on other sites

Kłania się teoria chaosu. Wykonać prosty układ elektryczny-chaotyczny i już ma się z czego korzystać. Składa się z układu drgającego LC i ujemnej rezystancji. Jeśli kogoś to bardziej interesuje proszę o info na PW(nie zawsze czytam forum) i postaram się zależ notatki z ćwiczeń z dynamiki obwodów.

Link do komentarza
Share on other sites

Dołącz do dyskusji, napisz odpowiedź!

Jeśli masz już konto to zaloguj się teraz, aby opublikować wiadomość jako Ty. Możesz też napisać teraz i zarejestrować się później.
Uwaga: wgrywanie zdjęć i załączników dostępne jest po zalogowaniu!

Anonim
Dołącz do dyskusji! Kliknij i zacznij pisać...

×   Wklejony jako tekst z formatowaniem.   Przywróć formatowanie

  Dozwolonych jest tylko 75 emoji.

×   Twój link będzie automatycznie osadzony.   Wyświetlać jako link

×   Twoja poprzednia zawartość została przywrócona.   Wyczyść edytor

×   Nie możesz wkleić zdjęć bezpośrednio. Prześlij lub wstaw obrazy z adresu URL.

×
×
  • Utwórz nowe...

Ważne informacje

Ta strona używa ciasteczek (cookies), dzięki którym może działać lepiej. Więcej na ten temat znajdziesz w Polityce Prywatności.