O nejkratších cestách v částečně známém prostředí

On Shortest Paths in Partially Known Environment

book chapter

en

In robot motion planning a robot should pass around obstacles, from a given starting position to a given target position, touching none of them, i.e., the goal is to find a collision-free path from the starting to the target position. This task has many specific formulations depending on the shape of obstacles, eligible directions of movements, knowledge of the scene, etc. The basic step in all methods used for solving this problem, e.g., roadmap methods, cell decomposition and case-based reasoning is to find the shortest path between starting and target positions or to find the shortest paths among all pairs of positions when we use a database of stored solutions and try to adapt these old solutions to a new problem. However, in a partially known scene, we must approximate the lengths of edges in a graph representation of the scene. In this contribution, we deal with the All-Pairs Shortest Paths Problem (APSPP) on a graph in which a fuzzy number, rather than a real number, is assigned to each edge. Since the fuzzy min operator based on the extension principle leads to non-dominated solutions, we propose another approach to solving the APSPP using a suitable fuzzy ranking method. We also show that the efficiency of computations may be improved by the proposed APSPP modification of the Dijkstra algorithm based on a binary heap data structure.

V úloze plánování pohybu robotu má robot projít z počáteční do koncové pozice ve scéně s překážkami tak, aby nedošlo ke kolizi s některou z překážek. Tato úloha má řadu specifických formulací podle tvaru překážek, možných směrů pohybu, znalosti scény apod. Základním krokem ve všech metodách použitých pro řešení zmíněného problému, např. v metodách silniční mapy, dekompozici na buňky a v případovém usuzování je cílem najít nejkratší cestu mezi počáteční a cílovou pozicí mezi všemi překážkami. Použijeme-li databázi vyřešených případů, pak se snažíme přizpůsobit tato řešení novému případu. Avšak v částečně známé scéně musíme aproximovat délky hran v grafové reprezentaci scény. V příspěvku se zabýváme hledáním nejkratších cest mezi všemi dvojicemi vrcholů grafu, kde ohodnocení hran grafu není dáno deterministicky, ale je vyjádřeno fuzzy čísly. Protože operace určení minima na fuzzy číslech využívající princip rozšíření vede k nedominovaným řešením, navrhujeme jiný přístup využívající vhodnou metodu srovnávání fuzzy čísel. Rovněž ukážeme, že efektivitu výpočtu řešení daného problému lze zvýšit modifikací Dijkstrova algoritmu založeného na datové struktuře binární halda.

In robot motion planning a robot should pass around obstacles, from a given starting position to a given target position, touching none of them, i.e., the goal is to find a collision-free path from the starting to the target position. This task has many specific formulations depending on the shape of obstacles, eligible directions of movements, knowledge of the scene, etc. The basic step in all methods used for solving this problem, e.g., roadmap methods, cell decomposition and case-based reasoning is to find the shortest path between starting and target positions or to find the shortest paths among all pairs of positions when we use a database of stored solutions and try to adapt these old solutions to a new problem. However, in a partially known scene, we must approximate the lengths of edges in a graph representation of the scene. In this contribution, we deal with the All-Pairs Shortest Paths Problem (APSPP) on a graph in which a fuzzy number, rather than a real number, is assigned to each edge. Since the fuzzy min operator based on the extension principle leads to non-dominated solutions, we propose another approach to solving the APSPP using a suitable fuzzy ranking method. We also show that the efficiency of computations may be improved by the proposed APSPP modification of the Dijkstra algorithm based on a binary heap data structure.

Shortest path problem, fuzzy ranking, binary heap, priority queue

2006

15.12.2006

Brno University of Technology, Faculty of Mechanical Engineering

Brno

80-214-3341-8

Březina, T. (ed.), Simulation Modelling of Mechatronic Systems II

2

139–147

9