Ask Your Question
0

What do the weights of edges in Djikstra represent?

asked 2020-03-04 21:15:38 -0600

DenS gravatar image

I have just followed a course in coursera called "Motion Planning for Self Driving Cars" by the University of Toronto. I understand that the algorithm Dijkstra is used for a graph search where the weights of each edge are different compared to the Best First Search (BFS). For a self-driving car on the road, I understand that these weights are the length of each road for example.

However, I have implemented the Dijkstra algorithm as a global planner for my Turtlebot and I am wondering, in the case of an office space with no roads, what would the edge weights represent? Do they still represent distances, and if so, how far apart are the nodes placed from each other such that it gives rise to different edge weights?

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
0

answered 2020-03-05 05:00:26 -0600

Weasfas gravatar image

In general Djikstra weights can be used to encode some important information not only distance. For instance, you can compute the time to travel, or the battery depletion estimation between two vertices. Dijkstra's algorithm can be used to find "shortest" path where shortest means smallest total weight, taking distance as shortest distance, time as smallest amount of time taken to complete the path etc.

Hence, the representation of the weights is arbitrary, generally speaking the weights are used as a distance because is usually the most suitable and easy way to do path planning between nodes, but you can have another metric or even an aggregation of information from several metrics.

You will need to analyze how you want to model the problem of indoor path planning with the turtlebot, it may depend on your indoor environment, its limitations and structure. Usually when you generate a graph in order to apply path planning algorithm you decide the distance between nodes and the weights assigned to each edge, modeling the estimated behavior of the movement of the robot and taking into account its physical and hardware limitations.

But I will say, I will glad to hear what other members more experienced in this field have to say about this problem.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-03-04 21:15:38 -0600

Seen: 79 times

Last updated: Mar 05 '20