# AVSS: Airborne Video Surveillance System
## 4 UAV Placement Algorithm
### Placement Search Algorithm  
Finding the best placement requires excessively large computation which greatly increases with higher resolution. A placement is composed of three independent variables:\(x,y\) coordinates, and the altitude. The \(x\) and \(y\) coordinates are the coordinates of the starting point of the rectangle, which is the bottom left corner of the rectangle. Unit width, height, and the score of a rectangle are fixed values per camera, and the height, width  
larger capture that has maximum score improvement. In this way, the number of possible candidates is \(N^{2}+3N-2\), which considers the general case of focusing area deployment where the entire area is \(F_{0}\) and others are all within \(F_{0}\). The size is dependent on the altitude of the UAV, which also affects the score of the placement. There is no local minima or maxima so that only the size that intersects with other focusing areas or UAV camera needs to be examined. There are three cases of placement: one side increase, both sides increase, and fixed. More specifically, the placement score is expressed as: \(S(h)=F_{1}wlh^{2}\left(\frac{D}{h^{2}}+\alpha\right)\), when both \(w\) and \(l\) are increasing with \(h\). In this case, \(\frac{d}{dh}S(h)=2F_{1}wlh\alpha\), which is always positive, so we know that there is no local maxima. When \(l\) is outside the boundary of the \(F_{1}\), \(S(h)\) is expressed as:  
\[S(h) =F_{1}^{\prime}wy_{1}h\left(\frac{D}{h^{2}}+\alpha\right)+F_{0} wlh^{2}\left(\frac{D}{h^{2}}+\alpha\right),\] \[\frac{d}{dh}S(h) =-F_{1}^{\prime}wy_{1}\frac{D}{h^{2}}+F_{1}wy_{1}\alpha+2F_{0} wha,\] \[\frac{d}{dh}S(h)h^{2} =2F_{0}wh^{3}\alpha+F_{1}wy_{1}\alpha-F_{1}^{\prime}wy_{1}D,\]  
As we know, a cubic function can be expressed as \((h-a)(h-b)(h-c)=h^{3}-(a+b+c)h^{2}+(ab+bc+ac)h-abc\). Because we know all coefficients in the above equation are positive, we can observe that \(a+b+c<0,abc>0\), and as \(h\) is an altitude, \(h>0\), which means there can be only one solution which is a local minima due to always positive \(\frac{d^{2}}{dh^{2}}S(h)\) as long as \(F_{1}^{\prime}\) is positive, which is true. Fixed means the derivative is 0, so there is no change in the component. It is to be noted that the iterative deployment algorithm does not guarantee globally optimal placement of UAVs. Globally optimal solution requires much more excessive search, which is impractical. As an attempt to find a better sub-optimal solution, we have tried multiple rounds of iteration over a fixed number of UAVs, but found that simply sorting the UAVs in the order of \(Dwl\) makes the algorithm finds the best solution. As an additional merit, sorting the UAVs based on the performance and the focusing areas on the focusing score makes the system always monitor high-priority regions whenever possible. In other words, if there is enough number of UAVs, there is no downtime for any of focusing area. Even when the number of UAVs is insufficient, high priority areas are monitored with no downtime. After a round of placement iteration, each UAV camera is stretched to fit the size of uncovered area if it is mostly desired. Also, if multiple cameras are capturing the same region, the region is divided to each of the camera to maximize the score and effectiveness of surveillance.