Mobility-Aware Computation Offloading for Swarm Robotics using Deep Reinforcement Learning

We consider the CPU frequency of a server as $f_{edg}$ CPU cycles per second, and that of robots as $f_{loc}$. There are $N_{rb}$ robots distributed on a finite plane, and the server is stationary in the center of the plane. The robots’ task is surveying an area while maintaining wireless networking requirements and making optimal swarm motions.

A robot will randomly generate some tasks to process during the movement. We consider that the probability that the robot will generate $k$ tasks in any interval $t$, is subject to Poisson random process with intensity $\lambda$, which is

Assume that the size of a task is $n$, and $c$ is CPU cycles needed to compute one bit of a task. Then, according to [4], the total consumed energy to compute this task locally is $E_{loc}=\gamma ncf_{loc}^{2}$, where $\gamma$ is the effective capacitance coefficient. The time to compute this task is $T_{loc}={nc}/{f_{loc}}$. In practice, robots have different types of tasks , e.g., when the robot performs tasks such as fire rescue, it needs to respond quickly, while the robot’s energy information can be reported periodically in a much slower manner. Here, we assume the task is expected to be finished no longer than $d$.

If the robot generates a task within a slot, it will send state information $I=\{d,v,l,n\}$ to the server immediately, $v$ is the movement direction, $l$ is the location of the user. After receiving this information, the server decides either compute the task locally or in the server.

Since the application is in extreme environments, the mobile server has limited resources, which is different from that in terrestrial environments. Here, we consider the server’s processing latency cannot be ignored. The energy consumption of the server is neglected. Assuming the server can only handle one task at a time, and other tasks are waiting in a queue that is used to offer services in order. When the server agrees to provide services for a task, the robot offloads the task information to the server, and waiting to get the result return. Assuming there are up to $M$ tasks waiting to be processed in the waiting queue. When there are more than $M$ tasks, the server immediately rejects all service requests. The server must process tasks in waiting queue in sequence.

Initially, all robots are randomly distributed in the plane and move in random directions at a constant speed $v$. Robot’s mobility is modeled as the robot moves in a straight line at a constant speed according to the initial direction of movement, and changes direction when it meets the boundary of the plane. According to [5] the upload transmission delay for each bit of a task is:

where $B$ is the bandwidth, $P_{tra}$ is the transmission power, $\sigma^{2}$ is the power of noise, and the channel gain $h$ follows the free space path loss model. Generally, the size of the computing result of a task is much smaller than the task size and, thus, the latency of the server transmitting the computing results to a robot can be ignored.

According to Equation (2), the transmission speed will change as the distance between a robot and a server changes. Therefore, due to the movement of robots, the transmission delay $T_{tra}$ is the solution of the integral equation: $\int_{0}^{T_{tra}}Blog_{2}(1+P_{tra}h/\sigma^{2})dt=n$.

Assuming all robots generate $N_{t}$ on average tasks per unit time. We define $\bm{X}=\{x_{1},x_{2},\cdots,x_{N_{t}}\}$ as the offloading decision set where $x_{i}=0$ means task $i$ is computed locally, $x_{i}=1$ means the task $i$ is offloaded to the server. Also, we use $\bm{J}=\{j_{1},j_{2}\cdots j_{N_{t}}\}$ to denote the queue order of the $N_{t}$ tasks that are processed in the server, where $j_{i}=0$ means the task will be computed locally, otherwise $j_{i}$ is the number of computing order in the server. Therefore, the energy consumption and delay to complete the $i$th task is:

where $T_{rea,j_{i}}$ is the time taken by the server to complete the $j_{i}$th task, $T_{com,i}=\frac{n_{i}c}{f_{edg}}$ is the server computing time, $T_{tra}$ is the time used to transmit data to the server. The two goals of the offloading algorithm are to minimize 1) weighted task processing delay, and 2)weighted energy consumption to complete the task. Because the optimization goals are coupled with $\{\bm{X,J}\}$, it is impossible to optimize them independently. We make a trade-off among these two goals and define the problem as:

where $\alpha$ and $\beta$ are weighting parameters, $t(\bm{X,J})=\sum_{i=1}^{N_{t}}\frac{T_{i}-d_{i}}{d_{i}}$, $e(\bm{X,J})=\sum_{i=1}^{N_{t}}E_{i}$.

The objective function is the weighted sum of the system execution delay and the energy consumption. The constraint (5b) guarantees the number of waiting tasks will not exceed $M$, (5c) shows each task’s position in the server wait queue is unique, and (5d) guarantees a task can only be processed locally or in the server. However, this problem cannot be solved efficiently since P1 is an NP-hard problem.

To prove it, we consider a special case where $\alpha$ is 0, $\beta$ is 1, and all tasks are generated in the same slot and are all offloaded to the server. If we consider the transmission delay of a task as the release time of it, $P1$ is equivalent to minimizing $t(\bm{X,J})$ with constraints (5b) and (5c). This is a single machine sorting problem with random processing and release time. Lee[6] proved that it is an NP-hard problem when there are tasks with different processing time and release time that need to be processed on even one machine. Therefore, this special case is an NP-hard problem. Since P1 is an NP-hard problem, we propose a solution by using DRL to solve it effectively.

Since the length of the server’s waiting queue is $M$, we have to sort up to $M$ tasks. There are total $M!$ choices to sort this problem, which is impossible to be solved by exhaustion search. We consider this problem as a special queuing problem that allows queue cuts. If the waiting queue is not full and there are $L$ tasks in the queue ($L<M$), then there are $L+2$ options for the server to handle the task request: 1) reject it; 2) place it in front of the existing $L$ tasks, or 3) place it in the last position of the queue.

If the newly arrived task is not placed at the end of the queue, it will increase the processing time of the existing $L$ tasks. Assuming that the processing delay required by the original $L$ tasks is $T_{o,1},\cdots T_{o,L}$, and the processing delay of the original tasks becomes $T_{n,1},\cdots T_{n,L}$ after a new task arrives, then we define the loss $l_{s}$ caused by the new task to the system as: $l_{s}=\sum_{i=1}^{L}\frac{T_{n,i}-T_{o,i}}{d_{i}}$. When a new task arrives, we can use one-dimensional search to find the best position to minimize the Equation (5a), and arrange the new task in this position.

Since the robots’ motion can be regarded as a stable Markov process, so we can use the DRL method to deal with the problem of task scheduling when robots are moving.

Q-Learning is a classical reinforcement learning method based on state-action pairs (Q-table). An action $a$ in each state $D$ corresponds to a $Q(D,a)$, which represents its expected cumulative reward. In Q-Learning method, we aim to maximize the long term reward which is $Q(D,a)=\sum_{r=0}^{\infty}r_{t}$. According to [7] we can use DRL to approximate this equation as $r_{t}+\varsigma\mathop{\max}\limits_{{a}^{\prime}}Q(D^{\prime},a^{\prime};\bm{\theta})$ , where $\bm{\theta}$ is the parameters of the neural network and $\varsigma$ is a discount factor. Next, we introduce the action space, the state space, and the reward.

According to algorithm 1, the size of the action space is equal to $M+1$, and the action space can be represented as $Action=\{0,1,2,\cdot\cdot\cdot,M\}$. We define the state space $D=\{D_{d},D_{v},D_{l},D_{n},I\}$, where $D_{d}$, $D_{v}$, $D_{l}$, $D_{n}$ are the vectors of $d$, $v$, $l$, $n$ for each task in the queue, respectively, and $I$ is the state information of the task which is currently under processing, and for the first five vectors, the order of the elements is the same as the order of the tasks in the queue. Since we aim to minimize the average cost of all tasks, if we simply put this task in the first position of the waiting queue, it will increase all other tasks processing time in waiting queue which increase the average cost of all tasks. Thus, the reward should also consider the loss $l_{s}$ of cut in, which is $\sum_{i=k}^{L}\alpha E_{add,i}+\beta T_{add,i}/U_{i}$, where $T_{add,i}$ is the extra time the $task_{i}$ should wait because of the cut in. Therefore, the reward of DRL can be represented as:

Next, we show the complexity of developed DRL model with respect to the swarm size. First, the time complexity of our DRL method is $\mathcal{O}(N)$. There are total of 4 layers of fully connected neural networks in DRL, and the number of nodes in each layer is $m_{1},m_{2},m_{3},m_{4}$. Since the one forward calculation of DRL can be regarded as 3 matrix calculation which is constant, and there are $M$ tasks at most in one slot to process, so there are $M$ times calculation is required at most. Therefore, the time complexity is $\mathcal{O}(N)$. Second, the space complexity of our DRL method is $\mathcal{O}(N)$. The number of weights in the neural network that requires space to be saved is equal to $\sum_{i=1}^{3}m_{i}m_{i+1}$. Since $m_{2},m_{3}$ are all constants, $m_{1}$ is proportional to $M$, $m_{4}$ is equal to $M+1$, so the amount of space occupied by the weight increases linearly with the increase of the server’s waiting queue length.