|
[Home]
Path-planning can be implemented in many areas of modern life. Time schedule, logistics, production planning, robots, e.t.c. are some of them of the most common uses. But there are some other areas not so common such as air-traffic control. We approache path-planning from a not so common aspect, using advanced robotic algorithms. With robotics, the problem is solved via navigation functions (modified potential functions) with great results.
In fact EUROCONTROL (European Organisation for the Safety of Air Navigation) was facing a problem with overlapping aircraft labels in the ATM consoles shown in Figure 1 and 2.
Figure 1: ATM console.
Figure 2: Label overlapping area.
We developed a Software System [Windows XP and Vista compatible] enabling the collision-free motion of aircraft labels using an implementation of the Navigation Functions methodology.
Potential field techniques have been successful for real-time obstacle avoidance in changing environments, but for motion planning, there are several limitations. One major problem is the spurious local minima, just as in the case:
(a)
(b)
Figure 3: Potential Function surface and robot trajectory with local minimum.
To escape these, one must resort to either randomizing techniques or navigation functions described below.
Navigation Functions guarantee collision avoidance in perfectly known and stationary environments. We consider a “decentralized” control algorithm where each controlled label (robot) treats as obstacles the labels, position symbols/tracks history and leader lines of all other aircrafts. Those are considered to be quasi-static due to the fact that the update rate of the position symbol of the aircraft is slow when compared with the anti-overlapping motion of the labels. The main advantage of navigation functions is the unique minimum at qd which means that robot will approach and finally stop at the target configuration without getting stuck in local minimums. At Figure 4 one can see that robot will not get stuck in local minimum as in Figure 3 and will converge to the final destination.
(a)
(b)
Figure 4: Navigation functions have no local minimums.
The proposed approach is applicable to point-mass robots moving in a generalized sphere world. To achieve that, suitable coordinate transformations are used to map the original workspace to a model sphere world - a disc punctured by an arbitrary number of smaller disjoint discs representing obstacles. Furthermore, the point-mass robot is created by simply by deducting the volume from the label and adding it to the obstacles (Minkowski sum).
Figure 5: Representation of label (robot) as a point.
A simple case study involves two airplanes that are heading in opposite trajectories and label original rest position is occupied by the other aircraft. Goal configuration of every label is set at 225o anti-clockwise from the speed vector and in 2 cm distance from the position symbol. In Figure 6 (b) one can see the potential field that is generated during the aircrafts movements of Figure 6 (a).
(a)
(b)
Figure 6: Navigation functions surface.
The Potential field makes the label-robot to “roll downhill” to the goal configuration. Robot will end up to the destination point starting from every point of the workspace. This conclusion can be drawn from Figure 6 (b) where the contours of the field are shown. Higher values of the fields have been depicted red, with maximum value 1 set to boundary and inside obstacles. As one moves closer to the goal configuration potential field values become lower and colour turns gradually to blue (potential field value 0).
The proposed system user interface is shown in Figure 7. The user can alter the parameters that are responsible for the label movement along with the desired destination angle of the labels. Also the final version involved database connection with real-time data for the aircrafts.
Figure 7: User interface.
The downloadable version contains only the simple case study (depicted in Figure 6) with two airplanes that are heading in opposite trajectories and a simulation video of a "busy" area with over 10 aircrafts involvement.
You can download the the required codec for the simulation video from here (Size: 169 KB). The simulation avi video can be found here (Right click mouse and press "Save Target As..." - Size: 1,88 MB).
For any path-planning problem fell free to contact us and we will come up with new, state of the art solutions!
| 
