Plánování cesty mobilního robota pomocí případového usuzování

Mobile Robot Path Planning by Means of Case-Based Reasoning

journal article - other

en

In this paper, we deal with mobile robot path planning in a partially known dynamic environment modelled by a two-dimensional grid in which known static obstacles and hazardous areas are defined. The aim of the path planning is searching for a path from a start to a goal position without collisions with known obstacles minimizing length and difficulty (risk) of the path. We propose path planning methods based on using a case graph, which is a structure composed of segments of already used paths. These methods try to construct a new path combining paths in the case graph with paths found by the A* algorithm. We present results of comparing proposed methods and methods based only on using Dijkstra's algorithm and the A* algorithm.

V tomto příspěvku se zabýváme plánováním cesty mobilního robota v částečně známém dynamickém prostředí modelovaném dvoudimenzionální mřížkou, ve které jsou zadány statické překážky a nebezpečné oblasti. Cílem plánování cesty robota je hledání cesty z počáteční do cílové pozice bez kolizí se známými překážkami při minimalizaci délky a obtížnosti (rizika) cesty. Navrhujeme metody plánování cesty založené na použití případového grafu, což je struktura složená ze segmentů již použitých cest. Tyto metody se pokoušejí konstruovat novou cestu kombinováním cest v případovém grafu s cestami nalezenými algoritmem A*. Prezentujeme výsledky srovnání navržených metod a metod založených pouze na použití Dijkstrova algoritmu a algoritmu A*.

In this paper, we deal with mobile robot path planning in a partially known dynamic environment modelled by a two-dimensional grid in which known static obstacles and hazardous areas are defined. The aim of the path planning is searching for a path from a start to a goal position without collisions with known obstacles minimizing length and difficulty (risk) of the path. We propose path planning methods based on using a case graph, which is a structure composed of segments of already used paths. These methods try to construct a new path combining paths in the case graph with paths found by the A* algorithm. We present results of comparing proposed methods and methods based only on using Dijkstra's algorithm and the A* algorithm.

Mobilní robot, plánování cesty, případové usuzování, algoritmy prhledávání grafu.

Mobile robot, path planning, case-based reasoning, graph searching algorithms

2005

20.09.2005

1210-2717

Inženýrská mechanika - Engineering Mechanics

12

A1

8