On Shortest Paths in Partially Known Environment

book chapter

English

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

ŠEDA, M.

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

Mechatronika

2

139

147

9