Mateus Souza
email: mateus.vilelasouza@uca.fr

Bruno Bachelet
email: bruno.bachelet@uca.fr

Thiago Noronha

Loïc Yon
email: loic.yon@isima.fr

Christophe Duhamel
email: christophe.duhamel@univ-lehavre.fr

A Model for Scheduling a Fleet of Autonomous Electric Agricultural Robots

Keywords: . Agriculture, scheduling, prize-collecting Topics: PO in the agriculture and environment, Logistics and Transport

Autonomous and electric robots appeared in agriculture to perform activities on the fields. The management systems dedicated to farms thus need to integrate software for the scheduling of a fleet of such robots. As agricultural systems are by nature subject to unpredictable events, it seems necessary to provide a solution for online scheduling. As a first step toward a global solution, we propose a model for a sub-problem that targets to provide the next route of each robot of the fleet in order to satisfy a subset of the demands for activities on fields emitted by the farmers. In this work, we present a mixed integer linear programming formulation for the sub-problem using the prize-collecting concept called here Prize-Collecting Robot Scheduling Problem with Time Window and Precedence Constraints. Specific constraints are introduced to ensure that PC-RSP provides viable solutions for the targeted online process.

Introduction

Recent advances in robotics bring autonomous, small and light robots to work in agriculture [START_REF] Duckett | Agricultural robotics: The future of robotic agriculture[END_REF]. Their introduction enables improving the efficiency of agricultural operations and reducing the environmental impacts [START_REF] Bochtis | Advances in agricultural machinery management: a review[END_REF], like the decrease of wastes, the focus on areas of great needs and potentially reducing fertilizer costs [START_REF] Blackmore | Robotic agriculture -the future of agricultural mechanisation[END_REF]. The traditional planning methods for agricultural operations need to be supplemented by new scheduling features, like route planning and sequential task scheduling [START_REF] Bochtis | Advances in agricultural machinery management: a review[END_REF] mainly to adapt to the introduction of these robots. Lately, the farmers use Farm Management Information Systems (FMIS), sophisticated and complex systems to support production management [START_REF] Fountas | Farm management information systems: current situation and future perspectives[END_REF].

In this context, we consider a farm composed of plots, and a warehouse where a fleet of robots is stored, set up (their tools, called here equipments, can be changed to enable a robot to perform different tasks), and maintained. Each plot represents an area with cultivation activities, and it is assumed here to have single entry and exit points. In each plot, a set of demands for activities that must be performed by the robots is emitted by the farmers. These demands have many requirements, which include: compatible robot -equipment pairing to perform the demand, a demand has to be achieved by only one robot (set up with one equipment only), a time window in which the activity must be performed, precedence constraints between demands, a priority level for each demand, and a preference date for the activity to be started.

There are different types of robots and equipments, and their numbers are limited. Equipments can only be installed or uninstalled at the warehouse, and the list of tools that are compatible with each robot is known. The time to install or to uninstall an equipment on a robot depends on both the types of the robot and the equipment. Robots can be set up with only one equipment at a time and can thus perform only a set of activity kinds once outside the warehouse to satisfy demands. We consider here electric robots operating on batteries. These batteries have to be recharged periodically at the warehouse. Besides, each different configuration (i.e. a pair of robot and equipment) has a specific battery discharging rate (assumed to be linear here) and performances (speeds to move and work). The energy and time spent by each configuration to execute the demands, and to move between locations, are deterministic and known beforehand (it can be provided by tools like [START_REF] Cariou | Mobile robot trajectory planning under kinematic and dynamic constraints for partial and full field coverage[END_REF]).

The decision problem consists here in managing and scheduling the robots, set up with equipment, to perform a set of demands in the farm. It is dynamic, i.e. new demands appear on the fly. Moreover, the execution of the demands are subject to unpredictable events, like: breakage of robot or equipment, unfavorable weather, unforeseen demands. Notice that the FMIS should react to these unpredictable events by emitting new demands [START_REF] Bachelet | Towards an architecture for online scheduling of autonomous robots in agriculture: Open issues[END_REF]. Thus, the problem needs to be handled by an online algorithm, because decisions must be made without the full knowledge of the future [START_REF] Karp | On-line algorithms versus off-line algorithms: How much is it worth to know the future[END_REF].

To model this scheduling problem, we propose an online approach, the Robot Scheduling Problem with Time Window and Precedence Constraints (RSP-TWP), a part of an ongoing project [START_REF] Belhassena | Towards an architecture for agricultural autonomous robots' scheduling[END_REF]. RSP-TWP is an iterative approach where the problem is decomposed in a sequence of sub-problems named Prize-Collecting Robot Scheduling Problem with Time Window and Precedence Constraints (PC-RSP) presented here. PC-RSP generates a single route for each robot in order to achieve some set of demands. A route is the trajectory of a robot (more precisely a configuration) that leaves the warehouse, moves sequentially to several plots to handle some demands before returning to the warehouse. In the global RSP-TWP problem, the PC-RSP sub-problem is called each time a robot returns to the warehouse and recharges its battery, in order to perform another trip with the same, or another equipment. As input, this problem needs mainly the availability dates of robots and equipments for a new route, and the current set of unscheduled demands.

We present here PC-RSP for which we propose a Mixed Integer Linear Programming (MILP) formulation. The performance of solving this MILP is evaluated for different instances, in order to show how this approach is amenable to be used in the perspective of the global online approach RSP-TWP.

Related Work

According to [START_REF] Pinedo | Scheduling in the service industries: an overview[END_REF], two types of scheduling problems exist: static where the schedule is not expected to change much over time, which can be considered to be the case of the PC-RSP problem analyzed in this work, as it only provides the next routes of the robots; and dynamic where the schedule is expected to change frequently, which is the case of the global RSP-TWP problem that should deal with unpredictable events. [START_REF] Allahverdi | A survey of scheduling problems with setup times or costs[END_REF] propose a review on scheduling problems. Our problem can be considered closely related to the job-shop problem, where the robots are the machines and the demands are the jobs. It is possible to consider in this case that our problem contains setup times, if we consider the travel times of the robots to move between the locations (warehouse and plots). However, our problem could also be considered close to a Vehicle Scheduling Problem (VSP), that is also known as Vehicle Routing Problem (VRP) [START_REF] Cordeau | Vrp with time windows[END_REF]. The robots are the vehicles that need to be scheduled to satisfy demands.

In our problem, each demand has to be satisfied inside a certain time window. [START_REF] Kontoravdis | A grasp for the vehicle routing problem with time windows[END_REF] present solutions for a VRP with Time Windows (VRP-TW), but they aim at minimizing the overall traveled distance and the number of used vehicles, and not to satisfy the maximum number of clients, or demands in our case. They propose to solve the problem with a Greedy Randomized Adaptive Search Procedure (GRASP). Tests on real instances were achieved, and the results are competitive in time with exact methods and reached good solutions (i.e. that handle all the demands with an acceptable number of vehicles and a reasonable traveled distance) in almost all cases. [START_REF] Bruglieri | A matheuristic for the electric vehicle routing problem with time windows[END_REF] consider a VRP-TW with the management of the energy of the vehicles (E-VRP-TW) dealing with the challenging of robot battery energy administration too. They handle the possibility of partial recharge of the vehicles' batteries and propose a MILP formulation. A Variable Neighborhood Search Branching (VNS-B) has been designed to obtain solutions of good quality in reasonable computational times. [START_REF] Schneider | The electric vehicle-routing problem with time windows and recharging stations[END_REF] address the Electric VRP-TW and Recharge Stations (E-VRP-TW-RS). In this problem, there are recharge stations where the vehicles can refill their battery in the path of the route. A hybrid heuristic has been designed that combines Variable Neighborhood Search (VNS) with Tabu Search (TS). The tests showed a high performance and the positive effects of the hybridization of strategies.

The prize-collecting concept guides the design of the objective function of PC-RSP. This approach is notably used for the Prize-Collecting Traveling Salesman Problem (PC-TSP), as presented in [START_REF] Fischetti | An additive approach for the optimal solution of the prize collecting traveling salesman problem[END_REF]. They search for a route for a vehicle to visit a subset of cities and use the concept of prize to introduce a reward on cities that are visited. PC-TSP is simpler in comparison to our PC-RSP problem, as we need to handle many robots and equipments to find several routes, and we propose to introduce a prize associated to the achievement of a demand. A branch-and-bound algorithm is proposed in [START_REF] Fischetti | An additive approach for the optimal solution of the prize collecting traveling salesman problem[END_REF] to solve optimally the PC-TSP problem that showed good performances on most of the tested instances. [START_REF] Stenger | The prize-collecting vehicle routing problem with non-linear cost: integration of subcontractors into route design of small package shippers[END_REF] addresses the Prize-Collecting Vehicle Routing Problem with Non-Linear cost (PC-VRP-NL) with the possibility of hiring outsource resources. This work also adapts the strategy of prize-collecting to a real problem, which is similar to our work only in using prizes and in the generation of routes. An integer linear model is presented like a VNS algorithm to solve the problem. After tests on instances adapted from classical VRP instances, it was demonstrated that the proposed VNS strategy exhibited a strong performance. [START_REF] Stenger | The prize-collecting vehicle routing problem with single and multiple depots and non-linear cost[END_REF] can be considered the continuation of [START_REF] Stenger | The prize-collecting vehicle routing problem with non-linear cost: integration of subcontractors into route design of small package shippers[END_REF], expanding the scope of PC-VRP-NL to the multi-depot case. This work deals with different aspects that are not taken into account in our PC-RSP problem: a non-linear objective function, multi-depot and the possibility of outsourcing the service to satisfy its customers. It was proposed an Adaptive Variable Neighborhood Search (A-VNS) algorithm to solve the problem, and benchmark instances, both for single-depot and multi-depot. In both cases, it was observed good performance of the proposed algorithm.

The multi-vehicle version of the Time-Dependent Prize-Collecting Arc Routing Problem (TD-PC-ARP) is presented in [START_REF] Black | The time-dependent prize-collecting arc routing problem[END_REF]. This work not only implements the strategy of prizes, but also includes the modeling of time, like in our problem, but without time windows for each demand. Two metaheuristics are presented, one based on VNS and the other one on TS. VNS had better performance on small instances and TS on large ones. [START_REF] Li | A two-level self-adaptive variable neighborhood search algorithm for the prize-collecting vehicle routing problem[END_REF] proposes a Two-Level Self-Adaptive Variable Neighborhood Search (TL-SA-VNS) algorithm to address the PC-VRP problem. They deal with the concept of prizes to satisfy clients and the generation of routes, but not with batteries, configuration of robots and equipments as we need to. They propose MILP to generate lower bounds for the problem, and a self-adaptive strategy to analyze the neighborhood to increase the probability of finding better solutions, and thus better upper bounds. The proposed metaheuristic showed better performances (i.e. lower gaps on obtained solutions) than Multi-Start Iteration Local Search (MS-ILS), Multi-Start Local Search (MS-LS), and Particle Swarm Optimization (PSO). [START_REF] Tang | Iterated local search algorithm based on very large-scale neighborhood for prize-collecting vehicle routing problem[END_REF] also addresses the PC-VRP problem, but with new constraints and an objective function that is a combination of factors. The objective takes into account the minimization of the number of used vehicles and the overall traveled distance, and the maximization of the number of visited customers. In our model, the objective considers only one factor, the number of handled demands, pondered by their priority and the proximity of their scheduled starting date with their preference date. This adapted PC-VRP is solved with an Iterated Local Search (ILS) algorithm based on a Very Large-Scale Neighborhood (VLSN) using cyclic transfer. This algorithm is compared with another ILS approach and a Multi-Start based on VLSN. It shows good performances by providing better solutions than the two other ones for the tested instances.

MILP Formulation

We propose here a MILP for the PC-RSP problem. Let D be the set of demands for activities (n = |D|), R the set of robots and E the set of equipments. The objective is to schedule the next route of each robot in R, while addressing some of the demands in their time window and satisfying the precedence constraints between demands. The robots leave the warehouse fully charged and must return to the warehouse at the end of each route, respecting the battery capacity. Besides, in its current route, the robot is equipped with one single equipment from E that is used to serve all the demands in that route. Each demand has a preferred date to be served and a priority. The objective is to find a schedule where demands are carried out as close as possible to their preferred date, and favoring the demands according to their priority. We propose to model this objective with triangular prize functions.

As PC-RSP is foreseen to be part of an online process, it needs the availability date a r ∈ R of each robot r ∈ R, meaning when robot r will be back at the warehouse and ready for a new route (i.e. fully recharged and unequipped) each time it is called. The model also requires the availability date b e ∈ R of each equipment e ∈ E and an up-to-date set of demands (i.e. the yet unscheduled demands in the global online process). Henceforth, we use the following terminology in this paper. A plot is an area of open land, especially one planted with crops or pasture, typically bounded by hedges or fences, with specific entry and exit points. It can also be called field or area. We consider here a single entry and exit point. The warehouse is the place where robots are recharged, and equipment are set up and removed from the robots. A location can be a plot or the warehouse. A farm is a set of locations, here we consider a single warehouse with several plots. An activity is an operation performed by a robot on a plot, such as irrigation, plowing, spraying, sowing, etc. A demand is a request for robots to perform an activity on a plot, and describes all the requirements to carry out this activity (e.g. the configurations able to carry out the activity, time window in which the activity must be achieved, etc.). An equipment is installed on a robot to make it ready to carry out a given kind of activity. It can also be called a tool. A configuration is a pair of compatible robot and equipment. A route is a circuit starting at the warehouse where a robot is first set up with one equipment and refilled, then sent successively to several plots to perform the same activity to satisfy many demands, and ultimately returns to the warehouse to uninstall the equipment from the robot.

Parameters

The battery capacity of robot r ∈ R is given by c r ∈ R. The recharging rate of robot r ∈ R is given by ρ r ∈ R. It is assumed that this rate is the same regardless the battery charge. The equipments compatible with robot r ∈ R are given by E(r) and the robots that are compatible with equipment e ∈ E are given by R(e).

As a demand is associated with a plot, we propose to model a set of demands as a graph where nodes represent demands (and consequently locations). Let G = (V, A) be the corresponding directed graph where V = D∪{0}∪{n+1}, where 0 and n+1 both represent the (same) warehouse. It is assumed that each route begins at 0 and ends at n + 1. The set of nodes A = {(i, j) : i, j ∈ D, i ̸ = j} ∪ {(0, j) : j ∈ D} ∪ {(i, n + 1) : i ∈ D} and A = {(i, j) : i, j ∈ D, i ̸ = j}.

The time for robot r ∈ R, if installed with an equipment e ∈ E, to carry out demand i ∈ D is given by δ re i ∈ R. δ re 0 is the time to install equipment e ∈ E(r) on robot r ∈ R at the warehouse and δ re n+1 is the time to uninstall the equipment e ∈ E(r) from the robot r ∈ R at the warehouse. Earliest starting date for serving demand i ∈ D is l i ∈ R, preferred starting date for serving demand i ∈ D is f i ∈ R and the latest starting date for serving demand i ∈ D is u i ∈ R.

The subset of demands that precede demand j ∈ D is P j ⊂ D, i.e. a robot can start j only after all demands i ∈ P j are achieved. The priority of demand i ∈ D in comparison with the other demands is given by ψ i ∈ R. This is the way to allow the farmer to express the relative importance of the demands.

The set of configurations that can carry out demand i ∈ D is C i ⊆ R × E. The configurations that go out of the warehouse (C 0 ) and back to the warehouse (C n+1 ) are assumed to be:

C 0 = C n+1 = C, where C = i∈D C i is the set of all valid configurations. C ij = C i ∩ C j , for all (i, j) ∈ A. The time for configuration (r, e) ∈ i∈D C i to move from location i ∈ V to location j ∈ V is d re ij ∈ R.
The energy spent by configuration (r, e) ∈ i∈D C i to move from location i ∈ V to location j ∈ V is e re ij ∈ R. The energy spent by configuration (r, e) ∈ i∈D C i to carry out demand i ∈ D is ϵ re i ∈ R. We also set ϵ rt 0 = 0 for all (r, e) ∈ C 0 , and ϵ rt n+1 = 0 for all (r, e) ∈ C n+1 .

Decision Variables (Discrete)

We define the decision variables x, such that x re ij = 1 if configuration (r, e) ∈ C ij carries out demand i ∈ D ∪ {0} and then moves to location j ∈ D ∪ {n + 1}, x re ij = 0 otherwise.

Auxiliary Variables (Continuous)

We define the auxiliary variables z, y and w. z i = 1 if demand i ∈ D is served, or z i = 0 otherwise. y re = 1 if robot r ∈ R uses equipment e ∈ E(r) to serve the demands assigned to a route, or y re = 0 otherwise. These variables do not need to be integer because their values are induced by x. w re i ∈ R is the date when configuration (r, e) ∈ C i starts the activity of demand i. In the case (r, e) does not carry out i, w re i = 0. This is not necessarily the date when r arrives at i, because it might need to wait for the opening of the time window of i to start performing the activity.

Objective Function

We define a prize function Z i for each demand i ∈ D that depends on the date w i when the activity starts, w i = (r,e)∈C i w re i . h - i is how much the service of demand i ∈ D will be advanced relatively to its preferred date, such that h - i = max(0, f i -w i ). h + i is how much the service of demand i ∈ D will be delayed relatively to its preferred date, such that h + i = max(0, w i -f i ). They are meaningful only if demand i is carried out. The maximum value of Z i is ψ i (the priority of demand i) when w i = f i (the preferred date) and linearly decreases with w i moving away from f i to reach 0 when reaching the limits (l i and u i ). The objective is thus to maximize the sum of the prize functions Z i as expressed by (1).

max Z = i∈D ψ i z i - h - i f i -l i - h + i u i -f i (1)

Constraints

(i,j)∈A (r,e)∈C ij

x re ij = z i ∀i ∈ D (2) e∈E(r) y re ≤ 1 ∀r ∈ R (3)
r∈R(e)

y re ≤ 1 ∀e ∈ E (4) (ℓ,j)∈A x re ℓj - (i,ℓ)∈A x re iℓ =      y re , if ℓ = 0 0, ∀ ℓ ∈ D -y re , if ℓ = n + 1 ∀ℓ ∈ D, ∀(r, e) ∈ k∈D C k (5) (i,j)∈A (r,e)∈C i (ϵ re i + e re ij )x re ij ≤ c r ∀r ∈ R (6) z i ≥ z j ∀j ∈ D, ∀i ∈ P j (7) (r,e)∈C i w re i + (i,ℓ)∈A δ re i x re iℓ ≤ (r,e)∈C j w re j + M a ij (1 -z j ) ∀j ∈ D, ∀i ∈ P j ( 8
)
w re i + δ re i + d re ij ≤ w re j + M b re ij (1 -x re ij ) ∀(i, j) ∈ A, ∀(r, e) ∈ C ij (9) l i (i,j)∈A:(r,e)∈C ij x re ij ≤ w re i ≤ u i (i,j)∈A:(r,e)∈C ij x re ij ∀i ∈ D, ∀(r, e) ∈ C i (10) h - i ≥ f i z i - (r,e)∈C i w re i ∀i ∈ D (11) h + i ≥ (r,e)∈C i w re i -f i ∀i ∈ D (12)
w re 0 ≥ b e y re ∀(r, e) ∈ C (13)

w re 0 ≥ a r y re ∀(r, e) ∈ C (14) x re ij ∈ {0, 1} ∀(i, j) ∈ A, ∀(i, j) ∈ A, ∀(r, e) ∈ C ij (15) 0 ≤ z i ≤ 1 ∀i ∈ D (16) 0 ≤ y re ≤ 1 ∀(r, e) ∈ C (17) h - i ≥ 0 ∀i ∈ D (18) h + i ≥ 0 ∀i ∈ D (19)
Constraints to manage the robots and equipments are given by constraints ( 2) to (4). Constraints (2) require that a demand must be served by at most one robot. Constraints (3), together with (5), ensure that a scheduled robot uses the same equipment to serve all the demands on its route. Constraints (4) manage the availability of each equipment. Constraints to model the routes of the robots, dealing with their energy and the time windows of the demands are given by ( 5) to ( 10).

The flow conservation constraints (5) impose that the route of each robot begins and ends at the warehouse. Constraints (6) enforce that each robot has enough energy to serve all the demands on its route and to return to the warehouse. Constraints ( 7) and ( 8) impose the precedence between demands. Subtour elimination constraints (9) link variables w and x. Constants M a ij and M b re ij are defined in Section 3.7. The restrictions on time windows are imposed by (10). They also ensure that any robot waits until the opening of the time window of a demand before starting the activity.

The variables h -and h + -used in the objective function -are determined by constraints ( 11) and ( 12), respectively. The domain of variables w is also lower bounded by a r and b e , any time a robot r or an equipment e is used in a route by constraints ( 13) and ( 14), respectively. The domain of variables x, z, y, h -, and h + are defined by constraints ( 15) to ( 19).

Towards Online Scheduling

As explained previously, PC-RSP will be called iteratively during the online process. We propose to add constraints ( 20) to ( 26) in order to enforce that each non-scheduled demand can be carried out in the next iteration of PC-RSP (not necessarily all of them simultaneously) if the schedule defined by variables x is performed as expected. For this, the following continuous auxiliary variables are defined: λ e ∈ R that is the next date when equipment e ∈ E will be available (i.e. when returning to the warehouse); µ r ∈ R that is the next date when robot r ∈ R will be available (i.e. when returning to the warehouse); and γ re i , such that γ re i = 1 if configuration (r, e) ∈ C i could handle demand i ∈ D in the next iteration (i.e. next time PC-RSP will be called), assuming that the schedule defined by variables x will be performed as expected, and γ re i = 0 otherwise. (ϵ re i + e re i,n+1 + ϵ re n+1 )x re j,n+1

λ e ≥ w re i + δ re i + d re i,n+1 + δ re n+1 -(1 -x re i,n+1 )M c re i ∀i ∈ D, ∀(r, e) ∈ C i (20) µ r ≥ w re i + δ re i + d re i,n+1 + δ re n+1 -(1 -x re i,n+1 )M d re i ∀i ∈ D, ∀(r, e) ∈ C i (
∀r ∈ R (22) µ r ≥ w re i + δ re i + d re i,n+1 + ξ r ρ r -(1 -x re i,n+1 )M e re i ∀i ∈ D, ∀(r, e) ∈ C i (23
)

λ e + δ re 0 + d re 0i ≤ u i + (1 -γ re i )M f re i ∀i ∈ D, ∀(r, e) ∈ C i (24) µ r + δ re 0 + d re 0i ≤ u i + (1 -γ re i )M g re i ∀i ∈ D, ∀(r, e) ∈ C i (25)
∀(r,e)∈C i

γ re i ≥ 1 -z i ∀i ∈ D (26) λ e ≥ b e ∀e ∈ E (27) µ r ≥ a r ∀r ∈ R (28)
γ re ij ∈ {0, 1} ∀(i, j) ∈ A, ∀(r, e) ∈ C ij (29)
Constraints (20) determine a lower bound of when equipment e will be available after being used in a scheduled route (i.e. when it will be available for the next route). Constraints (21) determine a lower bound of when robot r will be available for the next route, considering the time to uninstall an equipment from it. Constraints ( 22) compute the total energy ξ r of robot r to perform the scheduled route. Constraints (23) determine a lower bound of when robot r will be available for the next iteration, considering the time to recharge the battery. Constraints (24) bound λ e if equipment e is able to satisfy demand i in the next iteration. Constraint (25) bound µ r if robot r is able to satisfy demand i in the next iteration. Constraints (26) ensure that any non-scheduled demand can be carried out in the next iteration, at least by one available configuration. The domains of variables λ and µ are lower bounded by constraints ( 27) and ( 28) respectively. And the domain of the variables γ is defined by constraints (29). , M e re i , M f re i and M g re i used in some constraints presented previously. They are set here to have a complementary slack as small as possible in the model.

Constants

M a ij = u i + max (r,e)∈C i (δ re i ) ∀j ∈ D, ∀i ∈ P j (30) M b re ij > u j ∀(0, j) ∈ A, ∀(r, e) ∈ C 0j M b re ij = u i + δ re i + d re ij ∀(i, j) ∈ A : i ̸ = 0, ∀(r, e) ∈ C ij (31) M c re i = u i + d re i,n+1 + δ re n+1 ∀i ∈ D, ∀(r, e) ∈ C i (32) M d re i = u i + d re i,n+1 + δ re n+1 ∀i ∈ D, ∀(r, e) ∈ C i (33) M e re i = u i + d re i,n+1 + c r ρ r ∀i ∈ D, ∀(r, e) ∈ C i (34) M f re i = δ re 0 +d re 0i + max

Instances Generation

In order to generate complex instances for the PC-RSP problem, the data of Solomon's instances for the VRP-TW problem [START_REF] Solomon | Algorithms for the vehicle routing and scheduling problems with time window constraints[END_REF]) were used, those instances have 100 customers organized in clusters. The instances are grouped in two kinds of clusters, C1 and C2, where C1 instances have clusters more dense than those in C2. are set to 5 minutes. d re ij are the distances from Solomon' instances. e re ij is set to 0. ϵ re i is the weight (demand) of each customer from Solomon's instances. There is no precedence between demands.

In order to compute the preferred date and time window of each demand in the generated instances, it is necessary to build a viable solution (without time window constraints) for the problem, i.e. a set of routes for configurations that satisfies all the demands. From this solution, f i is set to the time a configuration starts to carry out demand i, and randomly l i is set to f i -U [0, 24] and Tables 1 and2 show results of solving the MILP model for PC-RSP with a time limit of respectively 300 and 3600 seconds. The first field is the name of the instances in Solomon's set. The next two fields are the upper bound and the lower bound, i.e. the so far best integer solution found. The fourth field is the relative gap between the two bounds. The last field is the percentage of demands satisfied by the best found solution.

u i to f i + U [0, 24]. ψ i is randomly set to U [1, 100].

Computational Results

Instances

In Table 1, we can observe that it was not possible to find a viable solution for 3 instances in C2 and 1 instance in C1 within the time limit. In Table 2, a viable solution is found for all the instances within the time limit. The gaps are smaller in C1 than in C2 in Table 1. And the gaps are mostly smaller in C1 than in C2 in Table 2. This suggests that the density of the clusters is a factor that makes the problem harder to be solved.

The comparison between Table 1 and Table 2 shows an improvement in the lower bounds with the increase of the time limit of execution. The improvement in the upper bound is very small, indicating that the linear relaxation of the model is not very good. The improvement of the gap of all instances can be observed, influenced mostly by lower bound improvement.

The tests were made on an Intel Xeon E5405 at 2.0 GHz, 16 GB of 667 MHz DDR2 RAM memory, and 4 cores (hyper-threading not activated). CPLEX 20.1 was used for linear program solving.

Conclusion

We proposed here a MILP formulation for the problem that we called Prize-Collecting Robot Scheduling Problem with Time Windows and Precedence Constraints (PC-RSP). This problem is to find the next route for each robot of a fleet, in order to satisfy some demands for activities on plots in a farm. It is part of a more global problem, the Robot Scheduling Problem with Time Window and Precedence Constraints Problem (RSP-TWP) that targets to produce a complete schedule to satisfy all the demands for activities in a given period of time.

To solve this problem, we consider solving PC-RSP repeatedly. Moreover, as agricultural systems are by nature subject to unpredictable events, we have foreseen to also use PC-RSP in a global online scheduling process. It is therefore necessary to solve PC-RSP within a short time, we assess less than 5 minutes.

As one can observe in Table 1, the proposed MILP for PC-RSP does not make possible to get a viable solution for all the instances within this time limit, showing the necessity of studying heuristics in future works to solve PC-RSP. However, from these results, it appears that the structure of the graph representing the locations of the farm has an impact on the difficulty to solve the problem. Studies to improve the model in order to find better upper bounds more rapidly should be done to solve PC-RSP more efficiently with MILP. After these studies, a method to solve PC-RSP for the global RSP-TWP problem will be considered.

  n+1)∈A:(r,e)∈C i,n+1

  j∈D, ṙ∈R:∀( ṙ,e)∈C j b e +u j +δ ṙe j +d ṙe j,n+1 +δ ṙe n+1 ∀i ∈ D, ∀(r, e) ∈ C i (35) to (36) define the constants M a ij , M b re ij , M c re i , M d re i

  Customers' time windows are used for the demands and the deposit becomes the warehouse. The robot set is composed of 3 robots, one of each kind, R = {1, 2, 3}, and the equipment set is composed of 3 equipments, one of each kind, E = {a, b, c}. With these two sets, 6 possible configurations are created, C = {(1, a), (1, b), (2, a), (2, c), (3, b), (3, c)}. c r is equal to the vehicle's capacity from Solomon's instances. ρ r is equal to c r divided by 8 hours. a r and b e are set to 0. G = (V, A) is the graph from Solomon's instances. C i is randomly built from C, such that |C i | = 3. δ re i is the service time from Solomon's instances. δ re 0 and δ re n+1

Table 1 :

 1 Results of MILP solving with execution time limit of 300 seconds.

		Upper bound Lower bound Relative gap	Percentage of satisfied demands
	InstancePCRSP-C101	3315.00	688.42	382%	12%
	InstancePCRSP-C102	3271.00	197.07	1560%	3%
	InstancePCRSP-C103	3310.00	198.25	1570%	4%
	InstancePCRSP-C104	3566.00	612.22	482%	9%
	InstancePCRSP-C105	3215.50	20.00	15977%	1%
	InstancePCRSP-C106	3431.00	152.00	2157%	2%
	InstancePCRSP-C107	3375.00	695.32	385%	10%
	InstancePCRSP-C108	3245.89	332.08	877%	7%
	InstancePCRSP-C109	3324.67	0.00	*	0%
	InstancePCRSP-C201	4984.00	39.00	12679%	1%
	InstancePCRSP-C202	5200.00	211.00	2364%	6%
	InstancePCRSP-C203	5151.00	0.00	*	0%
	InstancePCRSP-C204	5559.00	120.67	4507%	3%
	InstancePCRSP-C205	5034.00	0.00	*	0%
	InstancePCRSP-C206	5539.00	0.00	*	0%
	InstancePCRSP-C207	5378.00	76.00	6976%	2%
	InstancePCRSP-C208	4972.00	91.00	5364%	1%

* Not possible to calculate the gap, lower bound set to 0.

Table 2 :

 2 Results of MILP solving with execution time limit of 3600 seconds.

Acknowledgments

This work was sponsored by a public grant overseen by the French National Research Agency as part of the "Investissements d'Avenir" through the IDEX/I-SITE initiative CAP 20-25 (16-IDEX-0001).


Daniel Kersten
email: kersten@umn.edu

Pascal Mamassian

Arthur G Shapiro

Dejan Todorovic

Cast Shadow Illusions

). An attached shadow on an object is the darkened surface that faces away from the light source. A cast shadow on a surface is the dark area created by an object blocking light onto that surface. A cast shadow can also be created when part of an object blocks light onto another part of the same object. For simplicity, in this chapter, the word "shadow" will usually refer to "cast shadow".

Introduction

Shadows are everywhere, but they usually go unnoticed. We do, however, use their consequences all the time. Figure 1A shows two pictures each with a green square in front of a checkerboard background. The two pictures differ only in the cast shadows of the square. Because of these differences, the right square appears to be further from the background than the left square. By adding motion to the cast shadow, the effect on the perception of depth can be made quite striking. Moving the shadow, leaving the square fixed in the image, results in the square appearing to move in depth (see: http://youtu.be/ig2CV1TLn5A). It is only with scrutiny that one is convinced that the square is not moving at all within the picture frame. In particular, the square is not changing size, as it should if it was indeed moving in depth. Shadows seem to create a paradox for the visual system. While on the one hand they can be quite useful as cues for depth, their unobtrusiveness suggests that there may be good reasons for a visual system to get rid of them. A cast shadow provides useful information for the depth of an object relative to the background surface. One can produce the appearance of motion in depth of the unmoving square by moving the shadow over a sequence of frames, see: http://youtu.be/ig2CV1TLn5A. B. Cast shadows are most effective at conveying depth when they have typical properties (top panel). If the shadows are above the object, or are sharp, they tend to be less effective (bottom three panels) [START_REF] Kersten | Illusory motion from shadows[END_REF]. C. Information about depth from shadows can be placed in conflict with information from stereo disparity. The stereo disparity provides information indicating that the top square is further from the background, whereas the shadow indicates it is the bottom square that is further away from the background. There are differences between people, and readers may be able to judge for themselves which cue wins. To experience the stereo effect, the reader should try to cross the two eyes so that the left and right images are seen by the right and left eyes, respectively. An animated version of this demonstration, with moving shadows, can be viewed at: http://youtu.be/d4KMLLSs1C0.

Shadows: Use them or lose them?

As visual animals, we typically need information about objects for the job at hand, whether that be describing, handling, navigating around, or tracking them. It would make sense that shadows go unnoticed because our attention is primarily directed towards the tangible objects we need rather than towards their shadows. Depending on the task, it might even make sense for the visual system to filter out shadows completely; for example, when they fall on the very object of interest, making it difficult to detect the features specific to the object (see Figure 2A; [START_REF] Cavanagh | What's up in top-down processing[END_REF][START_REF] Lovell | Search for gross illumination discrepancies in images of natural objects[END_REF]. The problem of detecting object-specific features is part of a more general problem that the brain must solve to reliably recognize objects. The images of an object (called its "appearances") vary B A Figure 2. A. Shadows cast from other objects create problems for visual recognition. Upper and lower panels show the original gray level image and the output of a standard edge detector, respectively. While cast shadow edges can, in theory, provide some information regarding shape, they tend to be more trouble than they are worth. B. It isn't easy to tell whether cast shadows are physically correct, as illustrated by a photograph of Lee Harvey Oswald, the alleged assassin of John F. Kennedy (LIFE Magazine, February 21, 1964). Conspiracy theorists have argued that Oswald's claims that the photographs were doctored were supported by the supposed "fact" that shadows cast by his nose and body, were not consistent with a single light source [START_REF] Farid | The Lee Harvey Oswald backyard photos: real or fake?[END_REF].

greatly from one instance to the next because of changes in both viewpoint and illumination. Illumination gives rise to shading patterns that are affected by the object's orientation relative to the illumination sources and the viewpoint. And shadows, in particular, can have a strong effect on appearances.

Given the confounding nature of shadows, it may not be surprising that we seldom notice shadow inconsistencies in paintings or when artificially created in photographs [START_REF] Mamassian | Impossible shadows and the shadow correspondence problem[END_REF][START_REF] Ostrovsky | Perceiving illumination inconsistencies in scenes[END_REF][START_REF] Cavanagh | The artist as neuroscientist[END_REF]. Even with careful inspection we are not very good at deciding whether a cast shadow is faithful to the laws of optics or is faked (for example see the analysis of the Lee Harvey Oswald backyard pictures, Farid 2009; Figure 2B). Further, pictorial artists often eliminate shadows that might interfere with interpretation [START_REF] Jacobson | Why cast shadows are expendable: Insensitivity of human observers and the inherent ambiguity of cast shadows in pictorial art[END_REF][START_REF] Gombrich | Shadows : the depiction of cast shadows in Western art[END_REF]. Human visual recognition can suffer in the presence of shadows [START_REF] Tarr | Why the visual recognition system might encode the effects of illumination[END_REF][START_REF] Braje | Invariant recognition of natural objects in the presence of shadows[END_REF][START_REF] Braje | Illumination Effects in Face Recognition[END_REF], and considerable computer vision research has gone into detecting shadows in order to remove them (G. [START_REF] Finlayson | Removing shadows from images[END_REF][START_REF] Jacobson | Why cast shadows are expendable: Insensitivity of human observers and the inherent ambiguity of cast shadows in pictorial art[END_REF]. Does their confounding effect on recognition [START_REF] Porter | What makes cast shadows hard to see[END_REF], together with the need to attend to objects imply that shadows are more trouble than they are worth, and that the visual system filters them out? Our illustration of depth from cast shadows suggests obviously not.

In fact, artists, photographers, animators, and lighting designers have long known that shadows have positive as well as negative consequences for perception-their judicious placement adds a sense of depth, realism, and evokes mood, whereas injudicious placement of even optically correct shadows can be misleading or distracting. So while shadows don't have a starring role to play on the stage of conscious perception, the illusory motion demonstration described above does suggest that they have a strong supporting role in conveying information about depth. What kinds of parts do shadows play in depth perception and just how strong are their roles? And what information does the human visual system extract in order to use shadows?

The perceptual use of shadows Because of their role in providing depth information, shadows can be useful for diverse tasks such as deciding whether two surfaces are touching [START_REF] Thompson | Visual glue[END_REF], estimating the future trajectory of a flying object [START_REF] Taya | Cast shadow can modulate the judged final position of a moving target[END_REF], determining the structural form of patterns [START_REF] Khuu | Detecting the structural form of cast shadows patterns[END_REF], deciding whether one surface occludes another [START_REF] Tomonaga | Pacman in the sky with shadows: the effect of cast shadows on the perceptual completion of occluded figures by chimpanzees and humans[END_REF], and detecting differences in shape [START_REF] Rensink | The influence of cast shadows on visual search[END_REF]. Infants as young as 5-7 months use cast shadows for depth [START_REF] Yonas | Infants' perception of depth from cast shadows[END_REF][START_REF] Imura | Perception of motion trajectory of object from the moving cast shadow in infants[END_REF]. Cast shadows improve perception of relative depth in chimpanzees [START_REF] Imura | Moving shadows contribute to the corridor illusion in a chimpanzee (Pan troglodytes)[END_REF]. Shadow features, unlike specular highlights, provide reliable surface features for stereo disparity, which in turn provides information for 3D shape [START_REF] Puerta | The power of shadows: shadow stereopsis[END_REF]. (For a general review of the role of cast shadows in perception, see [START_REF] Dee | The Perception and Content of Cast Shadows: An Interdisciplinary Review[END_REF]. For a historical and cultural treatment of shadows, see Casati 2004b.)

The role of cast shadows as a means to convey depth in drawings was recognized long ago by Leonardo da Vinci [START_REF] Fiorani | The colors of Leonardo's shadows[END_REF]. One aspect of his advice-the ability to add "drop shadows"-is used everyday in graphics presentation and layout software (e.g. as a text format option in Microsoft's Powerpoint and Apple's Keynote presentation software). The strength of real-life drop shadows is illustrated below by putting them in conflict with our daily experience that objects shouldn't defy gravity.

How strong are cast shadow cues for depth?. A critical visual function is to know where an object is on a ground plane. Cast shadows provide pervasive and strong cues for contact between one surface and another, acting as a kind of "visual glue" [START_REF] Thompson | Visual glue[END_REF]. The information lies in the proximity of the image of an object and its cast shadow, the sharpness of the penumbra, together with how local shadow and object contours meet [START_REF] Madison | Use of interreflection and shadow for surface contact[END_REF]. When there is no visual glue, the depth of an object becomes ambiguous. As an object rises above a plane, the shadow gets further from the casting object, and the size of the penumbra increases. 2 Apparent Levitation. Cast shadows are sufficiently powerful as a depth cue, that lack of contact information can inveigle perception to believing that objects or people can defy gravity, a trick used by street magicians. Here the magician raises one foot creating a displaced cast shadow while using the same foot to hide the fact that the other foot is holding his body up tiptoed (cf. http://en.wikipedia.org/wiki/Balducci levitation).

Another trick is to take advantage of a gray day when the contact cue is weak, increasing depth ambiguity. Viewing from just the right angle allows a distant wet spot to assume the role of cast shadow, resulting in apparent levitation (left panel of Figure 3). Even on a bright day, an overhead sun can make an object's true shadow hard to see, reducing its role as visual glue, allowing a visually more salient shadow from another object to become associated with the object of interest making it appear to float mysteriously above the ground (right panel of Figure 3).

By creating variations of the green-square animation described earlier, one can show that the strength of the apparent change in depth is stronger if 1) the light source appears to come from above, 2) the cast shadow has a visible penumbra whose fuzziness grows with relative depth, and 3) the shadow is dark rather than light (which is physically impossible). These factors all suggest that the human visual system is sensitive to naturally and frequently occurring properties of cast shadows in images (see [START_REF] Kersten | Illusory motion from shadows[END_REF]; Figure 1B). Recognizing these factors has practical consequences; for example, illumination from above the camera improves the utility of cast shadows in endoscopy [START_REF] Mishra | Optimum shadowcasting illumination for endoscopic task performance[END_REF].

It is well-known that in addition to shadows, the human visual system uses multiple sources of depth information, including stereo disparity, motion parallax, relative brightness, and relative image size to produce estimates of relative depth [START_REF] Bülthoff | Integration of depth modules: stereo and shading[END_REF][START_REF] Landy | Measurement and modeling of depth cue combination: In defense of weak fusion[END_REF][START_REF] Cutting | Perceiving layout and knowing distances: The integration, relative potency, andcontextual use of different information about depth[END_REF]. One can use computer graphics to place different sources of information, or cues, in opposition. For example, Figure 1C shows stereo disparity competing with cast shadows. Which cue wins depends on the weight an individual's visual system gives to the stereo over the shadow information.

In many cases, the percept experienced is the consequence of how these cues get weighted based on their respective reliabilities [START_REF] Jacobs | Optimal integration of texture and motion cues to depth[END_REF][START_REF] Ernst | Merging the senses into a robust percept[END_REF][START_REF] Clark | Data Fusion for Sensory Information Processing Systems[END_REF]. This suggests that as we make a visual cue increasingly strong and more 2 The size of the penumbra also depends on the angular size of the light source. On a sunny day, the penumbra caused by the sun is quite small, the sun being far away, and only 1/2 • in diameter. On a cloudy day, the effective diameter approaches 180 • , and penumbrae are all but invisible except for small depth differences. And when there are multiple light sources, e.g. light filtering through the leaves of a tree, there can be multiple shadows that have characteristic transparency-like properties where they overlap. diagnostic of a relative depth change (vs. some other cause), one could make visual illusions in which a stronger cue (e.g. the fuzziness of a shadow penumbra) overrides cues that say otherwise. We've already seen this with the green-square demonstration in that the size of the image of the green square doesn't increase as it approaches the viewpoint, as it normally would under perspective projection.

One way to increase the perceptual strength of shadows for depth is to move the object in the image, while keeping the illumination and viewpoint constant. The left top panel of Figure 4A shows the first frame of an animation sequence, and the middle and right panels show two alternative endpoints of the ball's shadow trajectory. While a comparison of the middle and right-hand panels provides some sense of depth differences, the animated versions are considerably more striking (see http://youtu.be/hdFCJepvJXU). When the shadow travels horizontally in the image, the ball appears to rise above the checkerboard floor, and when the shadow travels diagonally, the ball appears to recede in depth towards the back of the box. The ball's size, appearance, and trajectory are identical in the two animation conditions. The lack of a change in size of the image of the ball presents a cue conflict, which the visual system largely ignores. The bottom row of Figure 4A shows a similar sequence, except that a yellow, solid slab is substituted for the shadow. As long as the slab appears to stay on the floor, viewers typically see the ball rise above the floor for the animation whose shadow endpoint corresponds to the bottom, middle panel; but, remain on the floor for the end-point illustrated by the bottom right panel. One explanation for the perception of the different trajectories with the yellow slab is that human vision is sensitive to the correlated motion typical of objects and their shadows resulting from light sources that do not move. This is called the "stationary light source" constraint [START_REF] Kersten | Moving cast shadows induce apparent motion in depth[END_REF]. So even if the slab, ersatz shadow, lacks most of the properties of a shadow, the visual system is equipped to perceive different trajectories as a consequence of the differences in correlated motion. Other factors, such as matching sizes between casting object and shadow, also play a role [START_REF] Ni | Perception of scene layout from optical contact, shadows, and motion[END_REF], but not as much as the correlated motion.

Another demonstration of the effect of the stationary light source constraint, and its impact on correlated motion, is illustrated in Figure 4B. The top row shows samples of several successive frames in which a ball and its shadow alternately accelerate and decelerate consistent with fixed light source from above. When all frames are shown in a movie, the ball appears to bounce (see http://youtu.be/6Wbbx6Zi3g4). However, if the ball has constant velocity (samples shown in bottom row of Figure 4B), the perceived coupling between the ball and its shadow is lost, the shadow seems to have a life of its own, and the ball no longer appears to bounce. When the trajectory of the shadow is horizontal, the ball appears to rise above the floor; when the shadow trajectory is diagonal, the ball appears to travel towards the back of the box. See http://youtu.be/hdFCJepvJXU. The perception of the different trajectories in depth relies on the visual system's ability to detect correlated motion (consistent with a stationary light source). Bottom panel: If the shadow is replaced by a yellow slab, the apparent difference in trajectories can still be seen. In addition to correlated motion, treating the slab as a substitute shadow relies on perceiving the slab to be on the floor. The coincidental alignment of one of the primary axes of the slab with that of the floor encourages this. See: http://youtu.be/ TGX7153-Ccw. Figure from [START_REF] Kersten | Moving cast shadows induce apparent motion in depth[END_REF]. B. See http://youtu.be/6Wbbx6Zi3g4 and main text for an explanation.

The future of shadows

Despite their ubiquity, there are substantial computational, perceptual, and neuroscience challenges to our understanding of the visual processing of shadows.

Computational challenges. While the potential usefulness of cast shadows in computer vision was recognized many years ago [START_REF] Waltz | Generating semantic descriptions from drawings of scenes with shadows[END_REF], the application to depth estimation has largely been neglected. This stands in contrast to substantial progress in understanding and using other cues such as stereo disparity and motion parallax. To use cast shadows, a visual system must effectively segment a scene into objects and shadows, determine which object (or object part) goes with which shadow (or shadow part; i.e., the shadow "correspondence problem", [START_REF] Mamassian | Impossible shadows and the shadow correspondence problem[END_REF][START_REF] Ni | Perception of scene layout from optical contact, shadows, and motion[END_REF][START_REF] Casati | The copycat solution to the shadow correspondence problem[END_REF]), and use this information in the context of the overall spatial layout (Figure 5). While there have been a number of analyses of the information provided by shadows (Casati, 2004a;[START_REF] Dee | The Perception and Content of Cast Shadows: An Interdisciplinary Review[END_REF][START_REF] Knill | Geometry of shadows[END_REF], the computational challenge will be to turn these observations into useful algorithms.

Statistical constraints on shadow photometry can be used for shadow recognition. For example, the color change across a shadow boundary is largely a change in luminance rather than chromaticity [START_REF] Kingdom | Colour vision brings clarity to shadows[END_REF][START_REF] Finlayson | Entropy Minimization for Shadow Removal[END_REF]. Similarly, texture statistics tend to remain similar across shadow boundaries [START_REF] Zhu | Learning to recognize shadows in monochromatic natural images[END_REF]. The global shape of shadow contours have statistical regularities consistent with the shadow patch laying on the surface receiving it. More specifically, shadow shapes follow the geometry of double-projection: the shadow on a surface is the projection of the casting object by the light source on to an oriented surface, and shadow's image is the result of a projection of the surface shadow onto the retina. One consequence of this is that it is not unusual to have a long thin shadow in an image cast by a compact object (e.g. with the highly oblique sun angles during sunrise or sunset). In contrast, a long, thin image is less likely due to a compact object in the world [START_REF] Brady | An extremum principle for shape from contour[END_REF]. Perceptual challenges. A major problem in visual perception is understanding how the visual system combines multiple cues for a task such as depth perception. One problem in combining shadows with other depth cues is the commensurability of their information. Some cues, like "looming", the expansion of the size of an object's image on the retina, provide the visual system with information for distance between an object and the observer. Rather than depth from the observer, cast shadows more directly provide an estimate of the distance between two objects (the object casting the shadow and the receiving surface; [START_REF] Schrater | How optimal depth cue integration depends on the task[END_REF]. In addition, this distance is dependent on usually invisible factors like the light source position. Thus, shadows should prima facie not be

Potential light source directions

Eye

Potential shadow locations Potential ball locations Floor

Figure 5. The human visual system solves several problems when estimating depth from cast shadows. Even if the "patches" representing an object and shadow are identified and paired, in order to determine relative depth, their locations need to be localized in an appropriate frame of reference [START_REF] Schrater | How optimal depth cue integration depends on the task[END_REF]. For example, while it is obvious that the shadow should be on the ground, an algorithm needs also to determine the ground plane. From [START_REF] Kersten | Perceptual Categories for Spatial Layout[END_REF]. considered as a metric depth cue like binocular disparity, and this makes it more difficult to understand how these two cues can interact (e.g. Figure 1C). However, it is conceivable that, given prior assumptions on the statistical structure of the environment, shadows could be "promoted" to a metric depth cue. Such a reliance on the statistical structure of natural scenes has been shown to promote the figure-ground convexity cue (an object with a convex boundary tends to be seen in front) to a full metric depth cue [START_REF] Burge | Natural-Scene Statistics Predict How the Figure-Ground Cue of Convexity Affects Human Depth Perception[END_REF].

Neuroscience challenges. The dual nature of shadows reflects, in large part, two different functional requirements of vision. A basic architectural aspect of the visual brain is the division into two main pathways: the ventral (or temporal) and dorsal (or parietal) streams, believed to be specialized for processing intrinsic object properties, and viewer-object spatial relationships, respectively [START_REF] Milner | The Visual Brain in Action[END_REF]. As discussed above, on the one hand, to recognize objects, the visual system needs to filter out image features, including those due to shadows, that are not intrinsic to the object. On the other hand, to determine where objects are, we've seen that the visual system uses cast shadows in addition to other depth cues. [START_REF] Bonfiglioli | Differential effects of cast shadows on perception and action[END_REF] argue that this functional distinction underlies their finding that incongruent shadows had a significant impact on motor task, but not on recognition performance. However, it has also been shown that cast shadows can be relatively ineffective in the online control of pointing movements in depth [START_REF] Hu | Binocular and monocular depth cues in online feedback control of 3D pointing movement[END_REF]. Consistent with a role for the dorsal stream in processing depth from shadows, neuroimaging results have found that the posterior portion of the medial parietal cortex is activated when observers perceive depth from cast shadows [START_REF] Katsuyama | Perception of object motion in three-dimensional space induced by cast shadows[END_REF].

Shadows have been studied for millennia, yet there are always new and fascinating observations to be made [START_REF] Casati | Some varities of shadow illusions: Split shadows, occluded shadows, stolen shadows, and shadows of shadows[END_REF][START_REF] Casati | Impossible Cast Shadows in Ukyio-e Paintings[END_REF]. Shadow illusions, in particular, raise significant questions about how the brain processes them. Attempting to answer these questions will insure that shadows continue to captivate artists and scientists alike for years to come.

  1

  Figure 1. A.A cast shadow provides useful information for the depth of an object relative to the background surface. One can produce the appearance of motion in depth of the unmoving square by moving the shadow over a sequence of frames, see: http://youtu.be/ig2CV1TLn5A. B. Cast shadows are most effective at conveying depth when they have typical properties (top panel). If the shadows are above the object, or are sharp, they tend to be less effective (bottom three panels)[START_REF] Kersten | Illusory motion from shadows[END_REF]. C. Information about depth from shadows can be placed in conflict with information from stereo disparity. The stereo disparity provides information indicating that the top square is further from the background, whereas the shadow indicates it is the bottom square that is further away from the background. There are differences between people, and readers may be able to judge for themselves which cue wins. To experience the stereo effect, the reader should try to cross the two eyes so that the left and right images are seen by the right and left eyes, respectively. An animated version of this demonstration, with moving shadows, can be viewed at: http://youtu.be/d4KMLLSs1C0.

Figure 3 .

 3 Figure 3. Left panel. The absence of a strong true shadow of the man, together with a "goodenough" substitute-the dark spot on the road-produces apparent levitation. Right panel. The shadow of a flag appears to belong to the platform, creating the illusion that the speaker is elevated with no visible means of support.

Figure 4 .

 4 Figure 4. A. The images in the left column show the first frame, and the middle and right frames show alternative endpoints of the ball's shadow. The trajectory of the ball is the same in all trajectories. Top panel.When the trajectory of the shadow is horizontal, the ball appears to rise above the floor; when the shadow trajectory is diagonal, the ball appears to travel towards the back of the box. See http://youtu.be/hdFCJepvJXU. The perception of the different trajectories in depth relies on the visual system's ability to detect correlated motion (consistent with a stationary light source). Bottom panel: If the shadow is replaced by a yellow slab, the apparent difference in trajectories can still be seen. In addition to correlated motion, treating the slab as a substitute shadow relies on perceiving the slab to be on the floor. The coincidental alignment of one of the primary axes of the slab with that of the floor encourages this. See: http://youtu.be/ TGX7153-Ccw. Figure from[START_REF] Kersten | Moving cast shadows induce apparent motion in depth[END_REF]. B. See http://youtu.be/6Wbbx6Zi3g4 and main text for an explanation.

. D.K. was supported by the WCU (World Class University) program funded by the Ministry of Education, Science and Technology through the National Research Foundation of Korea (R31-10008).