extfieldsofstudy:
Computer Science
Engineering

text:
Indoor UAV scheduling with Restful Task Assignment Algorithm

Research in UAV scheduling has obtained an emerging interest from scientists in the optimization field. When the scheduling itself has established a strong root since the 19th century, works on UAV scheduling in indoor environment has come forth in the latest decade. Several works on scheduling UAV operations in indoor (two and three dimensional) and outdoor environments are reported. In this paper, a further study on UAV scheduling in three dimensional indoor environment is investigated. Dealing with indoor environment\textemdash where humans, UAVs, and other elements or infrastructures are likely to coexist in the same space\textemdash draws attention towards the safety of the operations. In relation to the battery level, a preserved battery level leads to safer operations, promoting the UAV to have a decent remaining power level. A methodology which consists of a heuristic approach based on Restful Task Assignment Algorithm, incorporated with Particle Swarm Optimization Algorithm, is proposed. The motivation is to preserve the battery level throughout the operations, which promotes less possibility in having failed UAVs on duty. This methodology is tested with 54 benchmark datasets stressing on 4 different aspects: geographical distance, number of tasks, number of predecessors, and slack time. The test results and their characteristics in regard to the proposed methodology are discussed and presented.

emerging demand to employ UAVs for indoor operations [9]. For instance, UAVs can be utilized to perform tasks such as inspection and material handling in a manufacturing environment. To fulfill such tasks, the UAV is equipped with an imaging device and a gripper. UAVs perform the tasks at the designated positions with the required equipment. The execution manner of these tasks also considers the total makespan or/and battery consumption. To accomplish such a goal, a schedule of task executions needs to be generated, and the respective instructions to be sent to the UAVs. During the schedule generation, several constraints need to be satisfied to produce a feasible schedule.
The scheduling problem in this paper includes an optimization problem of assigning execution time of tasks in respect to the available limited resources such as UAVs and positions, whose class has been proven to be NP-hard [8]. Furthermore, the planning horizon may include non-determined recharge actions (as needed) during the operations. Unlike in [10], a variable recharge time is employed in this paper. Any sufficient time range (over the defined threshold) can be used for performing a recharge. Apart from that, other actions such as hover and wait on ground may also be included to represent feasible operations. In such a problem, obtaining an optimum solution takes a non-linear computation time in regard to the problem scale. During the numerical experiments (Section 5), benchmark datasets on both lab scale and industrial scale indoor environments are used. In the lab scale environment itself, with small numbers of tasks, hours of computation time are shown insufficient to complete the optimization process. This entails the need of a heuristic-based approach, where a near optimum (good quality feasible) solution is able to be obtained in a reasonable amount of time. Such computation time, together with the exponentially growing one obtained from experiments with IBM ILOG CPLEX, are presented in Section 5.
In [10], the authors developed a methodology which includes the earliest available time heuristic which is incorporated with a metaheuristic algorithm called Particle Swarm Optimization (PSO) to obtain a good quality feasible solution in a quick computation time. The objective in [10] is to find a minimized total makespan. Meanwhile in this paper, the objective of the optimization is to minimize the total energy consumption. The tasks are given time windows, from which can be inferred that as long as the time window constraints are not violated, the execution of the following business process will not be delayed. Hence, optimizing battery consumption become relevant to keep the operational cost minimum, while inducing short flight paths simultaneously. This objective is associated with the awareness of keeping the battery level preserved achieved through the Restful Task Assignment Algorithm (RTAA). Battery is the source of life for the UAV, where battery failure may lead to the failure of the task and the UAV itself. In addition, the map of the operational environment is constructed with directed paths, where the layout is designed to support collision avoidance throughout the operations (described in Section 3). The main contributions in this work are described as follows.

Developed a methodology for safe scheduling which includes:
a novel heuristic based on RTAA for constructing a schedule from a task sequence RTAA promotes the preserved battery level of the UAVs throughout the operations. The tendency of the preserved battery level avoids UAVs from suddenly dropping out of the game due to an unforeseen marginal remaining battery level. an incorporation of RTAA-based heuristic with PSO to obtain a good quality feasible solution in a short computation time PSO parameters used in Section 5 are inspired by the pilot study in [10], where parameter analysis was extensively performed. a directed-path three-dimensional indoor environment map The tasks are to be executed in a particular three-dimensional indoor environment, which is defined in a map. In the map, the paths are constructed in a directed manner, also in coherent with the UAV flying behavior, which altogether supports collision avoidance during the operations. 2. Performed numerical experiments and analysis on the characteristics of the resulting schedules on multiple datasets. There are 54 benchmark datasets stressing on different aspects, i.e. geographical distance, number of tasks, number of predecessors, and slack time. The characteristics analyzed from the resulting schedules are the total energy consumption, makespan, and computation time. The remainder of this paper is organized as follows. In Section 2, some related works on scheduling tasks with time windows and UAV scheduling in indoor environment are reviewed. Then, in Section 3, the formulation of the problem in this paper is presented. In Section 4, RTAA and its incorporation with PSO are described. Afterwards, the conducted numerical experiment is presented and analyzed in Section 5, followed with the conclusion in Section 6.

Literature review
Scheduling has been a consistently demanding research interest which involves numerous scientists and specific problems in the optimization area. In 1988, a study on deciding the minimum fleet size for minimum traveling salesman problem with time windows [5] was conducted to be integrated into the previous related work [6] in 1986. The evaluation of the optimum number of fleet at the first node of a branch-and-bound tree will reduce the number of infeasible routes and the size of the tree to be explored. This approach, wherein an optimal solution is aimed at, is suitable for scheduling tasks significantly prior to the execution where changes towards the schedule during the execution are less likely to happen, e.g. in school bus transportation problem. When different numerous tasks are performed by multiple agents on a daily basis, where the tasks may come until right before the operation is started, a non-exhaustive near optimal search within a short time becomes more practical.
A work on optimization using column generation approach for the vehicle routing problem with time windows [3] was carried out in 1992, where four essential rules for reducing the time window width were introduced as a part of the methodology. Rules 2 and 3 can be applied when there is only a single agent or there is no position occupation during the task execution. For instance, when a time window of a predecessor is trimmed upfront because the successor cannot be started sooner anyway (regardless of the predecessor's sooner completion time), the required position to be accessed may be occupied by another agent later. Executing the predecessor earlier (and the successor is not immediately executed afterwards) may become its only option to satisfy the given time window constraint. In regard to rule 1 and 4, the respective time window examples in [3] which may lead to some unfeasible task assignments is not the focus of this paper, and hence such a condition is not reflected in the benchmark datasets (they are discussed later in Section 5).
In the following years, heuristic-based approach is viewed to remain as a viable alternative for solving large-scale optimization problem in a short time [4]. For scheduling problem with time windows, a study on backtracking techniques for the job shop scheduling constraint satisfaction problem was conducted. To come up with a feasible solution as fast as possible, one essential remark to keep in mind is the expensive computation when a large complex conflict is met, for proving that some particular assignments need to be undone.
The beginning of aircraft scheduling problem [2] was mainly flagged in 1997, using branch-and-bound approach supported by column generation technique. The goal is to gain a substantial profit improvement over the existing airline's solution. The nature of such problem allows a longer computation time which is deemed reasonable. Recently, the application of aircraft has been widely explored, especially Unmanned Aerial Vehicle (UAV) into various application domains in both outdoor and indoor environments [9]. It can be deduced that a system of UAV application mainly comprises environment (mapping and positioning system), Unmanned Aerial System (UAV, ground station, control module), and task (scheduling). Those elements are affecting while enabling one another simultaneously. One problem instance of such kind involves numerous tasks and constraints to be considered in the scheduling process. This brings the appeal of heuristicbased approach being able to solve the problem with a good quality feasible solution in a reasonable time. A modified receding horizon task assignment heuristic which focuses on scheduling split jobs of long surveillance missions to maintain a persistent UAV operations was conducted [11], where an indoor system prototype was tested in [19]. Another heuristic-based is also used for UAV scheduling in two-dimensional environment with no constraint [16]. Under the metaheuristic family, PSO has been investigated for job shop and flexible manufacturing (where the employment of unmanned vehicles is found) scheduling problems in [10,13,14], and it is postulated to be effective and efficient. Such a metaheuristic algorithm is fast and easy to implement [13,20]. Such an approach towards multiple tasks scheduling problem for UAV operations in indoor environment was piloted in [10]. The objective is to produce a schedule with a minimized total makespan in a short time. The pilot work serves as the ground to identify further issues and the respective solution -which are discussed in the following sections in this paper.

Problem definition
Numerous task executions by UAVs in indoor environment require a thorough scheduling mechanism to reduce cost (e.g. time and energy) and promote safety towards both the users (human-labors) and the system itself (e.g. UAVs, indoor infrastructure). In the previous work [10], the total time of the operation is sought to be minimized to save both time and financial cost, and to allow the following business process to continue (e.g. surface inspections of the wind turbine blades need to be done before the trucks are booked for transporting them). In this study, the goal is to produce a schedule of task executions with a minimized total energy consumption and preserve the battery level throughout the operations. Additionally, a task has a time window attribute, in which the task must be executed. Furthermore, when dealing with UAVs in indoor environment, no sudden out-of-power is expected since it may lead to human injuries or infrastructure damages. Complying to these conditions, a new heuristic-based method which minimizes the total battery consumption with the awareness of keeping the battery level preserved is required; not strictly utilizing the UAV without recharge until the battery is depleted. This is the limitation that is exposed in [10], where a full recharge is done only when the battery is completely or nearly depleted that the UAV can't perform its following action. An instance of a task dataset is depicted in Table 1. Each task data consists of a task identifier, a start position, an end position (if it is an inspection task, then the value is the same as the start position; i.e. task 1 , 2 , 5 , 7 , 8 ), a processing time, a release date, a due date, and a predecessor list. In this study, the benchmark datasets used in Section 5 are tasks with time windows, while a support for assigning tasks without time window is induced in the proposed methodology -discussed later in Section 4. A characteristic which is introduced by the time window attribute is slack time. Slack time indicates the room where the execution time may be shifted around within the time window. For instance, task 10 in Table 1 has a time window of 281 seconds from 726∼1007, and a slack time of (281-44=)237 seconds-since the processing time of task 10 is 44 seconds.  Task ID)   1  c3  c3  10  726  1077  8  2  c1  c1  10  1007  1379  10  3  d4  f2  39  1429  1745  7  4  e2  b2  42  827  1230  9  5  d4  d4  10  0  382  -6  f1  e2  35  1428  1843  7  7  d1  d1  10  1007  1429  9;10  8  b3  b3  10  292  726  -9  c4  b3  35  382  827  5  10  a2  c2  44  726  1007  8 There are two types of task: inspection and material handling tasks. They expose 3 types of actions: perform task -material handling, perform task -inspection, and fly to. On top of that, there are 3 additional types of action that the UAV perform throughout the operations: hover, wait on ground, and recharge. Those actions are depicted in Table 2. The time for performing material handling is composite, where it comprises 30 seconds for loading and unloading the payload, and a variable flying time from the start to the end position. Such a level of task abstraction is needed to reduce the complexity of the computation. Throughout the operations, actions of perform task (material handling and inspection), fly to, and hover are the contributing factors in the battery consumption. Furthermore, an example of schedule which describes the solution representation for the addressed problem is depicted in Figure 1. It corresponds to the task dataset in the aforementioned Table 1. A schedule consists of the assigned tasks and the other actions, whose composition conforms to the UAV state machine depicted in Figure 2. Upon the completion of its last task, the UAV goes back to a nearest recharge station by default -such an action is not included in the schedule, while the assurance of having enough battery to go back is taken into accountthe imposing mechanism is explained later in Section 4.2.   Figure 3. Each location of interest is indicated by a letter, where positions in the same location are distinguished by a number (following the letter). The green nodes are the recharge locations, where recharge actions take place. The established directed paths (illustrated in Figure 4b) are also designed to avoid potential deadlock or collision. This means, with a sensor detecting the area forward where the UAV is going to fly, a short wait upon another UAV ahead will avoid collision among UAVs. In another word, such a situation in Figure 4a does not happen, where the UAVs collide or wait for one another continuously (deadlock). The constraints of the task scheduling problem in this study are mentioned as follows. 1. A task is executed once by one UAV. 2. A task is executed within the given time window. 3. A recharge station can be occupied by multiple UAVs.
The recharge station has no limited space due to the technology advancement in the space efficient battery recharge or even replacement platform [21], and a small size of UAV fleet (e.g. ≤10) may cover the most instances of UAV application in indoor environment. The recharge time for a depleted battery with the capacity of 20 minutes is 45 minutes. 4. A non-recharge-station position can be occupied by at most one UAV at a particular time. 5. A UAV can only execute at most one task at a time. 6. A UAV may only land at a recharge station. 7. The battery level of a UAV must never be depleted at any non-recharge-station position. 8. The battery of each UAV is fully charged in the beginning of the planning horizon. 9. A task can only be executed after all its predecessors are completed. 10. There is no cyclic nor redundant precedence relationship.
if a recharge is conducted by UAV k before task i is executed and task i is operationally preceded by task j 0 otherwise if no recharge is conducted before task i is executed by UAV k and task i is operationally preceded by task j 0 otherwise if a flight is required from s k 0 before UAV k executes task i 0 otherwise f j : start time of a task which is operationally preceded by task j f k ij : a i which is penalized with a large value M when a i ≤ z j or task i (or j) is not executed by UAV k f ij = 1 if a i < z j 0 otherwise g k ij : battery consumption when no recharge takes place before the execution of task i, which is preceded by j, by UAV k E : total battery consumption Note: Task i is operationally preceded by task j if task i is scheduled to be executed right after task j by the same UAV; it is different from precedence rule.
Objective function: minimize E Subject to: 1 -end time is the summation of start time and processing time of the task 2 -the start time and end time of a task shall not violate its time window 3 -every task is executed once by one UAV 4 -a UAV can only execute one task at a time 5 -battery condition that will trigger recharge as necessary 6 -no multiple tasks are executed at the same position at a particular time 7 -define what recharge does to the battery level and how the battery is consumed 8 -set the battery to be consumed for the flight from the UAV's initial position towards the first task; which is an exception case to the defined constraints for battery consumption in 14 and 15.
9 -determine the start time of a task which is the first task of a particular UAV 10 -operational precedence relationship indicates task i is executed right after task j by the same UAV; j operationally precedes i 11 -a task can operationally precede and be operationally preceded by at most one other task 13 -no cyclic operational-precedence 14 -guaranteed feasible recharge time in the schedule 16 -the sum of all UAVs' battery consumption does not exceed the total battery consumption i∈N k∈V The developed MILP model is solved for small-scale problems, and the data is shown later in Section 5. The exponentially growing computation time indicates the need of a heuristic-based approach which is capable of solving the large-scale problem within a reasonable amount of time. Such a methodology is developed in this study, and it is discussed in the following section.

Methodology
The proposed Restful Task Assignment Algorithm is described through Algorithm 3∼5 later in this section. To help to minimize the battery consumption while parallelizing task executions when deemed fit (which may lead to a shorter total execution time), Algorithm 3 is presented. The time window attribute on the task encourages the usage of Algorithm 4: Backward Fragment Placement Algorithm (BFPA) to quickly find a feasible solution if it exists and increase the system's robustness. Moreover, this method tends to preserve the battery level, since some empty time ranges in between the task executions can be used for having recharge actions. The detailed procedure is described in Section 4.2. A support for assigning tasks which couldn't be assigned in BFPA and those without time window is provided by Algorithm 5: Forward Fragment Placement Algorithm (FFPA). In respect to the route query between positions, Dijkstra's Algorithm [7] is employed in the map module.
RTAA is then incorporated with Particle Swarm Optimization (PSO), where task sequences from the initial swarm and the produced mutations throughout the whole search iterations are the inputs for RTAA. The mechanism of PSO is depicted in Section 4.1, followed by the description of RTAA in detail in Section 4.2.

Particle Swarm Optimization Algorithm
PSO is an optimization algorithm which falls under the category of metaheuristic approach. It allows explorations to areas which may not look promising in the beginning of the search, alienating it from getting trapped in a local optimum solution. The incorporation of PSO performs the battery consumption minimization process during a reasonable computation time. The calculation of the total battery consumption of a schedule is contributed only by task executions, flight actions (among positions of task execution and recharge stations), and hover actions. The PSO algorithm is depicted in Algorithm 1, where more details of the incorporation with such a problem nature of this paper can be found in [10].

Algorithm 1 Particle Swarm Optimization Algorithm
Input: Initial Swarm (swarm) Output: schedule of tasks on UAVs (schedule) 1: Initialize (parameters, swarm, local best and global best) 2: while stop condition not met do 3: velocity ← updateVelocity(swarm, velocity, local best, global best); 4: swarm ← updateSwarm(swarm, velocity); 5: localBest ← getLocalBest(fitness(swarm), localbest); 6: globalBest ← getGlobalBest(localBest, globalBest); 7: generation++; 8: end while The initial swarm has a role in placing initial starting points [12] throughout the solution space. There are 10 priority rules used in the initial swarm generation. Eight of them are addressed in [10], while two other rules in regard to the position occupation are introduced in this paper. Those are most and less occupied position rules, task will be sorted based on the projected-occupation-load of its execution position in ascending and descending manner. For material handling task, these two rules see the start position as the execution position. The example of sequences (particles) in the initial swarm created through the priority rules in regard to the dataset in Table 1 is depicted in Table 3.

Restful Task Assignment Algorithm
The scheduling algorithm is depicted by Algorithm 2∼5. The encapsulation of sub-methods performed in Algorithm 3∼5 provides a more clear top-constitutionalview of the heuristic approach depicted in Algorithm 2: Restful Task Assignment Algorithm (RTAA). The main idea of RTAA is to promote the existence of a continuous free timespan which can be used by the UAV to have a recharge. The algorithm takes input from a sequence of tasks created initially through the priority rules or update of position during a particular iteration. In line 1, the tasks are grouped based on the position occupation time where the task will start. For inspection tasks, it also acts as the position where the task will take place. Through the formed group, the positions will be ranked in a descending order; from the most occupied one to the most idle one. From line 3∼22, a method of creating a preliminary schedule without recharge action is depicted. Based on the ranked position list, tasks in the group will be iterated and tried to be assigned to a UAV to be executed at a particular time range. This provides the structure of the schedule by putting the tasks which are less flexible (i.e. to be executed at one position as many others may yield a smaller execution time range). In line 7, the task is put into schedule in a backward manner. Following the successful assignment, the record of UAV occupation-timestamp fragments (UOF) and position occupationtimestamp fragments (POF) are updated.
Tasks which couldn't be assigned previously and those without time windows will be attempted to be scheduled in line 14∼22. Here, the tasks are scheduled on the available time range according to the UOF and POF. When there are multiple possible placements of time fragment in the available time range, the task is assigned at the soonest execution time. If there is a task which still can't be assigned in this attempt, a return value is returned indicating that another sequence should be checked since the current one does not yield a complete feasible schedule for the given set of tasks. In this manner, assuming that the given tasks are rational, the computation time can be minimized. The distinction of time fragment and time range is depicted in Figure 5. After the preliminary schedule is constructed, the insertion of recharge, hover, and wait-on-ground actions is performed (line 23∼30). In this regard, a minimum recharge time shall be defined, to determine the amount of time that is worth (long enough) to be used for a recharge action. On the other hand, if the minimum recharge time is too long, then the potential time that actually can be used for recharging the battery would be wasted. The recharge insertion procedure looks for available time ranges which are not used for any task execution and at least equal to or greater than the defined minimum recharge time.
In every attempt to put a task into the schedule, indicated by '+' throughout the pseudocode (Algorithm 4 line 8 + and Algorithm 5 line 7 + ), there is a check of the required flight's execution time in respect to the adjacent task(s)'s and possibility to put a recharge action when applicable or necessary. This means, there will be no insufficient time for the UAV to fly from the end position of a preceding task to the start position of the successor task. Furthermore, there will be no insufficient battery value since a task will not be assigned at a particular time fragment when the formed sequence of tasks does not leave enough battery to go at least to the nearest recharge station. During this process, the time fragment for the task execution is ensured not to overlap with the existing UAV occupation time fragments. The reason why it is not done together with the trimming based on the position occupation time fragments is because of the dynamic flights of the UAVs between positions (where a recharge action might be replaced by a hover and a task execution -at a latter task assignment) causing frequent changes throughout the overall schedule construction. On the other hand, position occupation time fragments are stagnant once the assignments are made, regardless of the previous or the following assignments.
The distinction on the characteristic of UAV occupation and position occupation fragments is depicted in Figure 6. Let's assume that during the schedule construction, several task assignments are performed, where task 1 , 3 , and 4 are assigned sequentially. In figure 6b, a particular position occupation time fragment is depicted to be stagnant once the respective task is assigned. However, the UAV occupation task is depicted otherwise in Figure 6c. In the beginning, a material handling task 1 is assigned-where the time fragments for flight from the recharge station to A (R∼A), a load (L A ), flight from A to B (A∼B), and unload (U B ) are put at their calculated time ranges. When task 3 is assigned to the schedule, assuming that the related time-fragments satisfy the considered constraints, a time fragment of flight from the end position of task 1 : B to the start position of task 3 : D is assigned to the respective time-range. Afterwards, task 4 is assigned according to its time window, and it occupies the time range between the end of task 1 and the start of task 3 . This means that the time fragment of flight B∼D is obsolete now. Instead, fragments of flight B∼A, capturing inspection image at A, and flight A∼D are assigned in the respective time range. In another word, every assigned occupation time fragment of UAV 1 may change over time during the schedule construction.  tasks ← taskGroup.get(position) 5: for t in tasks do 6: if hasTimeWindow(t) then 7: isScheduled ← BFPA(posOccupationF ragments, uavOccupationF ragments, sched, t) 8: if isScheduled then 9: seq.remove(t) 10: end Prior to the task assignment, a sorting of the preferred UAV list for performing a particular task is done. This process is done based on the precedence relationships of the task to be assigned (1,2,4,5) and the possessed workload (line 3). The motivation behind the utilization of precedence relationship here is the tendency of the successor tasks being able to be executed immediately after its latest predecessor is done.

Algorithm 3 Sort the preferred UAV list
Input: a list of all UAV IDs (uavIDs), UAV occupation fragment (uavOccF ragments), current schedule (sched), upcoming task to be assigned (t) Output: a sorted list of UAV IDs -from the most preferred one to the least (pref U AV s) 1: uavOnDutyBef ore ← getUAVofTheLatestPredecessorIfExist(t, schedule) 2: uavOnDutyAf ter ← getUAVofTheEarliestSuccessorIfExist(t, schedule) 3: pref U AV s ← sortUAVIDsBasedOnCurrentWorkload(uavOccF ragment, uavIDs) 4: moveUAVIDToTheFrontOfList(pref U AV s, uavOnDutyAf ter) 5: moveUAVIDToTheFrontOfList(pref U AV s, uavOnDutyBef ore) 6: return pref U AV s The details of the first task assignment attempt is depicted in Algorithm 4: Backward Fragment Placement Algorithm (BFAP). In line 4∼7, possible time fragments for the task to be assigned at are listed. They are obtained by trimming the fragments of the original time window of the given task which overlap with the current record of POF. The trimming based on the end time of a predecessor and the start time of a successor is a consequence of the design of Algorithm 2, where a left to right (time-wise) task assignment procedure is not a must.
In line 8 + , the task is attempted to be assigned to the schedule in a backward manner to give an enhanced number of possibilities for the other tasks to be arranged without violating the given time window constraints. Once the task is assigned, the occupation fragments of the respective UAV and position are updated (line 10). Furthermore, when assigning tasks with the same precedence level, one with less slack may need to be assigned before the other(s) or maybe the other way around to yield a feasible schedule -as depicted in Figure 7. Task 12 has less slack than 11 and one may prefer to assign 12 before 11 . This results in the next task assignment attempt becoming infeasible (depicted in Figure 7b), while the other way around in Figure 7c is feasible. This is where the role of task sequence representation in the incorporated Particle Swarm Optimization comes in. The various task sequences enable a flexible exploration even towards an unlikely area. Additionally, it also promotes a quick exploration in a large solution space. In this manner, when there is no feasible schedule found, one can conclude that the given tasks (with the defined time windows) are too tight for the available resources (i.e., UAVs and positions). This is also supported by the condition where the tasks are not ranked based on their slack time before the task assignment -such treatment demotes the exploration during the search.  Get a list of UAVs sorted based on defined preferences: executor of a predecessor of task t, executor of a follower of task t, least loaded UAV 5: predBasedT imeW in ← trimTimeWin(t.timeWindow, sched) Trim time window based on the scheduled predecessor(s) and follower(s) 6: f reeStartP osF ragments ← trimOccupiedTimeRange(predBasedT imeW in, posOccupationF ragments.get(t.startPos)) 7: f reeEndP osF ragments ← trimOccupiedTimeRange(predBasedT imeW in, posOccupationF ragments.get(t.endPos)) Attempt to put the task into the schedule in a backward manner: 8: isScheduled ← assignTaskBackward(f reeStartP osF ragments, f reeEndP osF ragments, pref U AV s, sched, t) + 9: if isScheduled then 10: updateOccupationFragments(posOccupationF ragments, uavOccupationF ragments, sched) Update position and UAV occupation fragments according to the recently scheduled task 11: end if

12: return isScheduled
After the attempt of assignment of tasks with time windows in Algorithm 4 is performed, the unassigned ones or tasks without time window will be attempted to be assigned based on Algorithm 5: Forward Fragment Placement Algorithm. In this second attempt, several tasks with time window assigned in a tardy manner may be found when the respective time range allows the task to still meet the defined precedence relationships. However, on the opposite, a task with time window shall not be assigned before its release date. This assumption is made according to the accommodated task where the existence of lead task may fail the purpose of the task itself. For example, an inspection task is scheduled to be performed in the middle of the day: when a wind turbine blade would have been manufactured further. In such a situation, another (lead) inspection task executed in advance in the morning (before the given time window in the middle of the day) gives no contribution to the original intention of that task.
Generally, in the second attempt, the task assignment based on Algorithm 5 is attempted on the left side of a particular existing fragment (line 6). When there is a flexibility in the available time range, the soonest feasible time fragment will be chosen over the others (line 7). Such task assignment manner is promoted by the characteristic of Algorithm 4 where it tends to leave an empty area on the left-side of the (scheduled) task fragment. Hence, through Algorithm 5, this condition will be evened out by the insertion of the remaining unassigned tasks and potential recharge actions. In line 15, unscheduled tasks will be lastly attempted to be assigned after the last task in the existing schedule of a particular UAV when possible -satisfying the precedence relationships.

Algorithm 5 Forward Fragment Placement Algorithm
1: pref U AV s ← getPreferredUAVs(uavOccupationF ragments, sched, t) Get a list of UAVs sorted based on defined preferences: executor of a predecessor of task t, executor of a follower of task t, least loaded UAV 2: predBasedT imeW in ← trimTimeWin(t.timeWindow, sched) Trim time window based on the scheduled predecessor(s) and follower(s) Attempt to put the task into the schedule in a forward manner: 3: TRY FFPA: 4: for uav in pref U AV s do 5: for st in sched.get(uav) do 6: f reeT imeF ragment ← getFreeFragmentOnTheLeftSideOfScheduledTask(st, posOccupationF ragment) Based on position occupation time fragments 7: isScheduled ← assignTaskForward(f reeT imeF ragment, sched, t) + 8: if isScheduled then 9: updateOccupationFragments(posOccupationF ragments, uavOccupationF ragments, sched) Update position and UAV occupation fragments according to the recently scheduled task 10: break

Numerical Experiment
The developed MILP in Section 3 is attempted to be solved in IBM ILOG CPLEX, with 3 UAVs and up to 9 tasks. It is run on an Intel Core i7 processor (2.9 GHz) with 32 GB of RAM. The computation time of CPLEX grows exponentially as shown in Table 4. It reaches more than 2.5 hours after only 8 tasks, and this is significantly longer than the heuristic-based computation time for 100 tasks (presented later in this section). This condition essentially drives the need of pursuing a heuristic-based approach to obtain a good quality solution in a reasonable time.
The proposed methodology has been benchmarked by 54 datasets generated based on the flight demonstrations at the lab facility of the Department of Mechanical, Production and Management Engineering. The datasets have different characteristics, formed by different levels of four parameters: geographical scale, number of tasks, predecessor distribution, and slack time distribution. The summary of the task characteristics interpolated from both lab scale and industrial scale datasets can be illustrated in Figure 8.  Figure 8, there exist tasks with 3 or 4 predecessors in a particular dataset. The addressed parameter determines that the number of predecessors in a dataset satisfies the normal distribution with x = 0∨1∨2 and σ = min(1, x) -not the exact number of predecessors for each task. 4. For each number of predecessor distribution, there are 3 slack time distributions: 300, 600, and 1200 seconds. As depicted in Figure 8, there are some tasks with slack time of at least 100 and up to 1395 seconds. The addressed parameter determines that the slack time in a dataset satisfies the normal distribution with x = 300 ∨ 600 ∨ 1200 and σ = x/5 -not the exact slack time for each task. 5. Each dataset is used in a scheduling scenario which is run 20 times, whose results can provide a good quality observation.  In alignment with the restful characteristic of Algorithm 2, the overall battery level is desired to be preserved throughout the operations. The battery level of each UAV after each task execution from every feasible schedule constructed during the search (iterations) is recorded, and the cumulative data is depicted through histograms in Figure 9. It is portrayed that the battery level of the UAVs has the tendency of being in a sufficiently preserved level. This condition applies for both lab scale and industrial scale environment, which shows the scalability of the proposed methodology. The set of learning coefficients used for the PSO algorithm is c 1 =1, c 2 =2, with 40 particles of initial swarm, 40 iterations, and a stop criteria of 10 no-improvement iterations -this is inspired by the pilot study conducted in [10]. In this study, the experiment purpose is to stress-test the methodology. Hence, the solution space may get vast in the used datasets, stressing exploration rooms not only for PSO, but also for RTAA. Each sub-figure in Figure 10 represents 180 attempts, which correspond to a particular geographical scale of the environment and number of tasks. There are 9 settings for a particular set of geographical scale and number of tasks, depicted in Table 5. The battery consumption peaks are at setting 1, 4, and 7 for all sub-figures, where the slack time is 300. This behavior is caused by the situation where there is less time in between task executions, where UAVs will be required to hover and wait; since recharging at the recharge station within a very short period will be insignificant or even waste the battery more (due to the flights from and to the recharge station). In addition, it is depicted that the exposure of Algorithm 3 in Algorithm 4∼5 (and Algorithm 2 as a whole) may reduce the battery consumption in the produced schedule through the existence of precedence relationships. The results of the total battery consumption optimization in 1080 scheduling attempts are depicted in Figure 10, and the numerical data of average battery consumption is presented in Table 6.   In regard to the computation time, it tends to converge in the reasonable computation time area. The computation time of every 20 scheduling attempts of a particular dataset is recorded, and the respective overview for the benchmark datasets is depicted in Figure 11. In Table 7, the average computation time of every dataset is presented.

Conclusion
UAV scheduling problem in indoor environment has been emerging with various challenges to solve. In this paper, a study on safe UAV scheduling is conducted, where tasks with time windows are performed by multiple UAVs in indoor environment. A heuristic approach based on RTAA is proposed. Furthermore, an incorporation of PSO with RTAA is performed, where two additional priority rules are proposed apart from the ones utilized in the pilot study [10]. The study involves 54 benchmark datasets stressing on different aspects: geographical distance, number of tasks, number of predecessors, and slack time. From the analysis of the results, it can be deduced that the proposed methodology is very effective for producing a restful schedule in a reasonable amount of time. This depicts a safe UAV scheduling, where the battery level is shown to be sufficiently preserved throughout the operations. On top of that, RTAA (specifically Algorithm 3,4, and 5) which is incorporated with PSO generates a drive for the search to obtain minimum total battery consumption. This methodology is also shown to be scalable for both lab scale and industrial scale indoor environments.

Conflicts of Interest
The authors declare that they have no conflicts of interest.


InverseFaceNet: Deep Single-Shot Inverse Face Rendering From A Single Image

We introduce InverseFaceNet, a deep convolutional inverse rendering framework for faces that jointly estimates facial pose, shape, expression, reflectance and illumination from a single input image in a single shot. By estimating all these parameters from just a single image, advanced editing possibilities on a single face image, such as appearance editing and relighting, become feasible. Previous learning-based face reconstruction approaches do not jointly recover all dimensions, or are severely limited in terms of visual quality. In contrast, we propose to recover high-quality facial pose, shape, expression, reflectance and illumination using a deep neural network that is trained using a large, synthetically created dataset. Our approach builds on a novel loss function that measures model-space similarity directly in parameter space and significantly improves reconstruction accuracy. In addition, we propose an analysis-by-synthesis breeding approach which iteratively updates the synthetic training corpus based on the distribution of real-world images, and we demonstrate that this strategy outperforms completely synthetically trained networks. Finally, we show high-quality reconstructions and compare our approach to several state-of-the-art approaches.

Introduction
Inverse rendering aims to reconstruct scene properties such as geometry, reflectance and illumination from image data. This reconstruction is fundamentally challenging, as it inevitably requires inverting the complex real-world image formation process. It is also an ill-posed problem as certain effects, such as low-frequency reflectance and illumination, can be indistinguishable [34]. Inverse rendering, for example, enables relighting of faces by modifying the scene illumination and keeping the face reflectance and geometry fixed.
Recently, optimization-based approaches for inverse face rendering were introduced with convincing results [2,14,21,26,45]. One of the key ingredients that enables to disentangle pose, geometry (both related to shape and facial expression), reflectance and illumination are specific priors that constrain parameters to plausible values and distributions. Formulating such priors accurately for real faces is difficult, as they are unknown a priori. The priors could be learned by applying inverse rendering to a large dataset of real face images, but this is highly challenging without having the priors a priori.
We take a different approach to avoid this chicken-andegg problem. Instead of formulating explicit priors, we directly learn inverse face rendering with a deep neural network that implicitly learns priors based on the training corpus. As annotated training data is hard to come by, we adopt an analysis-by-synthesis approach that starts from a large dataset of synthetic face images with known model parameters (geometry, reflectance and illumination). This is similar to Richardson et al.'s approaches [35,36], but the parameter distribution of this training data does not match that of real-world faces and environments. As a result, the learned implicit priors are rather weak and do not generalize well to in-the-wild images. In contrast to previous approaches, InverseFaceNet for the first time also includes color reflectance and illumination. We furthermore significantly improve the implicitly learned priors by continuously updating the training corpus based on the distribution of real-world imagery using breeder learning inspired by Nair et al. [32]. The key idea is to apply the latest version of the inverse face rendering network to real photographs, to estimate the corresponding face model parameters, and then to create synthetic face renderings for perturbed (but still known) parameter values. This way, we create additional synthetic training data that better reflects the real-world distribution of face model parameters, and our network learns this distribution over time. Our experiments demonstrate that our approach greatly improves the quality of regressed face models for real face images compared to approaches that are trained exclusively on synthetic data.
The main contribution of our paper is InverseFaceNeta fast, deep, single-shot inverse face rendering network that estimates pose, shape, expression, color reflectance and illumination from just a single input image in a single forward pass, and is multiple orders of magnitude faster than previous optimization-based methods estimating similar models. To improve the accuracy of the results, we further propose a loss function that measures model-space distances directly in a modified parameter space. We further propose analysis-bysynthesis breeder learning to produce labeled training data following real-world parameter distributions, which leads to significantly improved reconstruction results for in-the-wild face photos.

Related Work
Reconstruction of faces and their appearance has been studied extensively, so we only review the most relevant subset of this vast literature.
Inverse Rendering (of Faces) The goal of inverse rendering is to invert the graphics pipeline, i.e., to recover the geometry, reflectance (albedo) and illumination from images or videos of a scene -or, in our case, a face. Early work on inverse rendering made restrictive assumptions like known scene geometry and calibrated input images [34,49]. However, recent work has started to relax these assumptions for specific classes of objects such as faces. Deep neural networks have been shown to be able to invert simple graphics pipelines [24,32], although these techniques are so far only applicable to low-resolution grayscale images. In contrast, our approach reconstructs full-color facial reflectance and illumination, and geometry. Aldrian and Smith [2] use a 3D morphable model for optimization-based inverse rendering. They sequentially solve for geometry, reflectance and illumination, while we jointly regress all dimensions. Thies et al. [45] recently proposed a real-time inverse ren-dering approach for faces that estimates a person's identity and expression using a blendshape model with reflectance texture and colored spherical harmonics illumination. Their approach is designed for reenactment and is visually convincing, but relies on non-linear least-squares optimization, which requires good initialization and a face model calibration step from multiple frames, while our approach estimates a very similar face model in a single shot, from a single inthe-wild image, in a fraction of the time. Inverse rendering has also been applied to face image editing [30], for example to apply makeup [26,27]. However, these approaches perform an image-based intrinsic decomposition without an explicit 3D face model, as in our case.
Face Models The appearance and geometry of faces are often modeled using 3D morphable models [4] or active appearance models [11]. These seminal face models are powerful and expressive, and remain useful for many applications even though more complex and accurate appearance models exist [22]. For example, Booth et al. [5] extend 3D morphable models to "in-the-wild" conditions, and deep appearance models [12] extend active appearance models by capturing geometry and appearance of faces more accurately under large unseen variations. We describe the face model we use in Section 4.

3D Face Reconstruction
The literature on reconstructing face geometry, often with appearance, but without any illumination, is much more extensive compared to inverse rendering. We focus on single-view techniques and do not further discuss multi-view or multi-image approaches [17,37,43]. Recent techniques approach monocular face reconstruction by fitting active appearance models [1,12], blendshape models [6,13,14], multi-linear face models [35,36,41,46], or mesh geometry [19,25,37] to input images or videos. Shading-based surface refinement can extract even fine-scale geometric surface detail [8,14,19,36,37]. Many techniques use facial landmark detectors for more robustness to changes in the head pose and expression, and we discuss them in the next section. A range of approaches use RGB-D input [e.g. 28,44,48], and while they achieve impressive face reconstruction results, they rely on depth data which is typically not available for in-the-wild images or videos.
Deep neural networks have recently shown promising results on various face reconstruction tasks. In a paper before its time, Nair et al. [32] proposed an analysis-by-synthesis algorithm that iteratively explores the parameter space of a black-box generative model, such as active appearance models (AAM) [11], to learn how to invert it, e.g., to convert a photo of a face into an AAM parameter vector. We are inspired by this breeding approach and incorporate a similar strategy into our training process (see Section 7) to make our technique more robust to unseen inputs, in our case real photographs. Richardson et al. [35] use iterative error feedback [9] to optimize the shape parameters of a grayscale morphable model from a single input image. Richardson et al. [36] build on this to reconstruct detailed depth maps of faces with learned shape-from-shading. Their approaches are trained entirely on synthetic data [4]. Tran et al. [46] train using a photo collection, but their focus lies on estimating morphable model parameters to achieve robust face recognition. In contrast to these approaches, ours not only recovers face geometry and texture, but a more complete inverse rendering model that also comprises color reflectance and illumination, from just a single image without the need for iteration.
Facial Landmark Detection Many techniques in 3D face reconstruction, including ours, draw on facial landmark detectors for robustly identifying the location of landmark keypoints in the photograph of a face, such as the outline of the eyes, nose and lips. These landmarks can provide valuable pose-independent initialization. Chrysos et al. [10] and Jin and Tan [20] provide two recent surveys on the many landmark detection approaches that have been proposed in the literature. However, none of these techniques works perfectly [42]: facial hair, glasses and poor lighting conditions pose the largest problems. In many cases, these problems can be overcome when looking at video sequences instead of single images [33], but this is a different setting to ours.

Overview
We propose a single-shot deep inverse face rendering network that learns the pose, shape, expression, skin reflectance and incident illumination from a single input image of a face.
To this end, we first detect a set of 66 2D facial landmarks [39], see Figure 2. We use the landmarks to segment the face from the background, and mask out the mouth interior to effectively remove the parts of the image that cannot readily be explained by our model. The masked face is input to our deep inverse face rendering network (Section 6). We generate purely synthetic facial imagery using a parametric face and image formation model (Section 4). Our training corpus is sampled from the probability distribution of this model (Section 5). We apply parameter breeding by analysisby-synthesis (Section 7) to bootstrap a synthetic training corpus that approximates the real-world distribution of faces and scene illumination. This leads to higher quality reconstruction results (Section 8). Finally, we discuss limitations (Section 8.4) and conclude the paper (Section 9).

The Space of Facial Imagery
We parameterize face images using m = 350 parameters: Here, R specifies the global rotation (3 parameters (27). Note that we do not include translation as our network works on consistently segmented input images (see Figure 2 and Section 3). In the following, we describe all parameters and the underlying models in detail.

Multi-Linear Face Model
We employ a multi-linear face model to parameterize facial geometry where V is the number of vertices of the underlying manifold template mesh. The geometry vector F [g] stacks the V 3D coordinates that define the mesh's embedding in space. Similarly, the reflectance vector F [r] stacks the RGB reflectance values. The space of facial geometry is modeled by the shape θ [s] ∈ R Ns and expression θ [e] ∈ R Ne parameters: The spatial embedding is modeled by a linear combination of orthonormal basis vectors b [s] i and b [e] j , which span the shape and expression space, respectively. a [g] ∈ R 3V is the average geometry of a neutral expression, the σ [s] i are the shape standard deviations and the σ [e] j are the standard deviations of the expression dimensions.
Per-vertex skin reflectance is modeled similarly using a small number of reflectance parameters θ [r] ∈ R Nr : Here, b [r] i are the reflectance basis vectors, a [r] is the average reflectance and the σ [r] i are the standard deviations. The face model is computed from 200 high-quality 3D scans [4] of Caucasians (100 male and 100 female) using PCA. We use the N s = N r =128 most significant principal directions to span our face space. The used expression basis is a combination of the Digital Emily model [3] and Face-Warehouse [7], see Thies et al. [45] for details. We use PCA to compress the over-complete blendshapes (76 vectors) to a subspace of N e =64 dimensions.

Image Formation
We assume the face to be Lambertian, illumination to be distant and smoothly varying, and there is no self-shadowing. We thus represent the incident illumination on the face using second-order spherical harmonics (SH) [31,34]. Therefore, the irradiance at a surface point with normal n is given by where H k are the b 2 = 3 2 = 9 SH basis functions, and the θ [i] k are the corresponding illumination coefficients. Since we consider colored illumination, the parameters θ [i] k ∈ R 3 specify RGB colors, leading to 3·9 = 27 parameters in total.
We render facial images based on the SH illumination using a full perspective camera model Π : R 3 → R 2 . We render the face using a mask (painted once in a preprocessing step) that ensures that the rendered facial region matches the crops produced by the 66 detected landmark locations (see Figure 2). The global rotation of the face is modeled with three Euler angles using R = Rot xyz (α, β, γ) that successively rotate around the x-axis (up, α), y-axis (right, β), and z-axis (front, γ) of the camera space coordinate system.

Synthetic Training Data Generation
Training our deep inverse face rendering network requires ground-truth training data {I i , θ i } N i=1 in the form of corresponding pairs of image I i and model parameters θ i . However, training on real images is challenging, since the groundtruth parameters cannot easily be obtained for a large dataset. We therefore train our network based on synthetically rendered data, where exact ground-truth labels are available.
We sample N = 200,000 parameter vectors θ i and use the model described in Section 4 to generate the corresponding images I i . Data generation can be interpreted as sampling from a probability P (θ) that models the distribution of realworld imagery. However, sampling from this distribution is in general difficult and non-trivial. We therefore assume statistical independence between the components of θ, i.e., This enables us to efficiently generate a parameter vector θ by independently sampling each subset of parameters. We uniformly sample the yaw and pitch rotation angles α, β ∼ U (−40°, 40°) and the roll angle γ ∼ U (−15°, 15°) to reflect common head rotations in uncontrolled photos. We sample shape and reflectance parameters from the Gaussian distributions provided by the parametric PCA face model [4]. Since we already scale with the appropriate standard deviations during face generation (see Equations 2 and 3), we sample both from a standard normal distribution, i.e., N (0, 1). The expression basis is based on artistcreated blendshapes that only approximate the real-world distribution of the space of human expressions; this will be addressed by the breeding step presented in Section 7. We thus uniformly sample the expression parameters using θ [e] ∼ U (−12, 12). To prevent closing the mouth beyond anatomical limits, we apply a bias of 4.8 to the distribution of the first parameter 1 . Finally, we sample the illumination parameters using θ [i] ∼ U (−0.2, 0.2), except for the con- 1 ∼ U (0.6, 1.2) to account for the average image brightness, and set all RGB components to the same value to achieve monochrome illumination. The breeding step presented in Section 7 introduces colored illumination.

InverseFaceNet
Given the training data {I i , θ i } N i=1 consisting of N images I i and the corresponding ground-truth parameters θ i , we train a deep inverse face rendering network N to invert image formation. In the following, we provide details on our network architecture and the employed loss function.

Network Architecture
We have tested several different networks based on the popular AlexNet [23] and ResNet [15] architectures, both pretrained on ImageNet [38]. In both cases, we resize the last fully-connected layer to match the dimensionality of our model (350 outputs), and initialize biases with 0, and weights ∼ N (0, 0.01). These minimally modified networks provide the baseline we build on. We introduce more substantial changes to the training procedure by introducing a novel model-space loss in Section 6.2, which more effectively trains the same network architecture. The color channels of the input images are normalized to the range [−0.5, 0.5] before feeding the data to the network. We show a comparison between the results of AlexNet and ResNet-101 in Section 8.1, and thus choose AlexNet for our results.
Input Pre-Processing The input to our network is a color image of a masked face with a resolution of 240×240 pixels (see Figure 2). We mask the face to remove any background and the mouth interior which cannot be explained by our model. For this, we detect landmarks [39] and resize their bounding box uniformly to fit inside 240×240 pixels, to approximately achieve scale and translation invariance.
Training We train all our inverse face rendering networks using the Caffe deep learning framework [18] with stochastic gradient descent based on AdaDelta [50]. We perform 75K batch iterations with a batch size of 32 for training our baseline approaches. To prevent overfitting, we use an 2regularizer (aka weight decay) of 0.001. We train with a base learning rate of 0.01.

Synthetic Training Corpus (before Breeding)
Real World Images Synthetic Training Corpus (after Breeding) Figure 3. Our approach updates the initial training corpus (left) based on the distribution of real-world imagery (right) using an analysis-bysynthesis breeding strategy [32]. The generated new training corpus (middle) better reflects the real-world distribution of facial images.

Model-Space Parameter Loss
We employ a modified Euclidean loss that measures distance between predicted parameters p and ground-truth parameters θ by taking the statistics of the face model into account: Here, Σ is a weight matrix that incorporates the standard deviations σ • of the different parameter dimensions: The coefficients ω • balance the global importance of the different groups of parameters, and 1 k is a k-dimensional vector of ones. We use the same values (ω R , ω s , ω e , ω r , ω i ) = (400, 50, 50, 100, 20) for all our results. Note that we do not scale the rotation and illumination dimensions individually, which allows them to vary freely. Intuitively speaking, our model-space loss enforces that the first PCA coefficients (higher variation basis vectors) should match the ground truth more accurately than the later coefficients (lower variation basis vectors), since the former have a larger contribution to the final geometry and skin reflectance of the reconstructed face in model space (see Equations 2 and 3). As shown in Section 8, this leads to more natural and accurate reconstruction results.

Breeding with Real Images
The real-world distribution of the model parameters θ is in general unknown for in-the-wild images. Until now, we have sampled from a manually prescribed probability distribution P (θ), which does not exactly represent the realworld distribution. The goal of our parameter 'breeding' step is to make the training data distribution better match the real-world distribution in a corpus R of in-the-wild face photographs. To this end, the breeding step automatically bootstraps the parameters for the training corpus R using analysis-by-synthesis [32]. Note that this step is unsupervised and does not require the ground-truth parameters for images in R to be available. Breeding is a four-step process (see Algorithm 1). It starts with a deep neural network N initially trained on a synthetic training corpus (Section 5) for 15K batch iterations. This guarantees a suitable initialization for all weights in the network. Given a set of images from the corpus of real-world images R, we first obtain an estimate of the corresponding model parameters θ r using the synthetically trained network (step 1). These reconstructed parameters are used to seed the breeding process. In the next step, we apply small perturbations to the reconstructed parameters (step 2) based on a noise distribution. This generates new data around the seed points in the model parameter space, and allows the network to slowly adapt to the real-world parameter distribution. We use the following noise distributions to resample the pose, shape, expression, reflectance and illumination parameters, generating two perturbed parameter vectors for each reconstructed parameter vector: α, β, γ : U (−5°, 5°), θ [s] : N (0, 0.05), θ [r] : N (0, 0.2), θ [e] : N (0, 0.1), and θ [i] : N (0, 0.02). In the next processing step (step 3), we generate new synthetic training images I r based on the resampled parameters θ r . The result is a new synthetic training set {I r , θ r } that better reflects the real-world distribution of model parameters. Finally, the network N is fine-tuned for N iter = 7.5K batch iterations on the new training corpus (step 4). In total, we repeat this process for N breed = 8 iterations of these breeding steps. Over the iterations, the data distribution of the training corpus adapts and better reflects the real-world distribution of the provided in-the-wild facial imagery, as illustrated in Figure 3. This leads to better reconstruction results at test time, as shown in Section 8. Table 1. Quantitative comparison of network architectures, model-space parameter loss and our breeding steps on 5,914 test images from CelebA [29]. The best values for each column are highlighted in bold. Training time includes all algorithmic steps except the initial training data generation. Test times are averaged over 5K images. All timings on an Nvidia GeForce GTX Titan. Errors show means and standard deviations. * For breeding, we first train 15K iterations on normal synthetic face images (Section 5), and then breed for a further 60K iterations (see Section 7). InverseFaceNet (AlexNet [23] with model-space loss and breeding) produces the best results in all error categories.

Experiments and Results
We evaluate our InverseFaceNet on several publicly available datasets. We start by validating our design choices regarding the network architecture (Section 6), model-space parameter loss (Section 6.2), and breeding of the training corpus (Section 7). We then show qualitative and quantitative results and comparisons on the datasets CelebA [29], LFW (Labeled Faces in the Wild) [16], FaceWarehouse [7], Thomas [13], Volker [47] and 300-VW (300 Videos in the Wild) [40].

Error Measures
We measure the quality of reconstructed face models using photometric error, geometric error, and overlap of face masks. We compute the photometric error using the RMSE of RGB pixel values (within the mask of the input image) between the input image and a rendering of the reconstructed face model. An error of 0 is a perfect color match, and 255 is the difference between black and white (i.e. lower is better). The geometric error measures the RMSE in mm between corresponding vertices in our reconstruction and the ground-truth geometry. We quantify the image-space overlap of the estimated face model and the input face image using the intersection over union (IOU) of face masks (e.g. see 'contours' in Figure 4). An IOU of 0% means no overlap, and 100% means perfect overlap (i.e. higher is better).  Figure 4) from CelebA [29] using the error measures described earlier (using our implementation of Garrido et al. [14] as ground-truth geometry, up to blendshape level).

Evaluation of Design Choices
Network Architecture We first compare the results of the AlexNet [23] and ResNet-101 [15] architectures, both with our model-space loss (see Section 6). Reconstructions using ResNet-101 have smaller geometric errors, but worse photometric error and IOU than AlexNet, which is exemplified by Figure 4. ResNet-101 is significantly deeper than AlexNet, so training takes about 10× longer (all timings on an Nvidia GeForce GTX Titan). At test time, we reconstruct a full set of face model parameters in 134 ms using ResNet-101, or  Figure 4. Qualitative comparison of ResNet-101 [15] and AlexNet [23] applied to inverse face rendering, both with model-space loss (MSL): ResNet-101 produces lower geometric error while AlexNet has lower photometric error (also on average, see Table 1). AlexNet with MSL and breeding clearly improves the reconstruction of reflectance and geometry, in all error categories. 9.79 ms using AlexNet, which is 13× faster. We thus use AlexNet for our inverse face rendering network. Table 1 shows that our model-space loss improves on baseline AlexNet [23] in all error categories, particularly the photometric error and IOU. As our model-space loss does not modify the network architecture, the time to reconstruct a better face model from a single image remains the same fast 9.79 ms as before.

Importance of Model-Space Loss
Importance of Breeding Adapting the distribution of face model parameters in the training corpus via breeding (Section 7) significantly improves the reconstruction quality and produces the lowest errors in all categories, as shown in Table 1. This can also be seen in Figure 4, which shows plausible reconstruction of appearance and geometry, the lowest geometric errors, and improved contour overlap for our inverse face rendering network with breeding.  Figure 5. Qualitative results on several datasets. Left to right: input image, our estimated face model and geometry, and contours (red: input mask, green: ours). In reading order: 300-VW [40], LFW [16], Volker [47], FaceWarehouse [7], Thomas [13] and CelebA [29]. Our approach achieves high-quality reconstructions of geometry as well as skin reflectance from just a single input image.
ing time and test time, which remains unchanged for AlexNet at 9.79 ms per image, or more than 100 Hz (ResNet: 7.4 Hz). Figure 5 shows several monocular reconstruction results obtained with our InverseFaceNet. As can be seen, our approach obtains good estimates of all model parameters, i.e., pose, shape, expression, colored reflectance and scene illumination. We next compare our reconstruction results qualitatively to current state-of-the-art approaches. Figure 6 compares our reconstruction to optimization-based approaches that fit a parametric face model [14] or a person-specific template mesh [13]. Our learning-based approach is significantly faster (9.79 ms vs about one minute [14]), and it is in principle orthogonal to these optimization-based approaches, since it could be used to provide an initial solution close to the optimum.

Qualitative Evaluation
We also compare to the state-of-the-art deep-learningbased approaches by Richardson et al. [35,36] and Tran et al. [46]. Specifically, we compare to the results of Richardson et al.'s 'CoarseNet' [36], which corresponds to their earlier method [35], and estimates pose, shape and expression, followed by a model-based optimization of monochrome Input Ours Es mate Geometry Es mate Geometry Richardson17 Figure 7. Qualitative comparison to Richardson et al. [36] on LFW [16]. Note that our reconstruction results are colored, and better fit the face shape and mouth expressions of the input images.  Figure 9. Quantitative comparison of geometric accuracy compared to Tran et al. [46], Richardson et al. [36] and Thies et al. [45] on the Volker dataset [47]. The heat maps visualize the pointwise Hausdorff distance (in mm) between the input and the ground-truth mesh. The ground truth has been obtained by the high-quality binocular reconstruction approach of Valgaerts et al. [47]. reflectance and illumination. 2 As can be seen in Figures 7  and 8, we obtain similar or even higher quality results than these two state-of-the-art approaches. In contrast to Richardson et al. [35,36], our approach also obtains an estimate of the colored skin reflectance and illumination. Note that their approach does not require landmarks for initial cropping, but it is significantly slower due to their iterative regression strategy. The approach of Tran et al. [46] does not recover the facial expression and illumination. In contrast, our approach provides a one-shot estimate of all face model parameters.

Quantitative Evaluation
We compare the geometric accuracy of our approach to stateof-the-art monocular reconstruction techniques in Figure 9. As ground truth, we use the high-quality stereo reconstructions of Valgaerts et al. [47]. Compared to Thies et al. [45], our approach obtains similar quality results, but without the need for explicit optimization. Therefore, our approach is almost two orders of magnitude faster (9.79 ms vs 600 ms) than optimization-based approaches. Note that while Thies et al. [45] runs in real time for face tracking, it requires significantly longer to estimate all model parameters from an initialization based on the average model. Our reconstructions are also of higher quality than the state-of-the-art learning-based methods by Richardson et al. [35,36] and Tran et al. [46]. In contrast to these methods, we obtain a reconstruction of more aspects of the same face model. More specifically, we reconstruct pose, shape, expression, and colored skin reflectance and illumination.

Limitations
We propose a solution to the highly challenging problem of inverse face rendering from a single image. Similar to previous learning-based approaches, ours has a few limitations. Our approach does not perfectly generalize to inputs that are outside of the available training data. This is a limitation our approach shares with many learning-based techniques.
Profile views of the head are problematic and hard to reconstruct, even if they are part of the training corpus. Note 2 We don't compare to their 'FineNet', which estimates a refined depth map, as we are interested in comparing to reconstructed face models. that even state-of-the-art landmark trackers often fail in this scenario. Handling these cases robustly remains an open research question. Incorrect landmark localization might produce inconsistent input to our network, which harms the quality of the regressed face model. This could be addressed by either more sophisticated face detection algorithms, or by joint learning of face alignment and reconstruction.
External occlusions of the face, such as hair, beards, sun glasses or hands, can also be problematic. To handle these situations more robustly, our approach could be trained in an occlusion-aware manner by augmenting our training corpus with artificial occlusions, similar to Zhao et al. [51].
Our inverse face rendering network produces temporally quite stable reconstructions if applied to video, as shown in our supplemental video. However, we cannot guarantee temporal coherence on a video sequence as the primary goal of our approach is single-shot monocular reconstruction. This could be alleviated by an additional optimization that ensures temporal coherence, or by training explicitly on temporal data.

Conclusion
We have presented InverseFaceNet -a single-shot inverse rendering framework for faces from a single image. Our technique successfully learns the inverse mapping from face images to an elaborate set of face and lighting model parameters that could not be regressed by previous methods.
A key contribution of our work is to overcome the lack of well-annotated image datasets by breeding a synthetic training corpus that captures the real-world distribution of facial imagery. This enables high-quality face reconstruction from just a single monocular image. Our evaluation shows that our approach compares favorably to the state of the art, and extends it by also learning colored skin reflectance and scene illumination.
Our learning-based single-shot inverse renderer could be used to quickly and robustly initialize optimization-based monocular reconstruction approaches close to the global minimum. We hope that our approach will stimulate future work in this exciting field.