Surfing through websites and videos, I interpreted that cost refers to parameters such as time taken to go from start position to the goal position or distance traveled in every possible path and cost functions refers to the functions of these parameters with some condition such as shortest time taken or shortest distance traveled. So is this interpretation, right?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The term cost function in path planning is borrowed from optimization. Rightfully so, since path planning in most cases is, in fact, an optimization problem.
The cost function in optimization expresses the function which should be minimized (as optimization is a synonym for minimization). Optimizing a cost function translates to finding its minimum. So if your function is $$f(x,y) = \sqrt{x^2+y^2}$$ by minimizing this function as: $$ \begin{align} \underset{x,y}{\min}&\quad f(x,y)\end{align} $$ you will get $f=0$. If we attribute meaning to this you could say that we are looking to minimize a distance and here cost becomes the distance. In this trivial example, the minimum cost is 0, i.e. you cannot be closer than distance 0.
If we look at path planning the cost function gets more complicated. If we look to minimize the travelled distance the cost function is the travelled distance, which is dependent on all the waypoints which you travel through. Let‘s denote the list (or vector) of waypoints with
$$\Theta =[\theta_1 \dots \theta_n ] $$
So the distance you travel can be calculated from these waypoints as $$f(\Theta)=\sum{\theta_i} $$
(If all $\theta$ are adjacent points on a uniform grid.) Minimizing this alone as $$ \begin{align} \underset{\Theta}{\min}&\quad f(\Theta) \end{align} $$ does not bring much since we can already know, that the minimum amount of travel we can do is 0. What makes this interesting are additional constraints, in other words, the function is subject to (s.t.) constraints. Setting the first point $\theta_1$ to be the starting point, forcing the last one $\theta_n$ to be the last one and forcing the all neighbouring $\theta_i$ to be adjacent. Loosly describing these as contraints gives:
\begin{align} \underset{\Theta}{\min}&\quad f(\Theta)\\ \text{s.t.}&\quad \theta_1 = \theta_{start}\\ &\quad \theta_n = \theta_{end}\\ &\quad \text{adjacent}(\theta_i, \theta_{i+1}) = 1\end{align}
This way, by minimizing the function, the minimum length of the path which connects the starting point with the target point can be found. However, finding the length is in many cases not what we are looking for. Finding the waypoints themself is in many cases of interest. This is also minimization (or optimization) of the same function, but we are not interested in the output of the function, but in the argument of the function, $\Theta$.
$$ \begin{align} \underset{\Theta}{\text{argmin}} &\quad f(\Theta) \end{align} $$
Distance is just one example of cost. It can also be the fastest route (minimum time), minimum energy, a combination of more factors (e.g time and distance) expressed as a weighted sum.
