Navigation functions are used in robotics, to create an intuitive feedback control in the situation where the system is fully actuated.
One usually starts with the configuration space which is simple (say, a convex domain $D$ in $n$-dimensional Euclidean space), with a target point $p\in D$ inside the domain. In the unobstructed setting, one can easily find a function $f$ (target function) such that its gradient vector field
$$v=-\mbox{grad} f$$
a) is pointed inside the domain $D$, so that there is no risk to leave it, and
b) has all trajectories convergent to the target point.
One can think of this function (and of other navigation functions we will be constructing) as potential energy minimized by the system: the target position corresponds to the global minimum of that function, to where trajectories converge.
This problem becomes more complicated when there are obstacles: some subsets $O_\alpha, \alpha\in A$ of the domain which the trajectories are not allowed to enter. In this case, the original vector field needs to be modified.
The navigation function apparatus proposed long ago by Koditschek and Rimon adds to the target function $f$ a barrier function $g$, which is explodes to $+\infty$ near the obstacles, but is small elsewhere. If one forms the new function,
$$U=f+\epsilon g$$ then, intuitively, far from the obstacles, the gradient vector field $$v_b=-\mbox{grad} U$$ will be following the trajectories of the original $v$, while being repelled from the obstacles when $g$ becomes large.
Here, as an example, we have the box $-3\leq x\leq 3, -2\leq y\leq 4$, and the energy function $$f=x^2+(y+1)^2$$ whose trajectories converge to the target point $p=(0,-1)$.
What happens if one adds an obstacle: the circle of radius $1$ centered at $(0,1)$? One would need to modify the vector field so that its trajectories to avoid the obstacle.
We introduce the barrier function $$g=-\log(x^2+(y-1)^2-1)$$ (see the contour plot on the right). It explodes near the boundary of the obstacle.
Combining $f$ and $g$ results in the navigation function $U=f+\epsilon g$, with the tunable parameter $\epsilon$. Antigradient vector fields for different values of $\epsilon$ ($1.5$ on the left, $.5$ on the right) are shown below.
Of course, the choice of $f$ and $g$ is arbitrary. One could have started with $f=2x^2+(y+1)^4$ and $g=1/(x^2+(y-1)^2-1)$. Fine-tuning such navigation fucntion is the task for this project.
Namely, one will have to create a navigation function for $n=5$ mobile robots, that start at the fixed positions $(\cos \theta_k, \sin\theta_k), \theta_k=k\pi/n, k=1,\ldots, n$ on the boundary of the unit circle and have each to reach prescribed point on the boundary of the circle, all the while avoiding the following obstacles, and staying away from each other at the distance at least $r$.
The target of the $k$-th robot is at the position $\theta’_k=\sigma_k\pi/n+\pi$, where $\sigma$ is a permutation of the numbers $1,2,3,4,5$: there are $n!=120$ such permutations, and for each of them one would need to generate the trajectory moving the robots from their starting to their final positions.
The obstacles are three disks, centered at $(0,0), (.5,.2), (-.3,-.3)$ each of radius $.1$, and $r=.05$.
The tak is to produce a navigation function of the vector of positions of $n$ robots within the disc (so that the vector has $2n$ components $(x_1,y_2,x_2,y_2,\ldots,x_n,y_n)$), and explicit expressions for its gradient (i.e., partial derivatives with respect to the coordinates $(x_k, y_k), k=1,\ldots, n$ of the robots). These expressions will be then fed into the program executing numerically a step. (The gradient will be rescaled to a fixed bound, to avoid arbitrary speeding.)
For each of the $n!$ instances, one would need to record the trajectories, computing how many steps you need to reach the specified positions. The navigation function resulting in the smallest average execution times wins.