---
# System prepended metadata

title: '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'

---

# 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 way 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 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 $varspeed$ from source to the Task, which is taken as random  by a random number generator provided it is under a lower and upper limit.

- Similarly, We will have some variable 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.


- 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 $TotalR$.

- 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. //TO BE REMOVED

- 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$.

### Algorithm :
* Chosen tasks array : $ta$ = [], $TotalR$  = 0 and $i$ = 0 
* Choosing the 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 $certainty$ value every time a task point is chosen in order to simulate changing environmental conditions(which is available from a set of values depicting different scenarios according to hazard involved). 
     - Randomize the speed ($varspeed$) which is between a lower and an upper limit 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 according to $time deadline (as well as try to cover any way point that comes before the task point) then choose the most efficient task point.  .
     
         - if $time stamp$ is verified for this point m.

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

        ![](https://i.imgur.com/Var8QyN.png)

         - Calculate $angle$ = angle formed by the line segment from the previous task to current task and from current task to $T_{m}$ (exterior angle) (calculated in degrees)
     
         - If the first point is being chosen, $angle$ = 1 as we cannot calculate the deviation angle with only first two points
 
         - 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)*angle}$$ 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.
  
         - Keep track of 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.

    * Iterate untill the drone has reached to destination or Total Time Limit or Total Distance Limit is exhausted.
* 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$.