ROS Answers: Open Source Q&A Forum - RSS feedhttps://answers.ros.org/questions/Open source question and answer forum written in Python and DjangoenROS Answers is licensed under Creative Commons Attribution 3.0Thu, 05 Mar 2020 05:00:26 -0600What do the weights of edges in Djikstra represent?https://answers.ros.org/question/345921/what-do-the-weights-of-edges-in-djikstra-represent/ 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? Wed, 04 Mar 2020 21:15:38 -0600https://answers.ros.org/question/345921/what-do-the-weights-of-edges-in-djikstra-represent/Answer by Weasfas for <p>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. </p>
<p>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? </p>
https://answers.ros.org/question/345921/what-do-the-weights-of-edges-in-djikstra-represent/?answer=345954#post-id-345954In 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.Thu, 05 Mar 2020 05:00:26 -0600https://answers.ros.org/question/345921/what-do-the-weights-of-edges-in-djikstra-represent/?answer=345954#post-id-345954