On Multi-Agent Coordination of Agri-Robot Fleets Marin Lujak 1 and Elizabeth Sklar2 and Frederic Semet3 Abstract. The need for sustainable agriculture has led to the recent Fleet coordination systems are commonly used to coordinate mo- introduction of Agriculture Mobile Robots (AMRs) and Precision bility and delivery services in a wide variety of domains. Their ap- Agriculture (PA) techniques designed to make the practice of farming plication in the coordination of large agriculture fleets is less com- more accurate, better controlled and more environmentally sound. To plex than in road traffic, but still highly challenging since “traffic” date, AMR research has focused on a single robot and its agriculture- in the agriculture field emerges from the interaction of multiple col- specific capabilities. Very little work has been done with respect to laborative decision makers. In practice, fleets are conventionally co- efficient and scalable real-time agricultural vehicles in general, and ordinated dividing an area of interest in sectors, each one assigned more specifically with respect to AMR fleet coordination (FC). This to a single human controller. The optimisation of the tractors and is especially the case when considering overall fleet performance, as tractor-implement combinations4 is still left to a human operator. well as tactical and operational real-time vehicles that can accom- Planning and scheduling of agri-robot and tractor tasks, paths and modate implementation and crop cultivation constraints. This topic related tractor-implement configurations, drivers and controllers is is of the utmost importance in the case of commercial agriculture still left to human planners. Such a segmented myopic view is one where major conglomerates with large and heterogeneous agricul- source of loss of efficiency for the overall system. Fully autonomous ture vehicle fleets could operate on huge land areas to effect preci- farming, with multiple robots coordinating simultaneously with one sion farming. In this paper, we discuss distributed and decentralized another in the same farm, is still an open challenge. multi-agent coordination models applicable in AMR fleet coordina- Our focus is on scalable and efficient multi-agent models, partic- tion. Dynamic coordination approaches are reviewed focusing on the ularly dynamic task assignment (DTA) approaches applicable to het- application of the multi-index assignment problem and the classical erogeneous agriculture vehicle fleets operating on large-scale farms, assignment problem. We discuss some open issues and research op- potentially managing multiple crops. The main question is: How can portunities in this context. these technologies improve the efficiency and autonomy of agricul- ture machinery fleets while decreasing their cost and dependence on humans? 1 Introduction This paper is intended for researchers in distributed optimisation and multi-agent coordination, to highlight the possibilities of inte- The goal of sustainable agriculture is to meet society’s need for food grating these two fields with application in the real-world domain of and textiles without compromising the ability of future generations sustainable agriculture. We also address researchers in agriculture, to meet their own needs [53]. This requires the optimisation of in- by demonstrating the added value of the application of combinato- put resources (e.g. fuel, water, fertilisers) to maximise productivity, rial optimisation and multi-agent systems technologies to everyday quality and yield and minimise waste, costs and diseases while con- problems faced in agricultural settings. The content may be relevant sidering ecological factors by minimising application of pesticides. for researchers or practitioners who wish to learn more about and/or Developments in sustainable agriculture have led to the recent intro- engage with problems in this domain. In Section 2, we describe the duction of Agricultural Mobile Robots, or agri-robots, and Precision background and context of farming with agriculture machinery. Sec- Agriculture, designed to make the practice of farming more efficient, tion 3 presents main features of multi-agent architectures which are accurate, controlled and environmentally friendly [26] (e.g. reduc- applicable in this context. In Section 4, we introduce the dynamic ing greenhouse gasses, conserving water, minimising pesticides and agriculture vehicle fleet coordination problem. Section 5 describes protecting soil). state-of-the-art optimisation models and algorithms for multi-agent To date, agri-robotics research has focused on single robot sys- agriculture fleet coordination. Finally, we discuss some open issues tems and mostly on functional challenges: navigation, control, sens- and conclude the paper with future work in Section 6. ing, image processing, platform stability, terrain handling and hard- ware/software infrastructure (e.g. balancing computation between 2 Autonomy of agriculture vehicles edge and cloud architectures). Little work has examined efficient, scalable, real-time, dynamic fleet coordination, considering tactical In this section, we briefly describe the agriculture domain and then and operational agricultural setting constraints. This topic is of the define agri-robot autonomy within this context. utmost importance in commercial agriculture, where major conglom- Tractors are farm vehicles that provide traction powered by slow erates could operate huge land areas with precision farming. speed, high torque engines to mechanise agricultural tasks. These tasks include, among others, pulling or pushing of agricultural imple- 1 IMT Lille Douai, Univ. Lille, France, email: marin.lujak@imt-lille-douai.fr ments or trailers, tillage, plowing, disking, harrowing and planting. 2 Lincoln Institute for Agri-food Technology, University of Lincoln, UK, Agricultural tools, or implements, include: irrigation machinery (e.g. email: esklar@lincoln.ac.uk 3 Centrale Lille, France, email: frederic.semet@centralelille.fr 4 For example, a tractor pulling a tiller Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). central pivot irrigation systems, pumps, sprinklers), soil cultivation robots, tracks their performance in real time, and responds to contin- implements (e.g. trowels, spikes, harrows, plows, tillers), planting gencies. The higher the fleet’s operational costs, the more importance machines (e.g. drills, seeders, spreaders), and harvesting machines is given to the fleet’s coordination. Fleets are conventionally coordi- (e.g. trailers, diggers, pickers). These implements may be towed be- nated by dividing an area of interest into sectors, each one assigned hind or mounted on the tractor. The tractor may provide power for to a single human controller. Such a segmented myopic view is a the implement, if required. This flexibility means that a farmer can source of loss of efficiency for the overall system. purchase a tractor and a number of attachments (implements) with- Our aim is to shift the current centralised fleet coordination out needing to acquire and maintain multiple different types of spe- paradigm toward distributed FC systems for agri-robots. Fleet own- cialised farm vehicles. In general, implement mounting, attaching ers, farmers, agriculture vehicles, operators and controllers may and removal are still not suitable for automation but can be performed each be modelled as a rational agent, each with its own local con- by human operators in a matter of minutes. straints and decision-making objectives that should be optimised According to the levels of vehicle autonomy described in [59], we (e.g. [11, 60]). These objectives generally include finding a mini- focus on: tractors with driver assistance (level 1), semi-automated mum cost matching of agents, implements and tasks, applied to a set tractors (level 2–partial automation), driverless remotely super- of time periods. In this multi-agent dynamic task allocation context, vised tractors (level 3–conditional automation), driverless fully au- available vehicles, drivers and implements should be (re-) assigned tonomous tractors (level 4–high automation) and complete automa- to each other and to pending tasks as new tasks appear. tion (level 5). At the driver assistance level (1), there is no automated Generally, coordination may be defined as the process of organ- decision-making. Operational decisions are taken by a human driver ising people or groups so that they work together properly and (e.g. steering and path following), while a fleet controller makes tac- well [14]. By the coordination of agriculture vehicle fleets, we refer tical decisions about the vehicle(s) (e.g. path and task planning), su- to the organisation and management of decision-making within the pervises the performance of the whole fleet and performs tractor- agriculture fleet with the aim of improving given key performance field assignment. In the case of a semi-automated tractor (level 2), indicator(s) of a fleet’s task allocation. the driver’s only is to supervise the vehicle and handle emergencies. The topics of coordination and task allocation are the object of Driverless remotely supervised tractors (level 3) operate without a studies in multiple disciplines—e.g. operations research, economics human inside the tractor itself, but still under supervision of a human and computer science. The corresponding definitions and related controller positioned at a control station. These tractors use vehicle- concepts may vary based on the specific discipline at hand. In our sur- to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communication vey, and in the following, we focus on the specific issues of dynamic for receiving driving instructions from a remote human controller. task allocation and distributed vs decentralised coordination. Task A driverless fully autonomous tractor (level 4) is capable of inde- allocation problems in agriculture vehicle fleets consider providers pendently performing its assigned task while tracking its GPS posi- of farming services (fleet owner(s)), drivers, vehicles, and their cus- tion, controlling its speed and sensing and avoiding obstacles in front tomers (farm owners) and thus all of them may be considered active of it. The environment of an assigned task has to be deterministic participants in the farming process. (the task is defined before it starts and the next state of the environ- Based on the ownership of the fleet, its structure, and the level of ment is determined by the current state and the actions performed, decentralising coordination that we want to achieve in the fleet task e.g. following a predetermined path on a field) [15]. Any delay in allocation, we can design: decision-making for the action choice must be as small as possible, preferably instantaneous without hesitation or time-consuming cal- • a centralised coordination model, where the task allocation culations (e.g. changing the steering angle when necessary). Sensor problem is solved in a single block by only one decision-maker technologies improve safety by detecting unforeseen obstacles while (e.g. a single entity) having total control over and complete infor- reactive behaviours are for rapid response. Currently, the majority of mation about the vehicle fleet; fully autonomous tractors navigate using lasers that bounce signals • a distributed coordination model, in the context of small farm- off several mobile transponders located around the field. ers with only one vehicle fleet owner, where the global task al- Highly automated agriculture vehicles (level 5) are mostly ap- location problem is decomposed such that each farmer is repre- plied for weed control (e.g. [37]), seeding (e.g. [2, 8]), harvesting sented by an autonomous decision maker (agent) that may solve (e.g. [66, 71]), environmental monitoring (e.g. [36, 51] and soil anal- its own subproblem only using its own local decision variables ysis (e.g. [17, 68]). Completely autonomous agriculture systems are and parameters. The allocation of a limited number of agriculture expected to be realised in the future [50]. machinery (global constraints) is achieved through the interaction Autonomous tractors and agri-robots may also work in tandem between competing farmer agents and the vehicle fleet owner (a with traditional machines whose drivers supervise their activities. We single autonomous agent) having all the fleet information avail- limit our discussion to autonomous vehicles that can be programmed, able. Farmer agents that compete for resources are not willing to can interact with each other and with humans in real time. disclose their complete information but will share a part of it if it facilitates achieving their local objectives. The vehicle fleet owner 3 Decentralizing coordination for agri-robot fleets agent is responsible for achieving globally efficient resource allo- cation by interacting with farmer agents usually through an auc- Fleet Coordination (FC) systems are commonly used to coordinate tion. The problem decomposition here is done to gain computa- mobility and delivery services in a wide variety of domains. How- tional efficiency since farmer agents can compute their bids in par- ever, traditional top-down centralised control architectures become allel. However, the resource allocation decisions are still made by a bottleneck in open and dynamic environments such as agricul- a single decision maker (vehicle fleet owner) with the requirement ture, where scalability, proactiveness and autonomy are key factors on synchronous bidding of farmer agents (e.g. [21, 22, 69]); or for success. Conventional FC systems require a control centre (with • a decentralised coordination model, which further decentralises human operators) that monitors and coordinates each of the fleet’s the distributed model by allowing for multiple resource (vehicle) owner agents, multiple competing farmer and/or agents request- tion case in which, due to the lack of global information, quality of ing the farming service, and asynchrony in decision-making. Each solution guarantees generally do not exist. Further, due to the lack farmer and resource owner agent has access only to its local infor- of global non-obsolete and truthful information, in general, solution mation, with no global information available. Farmer agents are approaches for decentralised coordination concentrate on finding a responsible of the execution of a set of (possibly overlapping) field feasible (admissible) solution without quality of solution guarantees. tasks. The objective for the subset of tasks belonging to an indi- In contrast with the distributed case most often studied in the opera- vidual farmer agent is to perform them at a minimal overall cost, tions research field, where the emphasis is on the method’s optimal- which reflects in specific task constraints. The individual task allo- ity gap, decentralised coordination methods are mostly approximate cation cost here is less important than the overall cost of a compet- heuristics-based methods without quality of solution guarantees but itive farmer agent. A set of tasks belonging to each farmer agent with proven completeness, soundness and termination—hence most competes with the sets of tasks of other farmers for the fleet’s ve- appropriate for deployment in real-world, dynamic and messy envi- hicles held by multiple resource owners. Similarly, if the vehicles ronments such as agricultural robotics. are owned by multiple fleet owners, then each vehicle agent should coordinate the allocation of its tasks with other vehicle agents of the fleet such that the overall operational costs of the fleet owner in 4 Dynamic coordination of agri-robot fleets performing the allocated tasks are minimised. The decisions spec- Planning and scheduling of different stages of cultivation for each ifying these interactions emerge from local information. Fairness crop are based on agri-food production goals and agronomic needs. in resource allocation here plays a major role. The same as in the These are typically determined by tables for technical itineraries, distributed model, a competitive agent is not willing to disclose which describe the entire cycle of crop cultivation processes through- its complete information but will share a part of it if it facilitates out the year. For example, for the cultivation of maize in Spain, the achieving its local objective. Resource allocation here is achieved scheduling of tasks is: deep ploughing in January; stone removal by the means of a decentralised protocol. in February and March; harrowing, seeding and fertilisation, fertil- ising inserting, irrigation system, maintaining herbicide application Generally speaking, coordination is distributed when complex be- in April and May; preseeding irrigation, and seeding and soil dis- haviour within a system does not emerge due to the control of a sin- infection in June, etc. [61]. Technical itinerary tables also include gle agent (e.g. the system owner), but rather through interactions scheduling of labourers for each month, required equipment and and communication between individual agents, each operating on labour (driver/labourer), yield in hours per hectare of equipment and local information. This form of control is typically known as dis- labour, and raw material (units per hectare). tributed control, that is, control where each agent is equally respon- In this paper, we focus on large agriculture conglomerates that sible for contributing to the global, complex behaviour by acting ra- grow multiple crops simultaneously. This means that crops with dif- tionally and collaboratively with one another based on their local ferent needs will share the same agriculture resources and a hetero- information. Agents are implicitly aware of the interaction rules (e.g. geneous vehicle fleet. Each one of these crops requires labours that norms) through mechanisms that are based on the agent’s interac- need specific equipment for their implementation, usually a certain tion with other agents and the environment. The system behaviour type of tractor and a compatible implement with specific characteris- is then an emergent property of distributed coordination mechanisms tics. For example, for deep ploughing, we need a tractor and a chisel; (algorithms) that act upon agents, rather than the result of a control for stone removing, a tractor and a trailer. mechanism of one centralised system owner. The matching between tractors and implements is done depending In decentralised algorithms, no global clock is assumed, no agent on the compatibility and the characteristics of the tractors and the has complete information about the system’s state, every agent makes implements at hand, and the terrain to be cultivated. In the case of its own decisions based only on its local information and failure of traditional tractors, we also need to include drivers, their availability one agent does not prevent the system to continue running. An exam- and specialisation(s) in the matching problem. ple is BitCoin: instead of one central server owned and operated by a Fertilisers, herbicides, fungicides and growth regulators are typi- single entity, Bitcoin’s ledger is distributed across the globe, making cally applied at specific stages of plant development in quantities and it impossible to shut down, break in or hack, as there is no single frequencies that can depend dynamically on field conditions. These central bottleneck of the system. conditions may vary from one part of the field to another due to dif- We note here the main differences between distributed and decen- ferences in crop development, soil characteristics (e.g. inclination, tralised coordination models. Distributed coordination relies on both chemical structure, etc.), varying microclimate (e.g. local sun expo- local and shared (global) parameters and variables; decentralised sure, temperature, humidity), prevalence of pests (e.g. insects) and coordination only has access to local information. Local parame- weeds and plant disease development. Thus, tasks have to be planned ters and variables are private (known only to the agent who holds locally based on these differences and may vary from one field loca- them), whereas global parameters and variables are public and shared tion to another with given short-time weather windows in which they among two or more agents—potentially among all the agents in the have to be performed. Potentially, they may extend across a 24-hour system. If we assume selfish agents, in the case of distributed coor- working day. dination, resource owners can manipulate these parameters and vari- The matching is done based on the list of labours to perform in the ables or deceive agents in communicating their values to influence fields, field and weather conditions, availability of individual actors, the individual decision making of each one of them and thus obtain etc. For each vehicle, a schedule is given throughout the workday in the behaviour of the system the resource owner wants. This can be terms of a route to follow and the plan of labours to do in the field on prevented by ensuring individual agents have access to non-obsolete this route, as well as the remounting of implements when necessary. and truthful information—using e.g. blockchain technology. In this Work breaks are preplanned and incorporated into the schedule. case, reaching the globally optimal solution with a high-quality so- Planning and scheduling of these tasks should be performed con- lution guarantee is possible, contrary to the decentralised coordina- sidering available labour, machinery, and raw material, minimising the overall time of operations and costs, optimising the amount to architecture to integrate a vehicle equipped with a farm implement, produce (yield) and reducing environmental impact while maintain- with the purpose of constituting a fully autonomous agricultural unit ing products of quality. A daily task schedule for machines, imple- able to work cooperatively in a fleet of robots. To achieve this aim, ments, drivers, and controllers should be generated at the beginning characteristics of the required configuration are identified, complying of each work shift, usually each morning. However, the possibility with specifications of hardware reliability, modularity, expandabil- of execution of some tasks depends strongly on the weather condi- ity, ergonomics, maintenance and cost, for the purpose of providing tions that may change during the day. The quantity of irrigation wa- manufacturers of agricultural machinery with solutions for automat- ter, pesticides or fungicides, or herbicides depends also on weather ing new developments in precision agriculture. The results obtained, conditions. Thus, a planning and scheduling solution method must be both qualitative and quantitative, confirm the validity of their pro- dynamic, producing a farming schedule that is adaptable in real-time. posal. The objective is to optimally allocate the agriculture machinery An example of a centralised coordination model of a multi-agent system to a set of given tasks in a rolling horizon, responding dy- architecture is a centralised entity OptiVisor that coordinates a Mo- namically to unpredicted contingencies and considering route con- bile Agricultural Robot Swarm (MARS), presented in [8]. OptiVi- gestion and the constraints of each one of the actors in this prob- sor is responsible for path planning, optimisation and supervision of lem. Each task requires a tractor-implement combination, and in case MARS and serves as a mediator between the robots and different of traditional tractors, also including a driver capable of operating cloud services. with that combination on a given task. In the allocation process, the The problem of assignment (dispatch) is to decide a vehicle to be best vehicle-implement-driver (VID) combination should be found at assigned to each task. Conventionally, vehicles are assigned to tasks the global level while considering each task’s requirements and its based on the First Come, First Served (FCFS) strategy. This strat- time and space of allocation. The VID combination should be routed egy creates great discrimination among the tasks, increases transport through the field considering congestion on the farm or road, and it costs and significantly lowers overall fleet performance. Fleet man- should be reconfigured when necessary considering both overall sys- agement significantly improves if the vehicles are dynamically as- tem performance, weather conditions and individual task, driver, im- signed (in real time) depending on the characteristics of each vehicle plement and vehicle requirements. Tasks may need specific weather and task requirements (e.g. [5, 10, 30, 55]. conditions while some tasks may be more important than others. Various mathematical and computational models have been de- Implement parameters usually include: maintenance frequency veloped for the optimisation of fleet operations to serve customer (maximum time and distance passed in operation between two main- demands while minimising costs, e.g. [4, 13, 30, 40, 41, 43]. Many tenance activities), operation state (damaged, operating), efficiency of the problems of fleet management correspond to combinatorial level for each task, task compatibility (an implement can perform a optimisation problems, such as the problem of determining optimal subset of tasks), tractor compatibility (it can be installed on a sub- routes e.g. [10, 13, 30, 35, 41, 43], that are still very difficult to solve, set of tractors) and potentially implement cleaning (to avoid cross- even in a static context with batch processing of requests and dy- contamination of diseases across fields). namic vehicle assignment problems, e.g. [25, 31, 44]. Tractor parameters include: maintenance and cleaning frequency, In the case of poor fleet performance, a penalty for non- operation state, task compatibility and compatibility with imple- compliance with Service Level Agreements (SLAs) translates into ments and related requirements (power, weight, front power take-off the loss of revenue. For agri-robot fleets, optimal allocation of tasks (PTO) used for taking power from a power source, guidance sys- and well-designed routes to agri-robots not only ensure the service tem or not, front loader, specific tires, etc.), driver requirements, fuel level, but also meet the needs of the fleet owner and stakeholders autonomy, and type and number of operators needed for operation in a cost-effective and efficient manner. Nowadays, the assignment per each task. Human operator parameters include: operation status of agriculture machinery and agri-robots to crop tasks is still mostly (available, unavailable), daily and weekly work hours and breaks (ac- done by human experts (e.g. [23, 67]). cumulated, required), task preferences/specialisations and mobility limitations (by car, walking). The overall objective is for the agriculture vehicle fleet to dy- 5.1 Multi-index assignment problem namically (re-)allocate the vehicle-implement or vehicle-implement- The methods for dynamic agri-robot fleet task assignment are rel- driver combination for each task and to route the combination evant in various scenarios, e.g. emergency services [5, 31, 32, 55], through dynamically changing tasks considering vehicle, implement, taxi, hot meal home delivery and vehicle sharing. We believe that a driver, maintenance and charging constraints while minimising the combination of these methods can provide a true differential value overall cost of the fleet’s operation. for agri-robot fleets. The problem of allocation of the vehicles to implements and in- 5 Related standard combinatorial optimisation divisible tasks may be modelled as a multi-index assignment prob- problems and solution approaches lem [45] that we re-run in each time period when the constituents of the problem change. Each constituent part of this allocation is char- In this section, we research standard combinatorial optimisation acterised by a set of attributes describing its availability and com- problems that provide a baseline for the coordination problem ap- patibility with the rest of the constituents that influence the cost or plied to agriculture fleets, as described previously. We concentrate profit resulting from such a multi-index allocation. Assume there are on the dynamic versions of these problems, that is, the case when n vehicle agents, m tasks and k implements. Here, the emphasis is both task demand and resource availability may vary in time. on one-on-one assignment among the elements in each set. Further- The most important decisions that must be taken by fleet man- more, each vehicle agent has a valuation function that maps each agers have to do with the problems of assigning agriculture vehi- implement-task combination to some non-negative value particular cles to implements and tasks (e.g. [31]) and managing their routes to that vehicle agent. These valuations are additive, which means that (e.g. [7, 9, 18, 46, 48, 49, 64, 65]). Emmi [16] proposes a control an agent’s value for a set of task-implement combinations is simply the sum of the values of each combination of this set. Our goal is signment problem for which several centralised approaches exist, to compute a one-on-one allocation, i.e. a partitioning of m tasks, k e.g. [40]. One of the best known is the Hungarian method [28]. implements and n vehicle agents, of minimum overall cost. In [21], Lujak et al. proposed a distributed version of the Hungarian The mathematical formulation of such a problem leads to axial k- Method for multi-robot task allocation where mobile robot agents are index assignment problems [47] and in the case of three indices (ve- required to store all the information locally and there is no available hicles, implements and tasks), to the axial 3-index Assignment Prob- shared memory. One of the tools for mechanism design of agent sys- lem (axial 3AP), which is an NP-hard binary programming problem tems are auctions, e.g. [3, 33, 54]. Schneider and colleagues [56, 70] for which the only scalable and efficient solution approach is based studied task allocation in the context of multi-robot teams and eval- on (meta-)heuristics (e.g. [62]). Moreover, no polynomial-time al- uated the efficacy of auction-based mechanisms when implemented gorithm can achieve a constant performance ratio for this problem on simulated and physical robots. This work highlights the levelling unless P = NP [12]. Crama and Spieksma designed approximation effects of real-world constraints, such as collision avoidance, which algorithms that yield a feasible solution whose value is not worse tend to minimise the differences between allocation mechanisms. than 3/2 of the optimal value when the overall assignment cost is a The implementation usually requires solving a combinatorial non- decomposable sum of the costs of all the three set pairs [12]. linear optimisation problem, which is in general NP-hard and in- Reynen et al. [52] present alternate integer programming formu- tractable for complex networks. However, with certain relaxations, lations for the multi-dimensional assignment problem with decom- the latter can be modelled as a convex optimisation problem [3, 42]. posable costs with an increased number of variables and present so- Computational optimisation auctions are methods that are similar lution methods based on Lagrangian Relaxation and massively par- to the Gauss-Seidel and Jacobii methods, e.g. [3]. This approach allel algorithms. Aiex et al. [1] designed a greedy randomized adap- is well suited for massive parallelisation of local decision-making tive search procedure with path relinking (GRASP) for solving axial based on the information interchanged among multiple processors. 3APs. GRASP is a multistart metaheuristic for combinatorial opti- It is modular, based on regular interactions, incremental, analysable, mization consisting of a construction procedure based on a greedy and permits incentive engineering. In [33, 34], Lujak et al. proposed randomized algorithm and a local search. A parallel version appeared a modified version of Bertsekas’ auction algorithm for the case of in [39]. Their computational experiments showed very good results incomplete information exchange and explored the deterioration of compared with previously proposed heuristics. Huang and Lim [24] the solution quality according to the size of the communication net- proposed a hybrid genetic algorithm for this problem and reported on work and proposed strategies to overcome this problem. Responding extensive computational experiments. Li et al. [29] propose a novel to the task assignment in the case of the medical emergency assis- convex dual approach to the three-dimensional assignment problem. tance of emergency patients by ambulances, Lujak et al. proposed It is shown that the proposed dual approach is equivalent to the La- a distributed algorithm for the simultaneous assignment of ambu- grangian relaxation method in terms of the best value attainable by lances [5, 31] and ambulances and hospitals to multiple simultaneous the two approaches. However, the pure dual representation is not only patients in [32], where the authors also proposed an ambulance vehi- more elegant, but also makes the theoretical analysis of the algorithm cle Voronoi-based relocation approach. Through a dynamic vehicle more tractable. reassignment, we can significantly increase the overall performance An asymptotical optimal approximation algorithm for axial k- of the fleet and lower farming costs. index assignment problems was given by Kravtsov [27]. Frieze et al. [19] study random multi-dimensional assignment problems where the costs decompose into the sum of independent random variables. 6 Open issues and research opportunities They minimise the total cost and show that with high probability a Agri-robot fleets are intrinsically decentralised systems. They com- simple greedy algorithm is a (3 + O(1))-approximation. An adaptive prise a number of geographically distributed agri-robots capable of algorithm that extends the basic greedy-type algorithmic schemes us- communicating with each other and possibly with fixed infrastruc- ing transition to a probabilistic setup based on variables randomisa- ture sensors on the field and/or with human collaborators. Tradi- tion for solving the axial 3-Index AP was also proposed [38]. Here, tionally, distributed systems refer to systems consisting of sequen- the minimisation of an objective function is replaced by the minimi- tial processes (each one with an independent thread of control, pos- sation of its expectation. sibly located on geographically distributed processors) that coordi- nate their actions by exchanging messages to meet a common goal 5.2 Assignment problem (e.g. [20, 63]). Distributed MAS-based route guidance for agri-robot fleets that The multi-index assignment problem is a higher dimensional ver- reach towards completely autonomous fleets is still an open scientific sion of the standard linear (two-dimensional) assignment problem, question. The topic of distributed and dynamic multi-task assignment i.e. a weighted bipartite matching problem in which the objective is and vehicle routing considering multiple vehicle, operator and farm- to minimise total cost of assigning n resources to n tasks. The latter ing constraints is still an insufficiently explored field. To the best is an important subproblem of many NP-hard optimisation problems, of our knowledge, distributed and decentralised MAS coordination e.g. Traveling Salesperson Problem, for which both sequential (Hun- models and optimisation approaches for vehicle fleet coordination garian algorithm, shortest path algorithms and auction algorithms) are scarce and have undergone limited testing. and parallel implementations of these algorithms are known. In this paper, we have discussed the levels of decentralizing coor- In the case where sets of fixed vehicle-driver-implement combina- dination of agri-robot fleets, from centralized over distributed, to the tions are static and given in advance, each such combination can be decentralized coordination models. Depending on the vehicle own- considered as an agent. Then, the multi-index assignment problem is ership context, a distributed or decentralized MAS may be applied; simplified to the assignment problem focusing on the one agent-one if there is only one fleet owner, we speak about the distributed case. task allocation at the time (e.g. [6, 32]). Otherwise, the decentralized case applies. The distributed and decen- The dynamic task assignment problem is equivalent to the as- tralized coordination models are more robust than their centralised counterparts because they are resilient to individual vehicle errors nation mechanisms may not fix the sustainable agriculture concerns, and can rely on their intrinsic built-in redundancy. They are scal- but they should improve them as they are directly related to giving able since they can operate at a larger scale and assist more fields at higher autonomy to the vehicle fleet while changing the hierarchical once aggregating vehicle capacity and field throughput across all the and unscalable farming structure to a more efficient balanced one. fleet’s vehicles. They are open, seamlessly adapting to vehicles en- tering or leaving the system, and they have fewer levels of authority. Finally, they do not suffer from the “single point of failure” prob- References lem found in centralised systems. However, distributed open vehicle fleets also have to deal with inter-agent communication and coordi- [1] Renata M Aiex, Mauricio GC Resende, Panos M Pardalos, and Ger- nation overhead that can sometimes make them slower or more diffi- ardo Toraldo, ‘Grasp with path relinking for three-index assignment’, INFORMS Journal on Computing, 17(2), 224–247, (2005). cult to control than their centralised counterparts. The decentralized [2] Amir Asghar Ali, Muhammad Zohaib, and Syed Atif Mehdi, ‘An au- fleets, on the other hand, lack the guarantees on solution quality. tonomous seeder for maize crop’, in Proceedings of the 2019 5th Following a decentralized solution approach, the agriculture ve- International Conference on Robotics and Artificial Intelligence, pp. hicle fleet coordination problem combines the aspects of the as- 42–47, (2019). signment problem, 3-index assignment problem and vehicle routing [3] Dimitri P Bertsekas, ‘Auction algorithms for network flow problems: A tutorial introduction’, Computational optimization and applications, problem. There are multiple centralised algorithms that work for each 1(1), 7–66, (1992). of these individual subproblems assuming perfect information, but to [4] Maurizio Bielli, Alessandro Bielli, and Riccardo Rossi, ‘Trends in the best of our knowledge, both the mathematical formulation for the models and algorithms for fleet management’, Procedia-Social and overall agriculture vehicle fleet coordination problem and the related Behavioral Sciences, 20, 4–18, (2011). [5] Holger Billhardt, Alberto Fernández, Lissette Lemus, Marin Lujak, solution approach are still open challenges. Nardine Osman, Sascha Ossowski, and Carles Sierra, ‘Dynamic coordi- In the decision-making distribution process, the emphasis of the nation in fleet management systems: Toward smart cyber fleets’, IEEE decomposition of the MAS coordination problem should be on the Intelligent Systems, 29(3), 70–76, (2014). scalability, local communication and computation constraints of each [6] Holger Billhardt, Marin Lujak, Vicente Sánchez-Brunete, Alberto physical vehicle agent, the structure and topology of the dynamic Fernández, and Sascha Ossowski, ‘Dynamic coordination of ambu- lances for emergency medical assistance services’, Knowledge-Based communication network, and the available communication and pro- Systems, 70, 268–280, (2014). cessing capacities of the developed cyber-physical MAS. One com- [7] Sixtine Binart, Pierre Dejax, Michel Gendreau, and Frédéric Semet, mon goal in this context is an efficient and cost-effective farming ‘A 2-stage method for a field service routing problem with stochastic service using an agriculture vehicle fleet while considering vehicle travel and service times’, Computers & Operations Research, 65, 64– 75, (2016). autonomy and fairness constraints in work assignment, individual ra- [8] Timo Blender, Thiemo Buchner, Benjamin Fernandez, Benno tionality, preferences and constraints whether it is of operators, farm- Pichlmaier, and Christian Schlegel, ‘Managing a mobile agricul- ers or fleet owner(s), as well as farming tasks’ constraints. Quality of tural robot swarm for a seeding task’, in IECON 2016-42nd Annual solution guarantees play a crucial role underlying sustainable com- Conference of the IEEE Industrial Electronics Society, pp. 6879–6886. petitive advantage. IEEE, (2016). [9] Luce Brotcorne, Gilbert Laporte, and Frederic Semet, ‘Ambulance loca- The long-term goal of distributing decisions in agriculture vehicle tion and relocation models’, European journal of operational research, fleets is the development of an open and non-proprietary software 147(3), 451–463, (2003). platform in a cloud for distributed route guidance and task coordi- [10] Bernard K-S Cheung, KL Choy, Chung-Lun Li, Wenzhong Shi, and nation at large agriculture farms and peer-to-peer sharing of relevant Jian Tang, ‘Dynamic routing model and solution methods for fleet man- agement with mobile technologies’, International Journal of Production agriculture resources, vehicles and agri-robots among farmers. Such Economics, 113(2), 694–705, (2008). an agri-robot fleet coordination approach contributes to a more ef- [11] Amélie Chevalier, Cosmin Copot, Robin De Keyser, Andres Hernan- ficient and competitive service in line with the Internet of Robotic dez, and Clara Ionescu, ‘A multi agent system for precision agriculture’, Things (e.g. [57]) and Internet of Food Things [58]. Human drivers in Handling Uncertainty and Networked Structure in Robot Control, may also benefit from this technology as they may be motivated to 361–386, Springer, (2015). [12] Yves Crama and Frits CR Spieksma, ‘Approximation algorithms for perform better if they feel a sense of autonomy, thus improving the three-dimensional assignment problems with triangle inequalities’, output, task engagement, time-on-task and accuracy. However, be- European Journal of Operational Research, 60(3), 273–279, (1992). havioural measures should be further studied to understand the trig- [13] Jacques Desrosiers, Yvan Dumas, Marius M Solomon, and François gers of individual effort and motivation. Soumis, ‘Time constrained routing and scheduling’, Handbooks in operations research and management science, 8, 35–139, (1995). Even though scalable coordination mechanisms are essential for [14] Merriam-Webster Dictionary, ‘Coordination— definition of coordina- efficiently managing large-scale distributed and decentralized agri- tion by merriam-webster’, Retrieved January, 21, 2020, (2020). robot fleets, it should be noted that, for real-world applications, they [15] Luis Emmi, Mariano Gonzalez-de Soto, Gonzalo Pajares, and Pablo need to be complemented with other technologies. In particular, se- Gonzalez-de Santos, ‘New trends in robotics for agriculture: integration mantic mismatches among agents need to be dealt with through the and assessment of a real fleet of robots’, The Scientific World Journal, 2014, (2014). alignment of ontologies, so agents can reach a common understand- [16] Luis Alfredo Emmi, ‘Contributions to the configuration of fleets of ing about the elements of coordination. In addition, trust and reputa- robots for precision agriculture’, Technical report, CSIC-Centro de Au- tion models are necessary for keeping track of whether the coordina- tomática y Robótica (CAR), (2014). tion plan and its execution respect the requirements defined a priori. [17] Haley Finegan, Seth Jaffe, Angela Leon, Kim Lytle, Edward Mor- gan, Charlotte Greene, Anne Meyer, Bethany Brinkman, Stephan The indirect benefits of such a distributed or decentralised agri- De Wekker, Hank Yochum, et al., ‘Development of an autonomous robot fleet coordination MAS (depending on the vehicle ownership agricultural vehicle to measure soil respiration’, in 2019 Systems and context), among others, should include higher efficiency and benefit Information Engineering Design Symposium (SIEDS), pp. 1–6. IEEE, in large farms, smaller carbon footprint and reduction in pesticides, (2019). and above all, fair participation of fleet owners, agri-robot operators [18] Fabien Malca Frédéric Semet, ‘Les problèmes de gestion de flotte en temps réel’, INFOR: Information Systems and Operational Research, and farmers with related rewards and benefits. Decentralised coordi- 44(4), 299–330, (2006). [19] Alan Frieze, Wesley Pegden, and Tomasz Tkocz, ‘On random multi- [41] Beatrice Ombuki, Brian J Ross, and Franklin Hanshar, ‘Multi-objective dimensional assignment problems’, arXiv preprint arXiv:1901.07167, genetic algorithms for vehicle routing problem with time windows’, (2019). Applied Intelligence, 24(1), 17–30, (2006). [20] Sukumar Ghosh, Distributed systems: an algorithmic approach, Chap- [42] Daniel Pérez Palomar and Mung Chiang, ‘A tutorial on decompo- man and Hall/CRC, 2014. sition methods for network utility maximization’, Selected Areas in [21] Stefano Giordani, Marin Lujak, and Francesco Martinelli, ‘A dis- Communications, IEEE Journal on, 24(8), 1439–1451, (2006). tributed algorithm for the multi-robot task allocation problem’, [43] Sophie N Parragh, Karl F Doerner, and Richard F Hartl, ‘A survey on in International Conference on Industrial, Engineering and Other pickup and delivery problems’, Journal für Betriebswirtschaft, 58(1), Applications of Applied Intelligent Systems, pp. 721–730. Springer, 21–51, (2008). (2010). [44] David W Pentico, ‘Assignment problems: A golden anniversary sur- [22] Stefano Giordani, Marin Lujak, and Francesco Martinelli, ‘A dis- vey’, European Journal of Operational Research, 176(2), 774–793, tributed multi-agent production planning and scheduling framework (2007). for mobile robots’, Computers & Industrial Engineering, 64(1), 19–30, [45] William P Pierskalla, ‘Letters to the editor — the multidimensional as- (2013). signment problem’, Operations Research, 16(2), 422–431, (1968). [23] Sami Salama Hussen Hajjaj and Khairul Salleh Mohamed Sahari, ‘Re- [46] Victor Pillac, Michel Gendreau, Christelle Guéret, and Andrés L view of research in the area of agriculture mobile robots’, in The Medaglia, ‘A review of dynamic vehicle routing problems’, European 8th International Conference on Robotic, Vision, Signal Processing & Journal of Operational Research, 225(1), 1–11, (2013). Power Applications, pp. 107–117. Springer, (2014). [47] Aubrey B Poore, ‘Multidimensional assignment formulation of data as- [24] Gaofeng Huang and Andrew Lim, ‘A hybrid genetic algorithm sociation problems arising from multitarget and multisensor tracking’, for three-index assignment problem’, in The 2003 Congress on Computational Optimization and Applications, 3(1), 27–57, (1994). Evolutionary Computation, 2003. CEC’03., volume 4, pp. 2762–2768. [48] Harilaos N Psaraftis, ‘Dynamic vehicle routing problems’, Vehicle IEEE, (2003). routing: Methods and studies, 16, 223–248, (1988). [25] Sarah Ibri, Mustapha Nourelfath, and Habiba Drias, ‘A multi-agent ap- [49] Harilaos N Psaraftis, Min Wen, and Christos A Kontovas, ‘Dynamic ve- proach for integrated emergency vehicle dispatching and covering prob- hicle routing problems: Three decades and counting’, Networks, 67(1), lem’, Engineering Applications of Artificial Intelligence, 25(3), 554– 3–31, (2016). 565, (2012). [50] Redmond R Shamshiri, Cornelia Weltzien, Ibrahim A Hameed, Ian [26] Anthony King, ‘The future of agriculture’, Nature, 544(7651), S21– J Yule, Tony E Grift, Siva K Balasundram, Lenka Pitonakova, Desa S23, (2017). Ahmad, and Girish Chowdhary, ‘Research and development in agri- [27] VM Kravtsov, ‘Polynomial algorithms for finding the asymptoti- cultural robotics: A perspective of digital farming’, Chinese Society of cally optimum plan of the multiindex axial assignment problem’, Agricultural Engineering, (2018). Cybernetics and Systems Analysis, 41(6), 940–944, (2005). [51] Ankit A Ravankar, Abhijeet Ravankar, Yukinori Kobayashi, and [28] Harold W Kuhn, ‘The hungarian method for the assignment problem’, Takanori Emaru, ‘Autonomous navigation of ground robot for vine- Naval research logistics quarterly, 2(1-2), 83–97, (1955). yard monitoring’, in The Proc. of JSME Annual Conf. on Robotics and [29] Jingqun Li, R Tharmarasa, Daly Brown, Thia Kirubarajan, and Kr- Mechatronics (Robomec) 2019, pp. 1A1–E05. The Japan Society of ishna R Pattipati, ‘A novel convex dual approach to three-dimensional Mechanical Engineers, (2019). assignment problem: theoretical analysis’, Computational Optimization [52] Olivia Reynen, Samhita Vadrevu, Rakesh Nagi, and Keith LeGrand, and Applications, 74(2), 481–516, (2019). ‘Large-scale multi-dimensional assignment: Problem formulations and [30] Sandro Lorini, Jean-Yves Potvin, and Nicolas Zufferey, ‘Online vehi- gpu accelerated solutions’, in 2019 22th International Conference on cle routing and scheduling with dynamic travel times’, Computers & Information Fusion (FUSION), pp. 1–8. IEEE, (2019). Operations Research, 38(7), 1086–1090, (2011). [53] Johan Rockström, John Williams, Gretchen Daily, Andrew Noble, [31] Marin Lujak and Holger Billhardt, ‘Coordinating emergency medical Nathanial Matthews, Line Gordon, Hanna Wetterstrand, Fabrice De- assistance’, in Agreement Technologies, 597–609, Springer, (2013). Clerck, Mihir Shah, Pasquale Steduto, et al., ‘Sustainable intensifi- [32] Marin Lujak, Holger Billhardt, and Sascha Ossowski, ‘Distributed co- cation of agriculture for human prosperity and global sustainability’, ordination of emergency medical service for angioplasty patients’, Ambio, 46(1), 4–17, (2017). Annals of Mathematics and Artificial Intelligence, 78(1), 73–100, [54] Eric Schneider, Ofear Balas, A Tuna Özgelen, Elizabeth I Sklar, (2016). and Simon Parsons, ‘An Empirical Evaluation of Auction-based [33] Marin Lujak and Stefano Giordani, ‘On the communication range Task Allocation in Multi-Robot Teams’, in Proceedings of the 13th in auction-based multi-agent target assignment’, in Self-Organizing International Conference on Autonomous Agents and Multiagent Systems, eds., C. Bettstetter and C. Gershenson, volume 6557 of LNCS, Systems (AAMAS), Paris, France, (May 2014). 32–43, Springer, (2011). [55] Eric Schneider, Marcus Poulton, Archie Drake, Leanne Smith, George [34] Marin Lujak, Stefano Giordani, and Sascha Ossowski, ‘Value of incom- Roussos, Simon Parsons, and Elizabeth I Sklar, ‘The Application of plete information in mobile target allocation’, in German Conference Market-based Multi-Robot Task Allocation to Ambulance Dispatch’, on Multiagent System Technologies, pp. 89–100. Springer, (2011). ArXiv, abs/2003.05550, (2020). [35] Marin Lujak, Stefano Giordani, and Sascha Ossowski, ‘Route guid- [56] Eric Schneider, Elizabeth I Sklar, and Simon Parsons, ‘Evaluating ance: Bridging system and user optimization in traffic assignment’, multi-robot teamwork in parameterised environments’, in Proceedings Neurocomputing, 151, 449–460, (2015). of the 17th Towards Autonomous Robotic Systems (TAROS) [36] Wenhao Luo, Changjoo Nam, George Kantor, and Katia Sycara, ‘Dis- Conference, pp. 301–313, (2016). tributed environmental modeling and adaptive sampling for multi-robot [57] Pieter Simoens, Mauro Dragone, and Alessandro Saffiotti, ‘The inter- sensor coverage’, in Proceedings of the 18th International Conference net of robotic things: A review of concept, added value and appli- on Autonomous Agents and MultiAgent Systems, pp. 1488–1496. In- cations’, International Journal of Advanced Robotic Systems, 15(1), ternational Foundation for Autonomous Agents and Multiagent Sys- 1729881418759424, (2018). tems, (2019). [58] Simon Pearson and Jeremy Frey and Roger Maull and Gerard Parr and [37] Flavio BP Malavazi, Remy Guyonneau, Jean-Baptiste Fasquel, Se- Andrea Zisman and, ‘Internet of Food Things Network Plus: event re- bastien Lagrange, and Franck Mercier, ‘Lidar-only based naviga- port series’, Technical Report IoFT-Event-Series:Report001, University tion algorithm for an autonomous agricultural robot’, Computers and of Lincoln, UK, (2018). electronics in agriculture, 154, 71–79, (2018). [59] Jean-Paul Skeete, ‘Level 5 autonomy: The new face of disruption in [38] Sergey N Medvedev and Olga A Medvedeva, ‘An adaptive algorithm road transport’, Technological Forecasting and Social Change, 134, 22– for solving the axial three-index assignment problem’, Automation and 34, (2018). Remote Control, 80(4), 718–732, (2019). [60] Kouah Sofia and Kitouni Ilham, ‘Multi-layer agent based architec- [39] RA Murphey, PM Pardalos, and L Pitsoulis, ‘A parallel grasp for ture for internet of things systems’, Journal of Information Technology the data association multidimensional assignment problem’, in Parallel Research (JITR), 11(4), 32–52, (2018). processing of discrete problems, 159–179, Springer, (1999). [61] Magnus L Sørensen, Agricultural water management research trends, [40] Rahul Nair and Elise Miller-Hooks, ‘Fleet management for vehicle Nova Publishers, 2008. sharing operations’, Transportation Science, 45(4), 524–540, (2011). [62] Frits CR Spieksma, ‘Multi index assignment problems: complexity, ap- proximation, applications’, in Nonlinear assignment problems, 1–12, Springer, (2000). [63] Andrew S Tanenbaum and Maarten Van Steen, Distributed systems: principles and paradigms, Prentice-Hall, 2007. [64] Paolo Toth and Daniele Vigo, The vehicle routing problem, SIAM, 2002. [65] Paolo Toth and Daniele Vigo, Vehicle routing: problems, methods, and applications, SIAM, 2014. [66] Ya Xiong, Yuanyue Ge, Lars Grimstad, and Pål J From, ‘An au- tonomous strawberry-harvesting robot: Design, development, integra- tion, and field evaluation’, Journal of Field Robotics, (2019). [67] Sajjad Yaghoubi, Negar Ali Akbarzadeh, Shadi Sadeghi Bazargani, Sama Sadeghi Bazargani, Marjan Bamizan, and Maryam Irani Asl, ‘Au- tonomous robots for agricultural tasks and farm assignment and fu- ture trends in agro robots’, International Journal of Mechanical and Mechatronics Engineering, 13(3), 1–6, (2013). [68] Xiu-Tian Yan, Alessandro Bianco, Cong Niu, Roberto Palazzetti, Gwenole Henry, Youhua Li, Wayne Tubby, Aron Kisdi, Rain Irshad, Stephen Sanders, et al., ‘The agrirover: a reinvented mechatronic platform from space robotics for precision farming’, in Reinventing Mechatronics, 55–73, Springer, (2020). [69] Michael M Zavlanos, Leonid Spesivtsev, and George J Pappas, ‘A dis- tributed auction algorithm for the assignment problem’, in 2008 47th IEEE Conference on Decision and Control, pp. 1212–1217. IEEE, (2008). [70] Dingdian Zhang, Eric Schneider, and Elizabeth I Sklar, ‘A Cross- Landscape Evaluation of Multi-Robot Team Performance in Static Task-Allocation Domains’, in Proceedings of the 20th Towards Autonomous Robotic Systems (TAROS) Conference, (2019). [71] Yuanshen Zhao, Liang Gong, Yixiang Huang, and Chengliang Liu, ‘A review of key techniques of vision-based control for harvesting robot’, Computers and Electronics in Agriculture, 127, 311–323, (2016).