# Multidimensional Knapsack Problem for travelling plane with certainity parameter, Angle component, 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 way-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 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 randomizing speeds array and time arrays accordingly to simulate the changing whether conditions that might effect the speed of plane and its time to reach a particular task point .
- $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.
- We have a certainity associated with each task:
$ct$=[$ct_{1}.......ct_{n}$]
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 .
This certainity changes with time .For the sake of simplicity we have randomized certainity after chosing a task point with a random number generator. It could be a value between 0 to 1.

- Minimum of angle of 2 radians(114.592 degrees) is required to choose a task point from previous task-point considering maneuverability for optimizing cost component.

- $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\}$$

- We have a quality of service array which consists of values between 0 and 1 .
- we will multiply this array with the respective reward values to modify the reward according to quality of service of a particular task.

## 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($\epsilon_{i}$):
$$ct_{i}*(\frac{r_i}{d_i+\tau_{i}})$$ ,where $ct_{i}$ is the certainity associated with task i $d_i$ can be Source-Task Or Task-Task Distance and $\tau_{i}$ is time it takes to perform the task + time to reach task s from previous task l .

### Algorithm
* Chosen tasks : $ta$ = [] and $TotalR$ = 0
* For Start choose most Efficient Task or the necassary point if we have the most efficient task after neccessary point in the following manner :
- Generate a random value for speed (varspeed) which is between a lower and an upper limit and a randomize all the certainity values between 0 and 1 to simulate the changing environmental conditions, Calculate the Time to Reach the task point according to varspeed.
- find $\epsilon$ for all i and take $d_i=ST_{i}$ ,$\tau_{i}=t_{i}+TimeST_{i}$ , where i<n
- $$\epsilon_{i}=ct_{i}*(\frac{r_{i}}{ST_i+\tau_{i}})$$
- Choose the $T_{i}$ , with the highest $\epsilon$ in case no wavepoint is found before $T_{i}$, but if some wavepoints is present before $T_{i}$ then choose it.
- Change $Tmax=Tmax-\tau_{i}$ and $Dmax=Dmax-ST_i$ in case a task point was chosen but if case a wave point was chosen then Change $Tmax$ = $Tmax$ - $TimeST_{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 all the certainity value for task points.
- randomize the speed.
- recalculate time to reach while calculating efficiency.
- for each task($T_{m}$)[Where m in range(i+1,n)]:
- check whether the angle formed by the line segment from the previous task to current task and from current task to $T_{m}$ is greater than the angleLimit($2$ radians).
- In case of task point angle validity will be taken into consideration but in case of a wave point the angle formed by the previous task, current task and wavepoint can be lesser than angleLimit.
- find $\epsilon$ for all i , $\tau_{i}$ = $t_{i}$ + $TimeTT_{ij}$ and $d_{i}$=TT[i][j] , where i<n
- find maximum $\epsilon$ as $\epsilon_{max}$ and corresponding task and keep track of any wavepoint $w$ coming in between.
- add task $s$ to ta as a chosen tasks in $ta$
- Change $TotalR = TotalR + r_{s}$ in case a task point was found before any wave point.
- Change $Tmax=Tmax-(t_{i}$+$TimeTT_{is})$ and $Dmax=Dmax-TT_{is}$ in case a task point was found before any wave point else change $Tmax$ = $Tmax$ - $t_{i}$ and $Dmax$ = $Dmax$ - $TT_{iw}$ if a wavepoint 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$