# Multidimensional Knapsack Problem for travelling plane with Certainty Parameter, QoS Parameter, Angle Component, Time Deadlines, To be covered necessary Task-points(i.e. the way-points, to define a trajectory) and arbitrary speed
## Given :
- We are given n tasks between the two end-points namely Source and Destination.
- Source is defined as $S(x,y,z)$ where $x$ is the x - coordinate, $y$ is the y - coordinate and $z$ is the z - coordinate of the Source .
- Destination is defined as $D(x,y,z)$ where $x$ is the x - coordinate, $y$ is the y - coordinate and $z$ is the z - coordinate of the Destination .
- Each Tasks $T_{i}$ is defined as $T_{i}(x_i,y_i,z_i,t_i,r_i)$ where $x_{i}$ is the x - coordinate, $y_{i}$ is the y - coordinate and $z_{i}$ is the z - coordinate of the task $T_{i}$ . $t_{i}$ stands for the time needed to complete task $T_{i}$ and $r_i$ is the reward associated with task $T_i$ .
- We have few tasks point i.e $W_{i}(x_i,y_i,z_i)$ that necessarily need to be covered that defines the trajectory between Source and Destination. We are considering the time to reach to these points.
- We have distance from source to the Task : $ST$=[$ST_{1}.......ST_{n}$]
- We have distance from Task to the destination :
$TD$=[$T_{1}D.......T_{n}D$]
- We have distance from between Tasks : $TT$=$\begin{bmatrix}\delta_{11} &. &. &. &\delta_{1n} \\ \delta_{21} &. &. &. &\delta_{2n} \\ . &. &. &. &. \\ . &. &. &. &. \\ \delta_{n1} &. &. &. &\delta_{nn} \\ \end{bmatrix}$

- We have a certainity parameter which is represented by $ct$

Certainity determines the probability of whether or not task will be reached. Higher the certainity the higher is the probability of the task to be reached. This certainity is dependent on various factors such as environmental factors and location of task to be chosen and it varies according to time . Higher certainity means more preferable task .
We are considering the uncertainties such as Rain, Wind, Lightning, Passing by of an arial vehicle, No Fly Zones etc. Based on these conditions we have assigned values to our certainty parameter where :
0.00 : No-fly zone
0.05 : Rain & Wind
0.10 : Rain
0.15 : Rain & Lightning
0.20 : Lightning
0.30 : Wind
0.40 : Aerial vehicle passes by(Deconfliction & Collision Avoidance)
0.50 : Wind & Lightning.
0.60 : Vehicle passes by & Rain
1.00 : No Issue
It is getting multiplied with the arbitary speed since uncertainty indirectly affects the speed of our aerial vehicle

- We have speed from source to the Task, where the speed from source to task is taken as random by a random number generator .
- Similarly, We will have some speed from Task to the destination and between the tasks where the speed is taken as random by a random number generator and it also randomizes on choosing a task . In Real Scenerio the speed might be random because of environmental factors and changing because of changing whether conditions.

- All the speeds will randomize after choosing a task for route.

- We are considering QoS Parameter depending upon the location of the task point in the QoS Region(Open Area), Interruptions/Block surface, difficult terrains, conjested areas, high rise areas, metropolitan areas and depending upon the condition that the delivery point is on the main road or somewhat in the streets or terrace/balcony.
- $qos$ = [$qos_{1}.......qos_{n}$]
We will multiply the quality of service value with reward while calculating efficiency respective to each point.
- Each value of QoS lies in the range 0-1 (inclusive).Depending upon these conditions QoS Parameter is assigned value from 0 to 1 where :
0.00 : Interruptions/Blocked surface
0.05 : Difficult Terrain
0.10 : Congested Areas
0.15 : High rise areas
0.20 : If the delivery point is on the main road
0.40 : If the delivery point lies somewhat in the streets
0.50 : Metropolitan Areas
0.60 : The delivery point has terrace/balcony
1.00 : When task point lies in QoS Region (Open Area)

- $Dmax$ is the total distance allowed and $Tmax$ is the total time allowed while travelling from Source to Destination completing the tasks such as to maximize the total reward.

- Minimum of angle of 0.8 radians(45.8366 degrees) is required to choose a task point from previous task-point considering maneuverability or optimizing cost component.
- Time stamps and Time deadlines are associated with each point in such a way that the time stamp is verified according to the time deadline given for a particular point :

0(LT) : the drone must reach before timestamp value
1(EQ) : the drone must reach at exactly the timestamp value
2(GT) : the drone must reach after the timestamp value

- $Max\sum\limits_{i =1}^{n} r_{i}x_{i}$ where $r_{i}$ is the Reward for a task $T_{i}$ .
- $\sum\limits_{i =1}^{n} d_{i}x_{i} < Dmax$ , where $Dmax$ is the total allowed distance and $d_{i}$ is the distance travelled to reach to task $T_i$ from previous selected task(Source, till no task is selected).
- $\sum\limits_{i =1}^{n} \tau_{i}x_{i} < Tmax$ , where $Tmax$ is the total allowed time and $\tau_{i}$ is the time required to complete task $(t_{i})$ along with the time required to reach a task from previous task selected$(t_{r})$
ie $(t_{i} + t_{r})$.

**where** , $$:x_{i}\in \{0,1\}$$

## Heuristic Algorithm
### Assumptions :
- We can only move in the forward direction,for two task $v_{i}$ and $v_{j}$ , the movement is allowed if $i<j$.
### Initialization :
- efficiency of task when we are at $i$ is ($\epsilon_{i}$):
$$\frac{r_i*qos_i}{t_i+\tau_{i}}$$ ,where $t_{i}$ is time it takes to complete the task and $\tau_i$ is the time to reach to current task from previous task, $r_{i}$ is the reward associated with task point and $qos_i$ is the QoS parameter associated with the respective task point.

### Algorithm :
* Chosen tasks : $ta$ = [] and $TotalR$ = 0
* Choosing Start Point :

- Firstly, verify the task points which can be reached according to the time deadline(as well as try to cover any way point that comes before the task point) then choose the most efficient task point.

- Generate a random value for speed ($varspeed$) which is between a lower and an upper limit,then multiply it with certainty value and randomize the certainity value $ct$ between 0 and 1 to simulate the changing environmental conditions, calculate the time to reach to the task point according to varspeed which is $\tau_i$.

- In case the time stamp is verified for a particular point then do the following :
- find $\epsilon$ for all i, where i<n
- $$\epsilon_{i}=\frac{r_i*qos_i}{\tau_i+t_{i}}$$ where $\tau_i$ is the time to reach the current point from the $Source$ and $t_{i}$ is the time to complete a task point.

- Choose the task point ${T_i}$ with the highest $\epsilon$ in case no way point is found before $T_{i}$, but if some way points is present before $T_{i}$ then choose it .
- Append the chosen point to $ta$.
- Change $Tmax=Tmax-\tau_{i}$ - $t_{i}$ and $Dmax=Dmax-ST_i$ in case a task point was chosen but if case a way point was chosen then change $Tmax$ = $Tmax$ - $\tau_{i}$ and $Dmax$ = $Dmax$ - $ST_{i}$.
- Add chosen task to $ta$ and change $TotalR = TotalR + r_{i}$ in case a task point was chosen.
* Choosing further tasks ,
- While we have tasks left in range $i+1$ to $n$ & if $Dmax$ - $d_{s}$ - $TD_{s}$ >= 0 and $Tmax$ - ($t_{s}$ + $TimeTT_{ls}$ + $TimeTD_{s}$) >= 0
- randomize the certainity value every time a task point is chosen in order to simulate changing environmental conditions.
- randomize the speed $varspeed$ and multiply it with the certainty value associated with the respective task point.
- for each task $T_{m}$ [Where $m$ in range($i+1$,$n$)]:

- check whether the $time stamp$ is verified for a particular point.
- check whether the $angle$ formed by the line segment from the previous task to current task and from current task to $T_{m}$ is lesser than the angleLimit ($0.8$ radians).

- if $angle$ and $time stamp$ are verified for this point m.

- calculate time to reach by using the formulae $\tau_{i} = distanceFromPrevPointToChild/varspeed$ before calculating efficiency.

- find $\epsilon$(efficiency) for this task points and keep track of the highest efficient task point.

- $$\epsilon_{i}=\frac{r_i*qos_i}{\tau_{i}+t_i}$$ where $t_{i}$ is time it takes to complete the task point and $\tau_i$ is time to reach task $s$ from previous task, $r_{i}$ is the reward associated with point and $qos_i$ is the qos parameter associated with the respective point.

- find maximum $\epsilon$ as $\epsilon_{max}$ and corresponding task and keep track of any waypoint $w$ coming in between.
- Add the most efficient task point to $ta$ in case no way point was found else choose the way point and add it to $ta$.
- Change $TotalR = TotalR + r_{s}$ in case a task point was found before any way point.
- Change $Tmax=Tmax-(t_{i}$+$TimeTT_{is})$ and $Dmax=Dmax-TT_{is}$ in case a task point was found before any way point else change $Tmax$ = $Tmax$ - $t_{i}$ and $Dmax$ = $Dmax$ - $TT_{iw}$ if a way point was found before task point.
* Repeat untill no task is left to choose in range $i+1$ to $n$.
* To end Change $Dmax = Dmax$ - $TD_{l}$ and $Tmax = Tmax$ - $TimeTD[l]$ where l is the last task chosen .

* We Have Total Reward in $TotalR$ and chosen path in $ta$.