Searching for the shortest-path in an unknown or changeable environment is a common problem in robotics and video games, in which agents need to update maps and to perform re-planning in order to complete their missions. D* Lite is a popular incremental heuristic search algorithm (i.e., it utilizes knowledge from previous searches). Its efficiency lies in the fact that it re-expands only those parts of the search-space that are relevant to registered changes and the current state of the agent. In this paper, we propose a new D* Extra Lite algorithm that is close to a regular A*, with reinitialization of the affected search-space achieved by search-tree branch cutting. The provided worst-case complexity analysis strongly suggests that D* Extra Lite’s method of reinitialization is faster than the focused approach to reinitialization used in D* Lite. In comprehensive tests on a large number of typical two-dimensional path-planning problems, D* Extra Lite was 1.08 to 1.94 times faster than the optimized version of D* Lite. Moreover, while demonstrating that it can be particularly suitable for difficult, dynamic problems, as the problem-complexity increased, D* Extra Lite’s performance further surpassed that of D*Lite. The source code of the algorithm is available on the open-source basis.
In this paper creating semantic maps based on laser terrestrial data is shown. Semantic map is based on transformed geometric data (3D laser range finder) into the data with assigned labels. This labels can help in several applications such as navigation of mobile robot by finding traversable and not traversable regions. Computation of large 3D data sets requires high computational power, therefore we proposed the GPU based (Graphic Processing Unit) implementation to decrease the computational time. As a result we demonstrate the computed semantic map for mobile robot navigation.
PL
W niniejszej pracy zostało przedstawione tworzenie map semantycznych na podstawie danych z naziemnego skaningu laserowego. Mapa semantyczna bazuje na danych pomiarowych z przypisanymi etykietami. Te etykiety mogą zostać wykorzystane w wielu aplikacjach, jak nawigacja robota mobilnego z wykorzystaniem podziału na regiony przejezdne i nieprzejezdne. Obliczenia dużych trójwymiarowych zbiorów danych wymaga zastosowania duże mocy obliczeniowej, dlatego zaproponowaliśmy implementację wykorzystującą GPU (Graphic Processing Unit), by zmniejszyć czas obliczeń. W rezultacie prezentujemy mapę semantyczną do nawigacji robota mobilnego.
System nawigacji autonomicznego robota mobilnego składa się z następujących elementów: detekcja przeszkód, znajdowanie wolnej drogi prowadzącej z miejsca w którym znajduje się robot do miejsca docelowego, określenie pozycji robota oraz realizacja wyznaczonej ścieżki. W naszych eksperymentach wykorzystywany był robot mobilny B14, 16 czujników podczerwienie, komputer z procesorem Pentium oraz jedną kolorową kamerę. Mapa otoczenia jest reprezentowana jako siatka prostokątnych komórek i budowana jest na podstawie danych pochodzących z sonarów i czujników podczerwieni. Każda komórka może przyjmować jeden ze stanów: wolna, zajęta lub nieznana. Mapa jest budowana przyrostowo przy użyciu rozmytej metody agregacji. Metoda agregacji wymaga znajomości aktualnego położenia robota w otoczeniu. Dlatego samo lokalizacja, oparta na danych otrzymywanych z sensorów jest kluczowym komponentem systemu sterowania robota mobilnego.
EN
Mobile robot navigation can be stated into following problems: detection of obstacles, finding free path leading from the robot's position to the goal position, estimation of the robot position and path realization. In our experiments the mobile robot B14 equipped with 16 sonars, 16 infrared sensors, on-board Pentium computer system and one colour camera is used. The grid-based map of an environment is built based on sonars infrared sensors. The status of each cell of the map can be free, occupied or unknown. The maps is built up incrementally and fuzzy method of data aggregation is used. The mapping method requires knowledge of the robot's position within the environment. Therefore a self-localization module is necessary. In presented navigation system artificial visual landmarks are used in order to compute the robot's position.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.