Isabelle Fantoni

Olivier Kermorgant

Sébastien Ecault

I am so thankful to those who

INTRODUCTION

With recent rapid advancements in technology, the fourth industrial revolution, industrial 4.0, is born with the emphasis on smart factory1 . With this trend, warehouses and distribution centers (DC) start to adopt automation and robotics in their daily operations. In fact, they can leverage multi-robot system (MRS) technology to greatly benefit from its robustness and efficiency compared to single-robot systems [START_REF] Gautam | A review of research in multi-robot systems[END_REF]. As the name suggested, MRS is a robotics system formed by multiple robots; they may or may not cooperate and communicate with each other to accomplish certain tasks. The tasks can be found in a wide range of applications. Patrolling [START_REF] Popescu | Multi-cycle Coverage for Multi-robot Patrolling -application to data collection in WSNs[END_REF] is one of them, which requires robots to visit certain places over and over again. The task is to divide roles and coverage areas between multiple robots. Exploration and mapping is also a subject of interest applying to MRS. The benefits of having multiple robots performing this task are shown in [START_REF] Christopher | A novel low-cost, limited-resource approach to autonomous multi-robot exploration and mapping[END_REF]. On the other hand, a task that corresponds the most to the automatizing warehouses and DC is the load transportation task. Indeed, not only it can improve efficiency, but also workers' safety. According to the data from the U.S. Bureau of Labor Statistics (BLS), the rate of recordable illness and injury cases in the warehousing and storage sector was 4.8 out of 100 workers in 2020 2 .

Formation control is a basis of the MRS when dealing with transportation tasks, especially for a heavy load that requires more than one robot working together to move it. Formation control can be seen as a problem of driving robots to a desired geometric shape, which is, normally, defined by inter-distances between robots in the group [START_REF] Miao | Distributed Estimation and Control for Leader-Following Formations of Nonholonomic Mobile Robots[END_REF]. Depending on the hardware setups and transporting scenarios, the team's formation can be a rigid or flexible shape. For instance, the formation in [START_REF] Wang | Kinematic multi-robot manipulation with no communication using force feedback[END_REF] does not need to be rigid because of the gripper attached to each robot. In contrast, our goal is to transport the load by placing it directly on top of the robots. The challenge of our aim is to be able to use any commercial off-the-shelf robot for the task without needing to heavily modify or customize the robots. Therefore, a rigid formation is required for such a mission. Formation control enables a group of robots to cooperatively carry a load. However, it does not decide which robot should be chosen for the formation team; this is where multi-robot task allocation (MRTA) is needed. MRTA problems are NP-hard optimization problems whose aim is to assign robots to tasks in an optimal manner [START_REF] Hussein | Hybrid Optimization-Based Approach for Multiple Intelligent Vehicles Requests Allocation[END_REF]. The problem is usually expressed as a cost function that is defined based on the context and requirements of the system. Since our main application of interest is logistics in warehouses, tasks to be allocated can require either single (simple pick-and-place mission) or multiple robots (heavy/huge load transportation). Tasks may be defined as a static list to be allocated at once as well as dynamically added online during the operation. Total execution time, which includes time to do allocation and time to complete the mission, is considered the optimizing parameter. Two different allocation approaches are studied in order to determine the most suitable for these constraints: Contract Net Protocol (CNP) and Tabu Search (TS). CNP is an auction-based approach that consists of an auctioneer, whose job is to send out proposals of tasks, and a group of robots, which send their bids back to the auctioneer for the tasks [START_REF] Noack | Negotiation Protocol Comparison for task allocation in highly dynamic environments[END_REF]. TS is a local search method that allows the search to step on worse solution neighbors, thus escaping the local minimum. A tabu list is introduced to store sets of banned solutions for several iterations to avoid cycling [START_REF] Laporte | Chapter 4: Heuristics for the Vehicle Routing Problem[END_REF]. A practical use case concerning the application in the warehouse is shown in Figure 1. In a given environment, numerous robots co-exist in order to help the operators moving things from one point to another. This is where task allocation is needed to adequately match a robot with a mission. Moreover, if the load to be placed on top is heavy or huge, thus a group of robots is needed, the formation control is required in order to avoid the load to slip off. The formation can be in various shapes and sizes of the number of robots. In addition to cooperative navigation, the team also has to be able to reactively avoid any obstacles that are not already mapped in the environment. This thesis tries to answer this use case. The goal of this PhD research is to develop and implement in an industrial environment a cooperative load-transporting system by leveraging the multi-robot system. A group of nonholonomic mobile robots is used to carry the load on top. Since there are usually more robots than required for a task in a real-world scenario, multi-robot task allocation is required to efficiently choose adequate robots. The contributions of this thesis are as follows: 1) adaptation of a consensus flocking algorithm to formation control for the nonholonomic system, 2) improvement to the obstacle avoidance of the former algorithm such that the formation remains rigid while evading the obstacle, 3) proposition of an optimization-based formation control that decomposes the transportation task into multiple cost objectives with different priority levels. Hierarchy quadratic programming is then used to solve for an optimal formation control that can preserve the shape during navigation, and 4) comparison of two task allocation methods: CNP and TS, in order to determine a suitable approach for our application.

This thesis acts as a testament to the effectiveness of the collaboration between academic lab and company. In fact, this research project is proposed to the LS2N lab3 by E-COBOT4 , a manufacturer of mobile robots whose mission is to provide flexible and reconfigurable logistics solutions for warehouses and factories. Parts of this work will be implemented directly to the robot fleet of E-COBOT, named Husky. It is important to show that the research done in the scientific lab can be practically deployed in a commercially viable way.

The thesis starts with an overview of the state-of-the-art of multi-robot system. In this first chapter, we present different types of control architectures as well as control strategies for both the formation and task allocation. Chapter 2 presents the work done for the formation control. This chapter includes the two proposed controllers for formation: consensus-based and optimization-based. Simulation and experimental results of these two approaches are also presented in this chapter. The comparison work of task allocation can be found in chapter 3, where details of the two approaches are introduced along with the simulations of different study cases. Last but not least, the overall conclusion and perspectives for future work are discussed in the final chapter.

Publications Journal article

Daravuth Koung, Olivier Kermorgant, Isabelle Fantoni, and Lamia Belouaer, "Cooperative Multi-Robot Object Transportation System Based on Hierarchical Quadratic Programming", IEEE Robotics and Automation Letters, Oct., 2021, vol. 6, pp. 6466-6472. (This paper was also selected for presentation at the 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS))

Chapter 1

STATE OF THE ART

Introduction

In this chapter, an overview of the work related to the multi-robot system (MRS) is presented. We start with a classification of control architecture used in the MRS. Then, we present state-of-the-art techniques for formation control, which is followed by an introduction to various load handling strategies. These strategies focus particularly on logistics problems, which corresponds to our application scenarios. Finally, a general review of the multi-robot task allocation methods is presented.

As the MRS is a broad field of research, the reviews of literature in the following sections focus on pure interaction between mobile robots. It does not discuss other forms of MRS such as collaborative robotic manipulators or human-robot interaction.

Control architecture

The research activities of the multi-robot system have been taken off as early as the late 80s; work done in [START_REF] Asama | Design Of An Autonomous And Distributed Robot System: Actress[END_REF] and [START_REF] Caloud | Indoor automation with many mobile robots[END_REF] are some of the earliest scientific researches in the field. Since then, many studies have been conducted; these works mainly fall into three control architectures [START_REF] Yan | A Survey and Analysis of Multi-Robot Coordination[END_REF][VR21]: centralized, distributed, and hierarchical.

In this section, we discuss the differences between these control architectures including their advantages and disadvantages.

Centralized architecture

This architecture is based on a central control agent as shown in Figure 1.1. This controller can be an external server or a robot in the team. In order to coordinate and generate control command of the overall system, it requires the states of all robots in the group. Since the controller receives every robot's state, the main advantage of this control structure is the global knowledge of each robot in the group, which is crucial for optimal decisions and performance. However, this architecture suffers an issue of robustness and reliability since the group of robots depends on a central controller. In addition, it, generally, requires higher computation power compared to other control architectures, which diminishes the system's scalability [START_REF] Yan | A Survey and Analysis of Multi-Robot Coordination[END_REF].

Control architecture

Distributed architecture

This control architecture allows each robot to make its own decisions. As shown in Figure 1.2, this architecture is based on the idea of sharing information between neighbors. Each robot makes decisions independently with respect to others' states; there is no single-point controller. The exchanging information can be anything from velocity, and position to sensor data such as lidar scan points or camera images depending on the needs of the system. Due to the nature of having no central controller, reliability is one of its main advantages. In fact, it responds better to changing or unknown environments. Moreover, it is also suitable for large and scalable systems because the communication is limited to within the interaction range between neighbors. However, this could lead to a solution that is often suboptimal in terms of stability and convergence rate [START_REF] Yan | A Survey and Analysis of Multi-Robot Coordination[END_REF].

There is a growing interest in this type of control architecture; in some literature, however, this controller is referred to as decentralized. This could be because of the researchers' backgrounds and specialty differences.

Hierarchical architecture

This architecture is a mixture of the centralized and distributed control structure; there could be more than one central controller, where each controller is in charge of a local cluster of robots. Figure 1.3 illustrates a hierarchical architecture; there are two local central agents (Robot 1 and Robot 2 ) for coordinating their respective cluster. This control approach is, generally, implemented in an environment where there exist numerous independent tasks; each task required an individual or a group of robots. Compared to distributed, this architecture is less robust; but requires less communication between robots. Similar to the distributed situation, this type of control is called, interchangeably, as hybrid in the literature.

Formation control

The formation is one of many applications of the MRS. Formation control can be seen as a problem of driving robots to a desired geometric shape, which is, normally, defined by the inter-distance between robots in the network [START_REF] Miao | Distributed Estimation and Control for Leader-Following Formations of Nonholonomic Mobile Robots[END_REF]. Numerous control strategies can be, interestingly, seen in the literature. Some of which are [START_REF] Hou | A survey on the formation control of multiple quadrotors[END_REF]: leader-follower, virtual structure, and behavior-based approach, which we will explore in this section.

Leader-follower

Leader-follower approach is widely used for formation control due to its simplicity for implementation. In the control strategy, one or more robots are assigned to be the leader(s) of the group, which leaves the remaining members as followers. Figure 1.4 shows a simple one leader and one follower situation. The reference of the desired trajectory is given to the leader(s), and the local control law of each follower can be defined based on the desired relative position of that follower to its leader. Some work based on the basic configuration of a leader and a follower can be found in [START_REF] Luo | A leader-following formation control of multiple mobile robots with obstacle[END_REF], [START_REF] Consolini | On the Control of a Leader-Follower Formation of Nonholonomic Mobile Robots[END_REF], and [START_REF] Wang | A Practical Leader-Follower Tracking Control Scheme for Multiple Nonholonomic Mobile Robots in Unknown Obstacle Environments[END_REF]. In [START_REF] Consolini | On the Control of a Leader-Follower Formation of Nonholonomic Mobile Robots[END_REF], the formation is formed by defining a geometric framework based on the distance and angle between each follower and the leader. Instead of following the leader, the authors of [START_REF] Luo | A leader-following formation control of multiple mobile robots with obstacle[END_REF] introduce a virtual-following robot whose position is derived from the leader; then the problem is converted from formation to tracking control for the follower robots. In [START_REF] Wang | A Practical Leader-Follower Tracking Control Scheme for Multiple Nonholonomic Mobile Robots in Unknown Obstacle Environments[END_REF], the authors use a similar technique as [START_REF] Consolini | On the Control of a Leader-Follower Formation of Nonholonomic Mobile Robots[END_REF]; there is an obstacle avoidance in addition, and a bounded barrier function to ensure that the leader stays inside the follower's field of view. In [START_REF] Wang | Adaptive Vision-Based Leader-Follower Formation Control of Mobile Robots[END_REF], a vision-based leader-follower approach is studied. The controller is an image-based visual servoing; control variables are the 2D coordinate of the leader detected by a pin-hole camera. The idea is to avoid any need for communication from the leader.

Stability analysis of such an approach is relatively straightforward as the controller of each follower is mostly defined based on the distance and bearing to the leader. On the other hand, this control strategy depends solely on the leader. It must not be failed or it can affect the whole formation. In addition, error propagation is common in this system. There is, generally, no communication feedback from each follower to the leader. As a result, the leader may leave its followers behind, for instance, when the leader moves too fast. The lack of ability to perform self-organization is also an issue in this approach.

Virtual structure

For the strategy of the virtual structure, a central controller presumes the entire group of robots as a single entity. The desired motion is defined for the whole formation, which is, then, transformed into the desired motion of each robot for individual tracking. Examples of such work can be found in [START_REF] Thijs | Formation control of unicycle mobile robots: a virtual structure approach[END_REF] and [START_REF] Chen | A nonlinear formation control of wheeled mobile robots with virtual structure approach[END_REF]; nonholonomic robot formation is performed using a virtual center, which is defined from a predefined reference trajectory. As illustrated in Figure 1.5a, the virtual center is used to determine the desired position for each robot at any time instance; then the robots track this position in Cartesian space following a control command from a centralized computer. In [START_REF] Boon | A flexible virtual structure formation keeping control for fixed-wing UAVs[END_REF], this control approach is applied to fixed-wing UAVs. However, the virtual structure introduced is flexible in order to allow the formation to turn smoothly following the desired trajectory. Moreover, the virtual reference point does not have to always be at the center of the formation. As demonstrated in [START_REF] Yoshioka | Formation Control of Nonholonomic Multi-Vehicle Systems based on Virtual Structure[END_REF], virtual vehicle (VV) is introduced for each robot instead. With different desired positional relations between the robot and VV, the formation can be achieved by driving all the VV to converge to a common position as shown in Figure 1.5b. Figure 1.5 -A virtual structure using (a) virtual center approach [BWN09] and (b) virtual vehicle approach [START_REF] Yoshioka | Formation Control of Nonholonomic Multi-Vehicle Systems based on Virtual Structure[END_REF].

Since each robot has its own trajectory to follow, robots' behaviors can be simpler to describe. In addition, inter-robot communication is, generally, not required in such an approach. This is one of its benefits, but also a drawback because inter-robots collisions could occur in the presence of perturbations. Moreover, it is not a distributed approach, thus suffering the previously mentioned disadvantages of a central controller.

Behavior-based

In the behavior-based approach, various desired behaviors corresponding to different situations are assigned to each robot. This strategy was first introduced by [START_REF] Brooks | A robust layered control system for a mobile robot[END_REF], and we can still find this approach in recent work. Figure 1.6 illustrates the concept of this approach. The behaviors can be collision avoidance, obstacle avoidance, formation, go-togoal, etc. These behaviors are then fused together based on their priority and importance. In [START_REF] Marino | A Decentralized Architecture for Multi-Robot Systems Based on the Null-Space-Behavioral Control with Application to Multi-Robot Border Patrolling[END_REF], the authors proposed a behavior-based framework of null-space-behavioral (NSB) control for patrolling application. This NSB approach is also implemented for formation control, which can be found in the work of [START_REF] Ahmad | Multi-robot formation control using distributed null space behavioral approach[END_REF]. The NSB is used to solve a conflict of control velocity when a robot is a part of different groups that have the same or different formation tasks. On the other hand, a simple computation-free behavior-based control is studied in [START_REF] St-Onge | Circle Formation with Computation-Free Robots Shows Emergent Behavioural Structure[END_REF]. In order to form a circle, each robot has four behavior states: 1) scouting: to find a leading robot; 2) chaining: to follow a moving robot; 3) hooking and looping: to close a loop; 4) merging: to integrate any lone robot to an existing circle.

Avoidance behavior

The author of [START_REF] Craig | Flocks, herds and schools: A distributed behavioral model[END_REF] introduced three rules for flocking behavior, which are collision avoidance, velocity matching, and flock centering. The idea was to simulate the natural behavior of birds during the flight in the group, so-called flocking. Developed from these rules, recent flocking literature can be seen in [START_REF] Olfati-Saber | Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory[END_REF] and [START_REF] Saif | Distributed integral control of multiple UAVs: precise flocking and navigation[END_REF]. In order to keep a coherent velocity, each robot's controller has a velocity control term that is based on consensus.

The consensus algorithm is a control strategy whose objective is to get to an agreement on some control features, for instance, the states of robots in the team [START_REF] Hou | A survey on the formation control of multiple quadrotors[END_REF]. [START_REF] Wang | A graph based formation control of nonholonomic wheeled robots using a novel edge-weight function[END_REF] is one of the recent literature that implements consensus for formation control. The authors introduce a weight function to the coefficient of consensus controller for nonholonomic wheeled robots. The formation is achieved once this weight converges to zero. In [START_REF] Fu | Consensus of second-order multiagent systems with both velocity and input constraints[END_REF], the consensus is applied to second-order systems. The work also includes velocity constraints in form of a tangent and local velocity damping function.

The main advantages of this control strategy are the self-organization and scalability of the system. It does not require any central controller sinch each robot has its own set of rules and goals to follow. On the other hand, this approach suffers an issue of being complicated in terms of stability analysis, and a slower convergence rate compared to other methods.

Other approaches

Apart from the presented well-known control strategies above, there are some other effective approaches such as optimization and machine learning.

Optimization is another method of interest for formation control. In [START_REF] Liu | Nash-optimization distributed model predictive control for multi mobile robots formation[END_REF], the authors propose a distributed model predictive control approach in which each mobile robot is considered as a subsystem. The neighboring subsystems are, then, coupled in the cost function where nash-optimization is used to solve for an optimal solution. The cost function includes path-following and formation. On the other hand, a centralized optimization-based control is proposed by [START_REF] Héctor | Multi-vehicle coordination based on hierarchical quadratic programming[END_REF]. The authors define different tasks as equality and inequality constraints. The tasks consist of formation, obstacle avoidance, and trajectory tracking; they all have different levels of priority. The hierarchical quadratic programming framework is used in order to solve for an optimal solution that respects imposed constraints.

Last but not least, the use of machine learning techniques can also be found in the field of MRS. [START_REF] Ling | A Simple Scheme for Formation Control Based on Weighted Behavior Learning[END_REF] and [START_REF] Wang | Pattern-RL: Multi-robot Cooperative Pattern Formation via Deep Reinforcement Learning[END_REF] are some of the recent works in literature; the authors applied the reinforcement learning approach for formation control. In [START_REF] Ling | A Simple Scheme for Formation Control Based on Weighted Behavior Learning[END_REF], a set of formation behaviors is pre-defined. Each action contributes with a certain weight to the overall control; the reinforcement learning constantly adjusts these weight coefficients for optimal formation behavior. On the other hand, the authors of [START_REF] Wang | Pattern-RL: Multi-robot Cooperative Pattern Formation via Deep Reinforcement Learning[END_REF] propose a deep 22 neural networks framework that tries to generate a general formation pattern; it is based on trial-and-error feedback from each formation round in order to improve the formation strategy. As logistics is one of the emerging applications of the MRS, cooperative transportation task is a mission that has demands in real-world usage. To collectively move an object, a team of mobile robots can utilize one of the numerous load handling strategies; some of which include [START_REF] Tuci | Cooperative Object Transport in Multi-Robot Systems: A Review of the State-of-the-Art[END_REF]: pushing-only, caging, and grasping. Figure 1.7 shows the different types of load handling scenarios. For the pushing-only and caging strategy, there is no physical joint between the robots and the object. These two strategies are one of the easiest to implement. However, they can be inefficient due to frictional forces. The terrain on which the robots operate has to be smooth. The same requirement also applies to the object's bottom surface. As the name suggested, all that is needed to be done to move an object is to straightforwardly push or, sometimes, pull that object (Figure 1.7a). This technique can be found in the work of [START_REF] Eoh | Multi-robot cooperative formation for overweight object transportation[END_REF], [START_REF] Chen | Occlusion-Based Cooperative Transport with a Swarm of Miniature Mobile Robots[END_REF] and [START_REF] Muhanad | Cooperative object transport with a swarm of e-puck robots: robustness and scalability of evolved collective strategies[END_REF]. When the object is surrounded by both pushing and pulling robots, as shown in Figure 1.7b, it is called caging. This approach is implemented in [START_REF] Héctor | Multi-vehicle coordination based on hierarchical quadratic programming[END_REF], [START_REF] Dai | Symmetric caging formation for convex polygonal object transportation by multiple mobile robots based on fuzzy sliding mode control[END_REF], and [START_REF] Wan | Multirobot Object Transport via Robust Caging[END_REF]. On the other hand, the grasping approach can be found in the work of [START_REF] Yang | A decentralized control system for cooperative transportation by multiple non-holonomic mobile robots[END_REF], [START_REF] Wang | Kinematic multi-robot manipulation with no communication using force feedback[END_REF], and [START_REF] Alonso-Mora | Multi-robot formation control and object transport in dynamic environments via constrained optimization[END_REF]. In this case, the load is carried by manipulators that are on top of the mobile platforms; the manipulators may be either passive or active joints. Even though the rigidity of the formation's shape is not important, it requires additional and complex mechanisms added to the robots.

Load handling strategy

Task allocation

Multi-robot task allocation (MRTA) problem is solved differently depending on the type of tasks, robots, and assignation nature. Generally, there are three classifications of MRTA [START_REF] Gerkey | A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems[END_REF]. Table 1.1 shows a summary of this taxonomy. Single-robot (SR) task means only one robot is required to complete this task, while the Multi-robot (MR) may require multiple robots. Single-task (ST) robot represents a kind of robot that can execute only one task at a time, while the Multi-task (MT) counterpart can perform multiple tasks simultaneously. Instantaneous assignment (IA) assumes that tasks are independent of each other. With the available information on robots, tasks, and the environment, only instantaneous allocation is possible; there is no future assignment planned. Timeextended assignment (TA) allows a schedule allocation into the future. It requires more information, for instance, the dependencies between tasks. Some of the practical problems that can be solved using MRTA techniques are the Multiple Traveling Salesman Problem (mTSP) and the Vehicle Routing Problem (VRP) [START_REF] Ayorkor Korsah | A comprehensive taxonomy for multi-robot task allocation[END_REF]. mTSP is a modified version of the classic Traveling Salesman problem (TSP). In TSP, the salesman has a list of towns to visit; the aim is to find the optimal path that would require the least traveling distance or time to complete the tour. All the towns have to be visited only once. Increased to m salesmen in mTSP, the goal remains the same; starting from the same point, each salesman has to visit at least one town before returning back to the start point. Applying to robotics, the town represents a destination point in the environment while each salesman is represented by a robot. The travel cost to be mini- -MinSum: to minimize the total cost of all robots.

-MinMax: to minimize the worst cost of a robot.

-MinAve: to minimize the average cost of all targets.

Numerous studies have been proposed in the literature to address the MRTA problems. We will present some of the recent work that mainly falls into two of the most widely used MRTA approaches [START_REF] Khamis | Multi-robot Task Allocation: A Review of the State-of-the-Art[END_REF]: market-based or auction-based and optimization-based.

Auction-based

Inspired by economical studies, market-based relies on a mechanism called auction. Figure 1.8 demonstrates a process of the auction for market-based task allocation. A central server or one of the robots in the team can be an auctioneer in order to broadcast tasks to be done. Then, each individual robot submits its bids based on various factors such as distance to travel, time to execute, battery level, robot capability, etc. After all bids are received, the auctioneer can decide and pick the appropriate winner for the task.

The auction process can be divided into two categories [START_REF] Seenu | Review on state-of-the-art dynamic task allocation strategies for multiple-robot systems[END_REF]: single-item auction and combinatorial auction. These two are developed further to various variants, but the core definition remains. Single-item auctioning method allocates only a task at a time. It is a simple and efficiently quick approach. However, optimality can not be guaranteed because some tasks may be close to each other and should be allocated to the same robot. This issue can be solved using the combinatorial auction. Since a set of positive synergy tasks are put to auction at once, the solution can be more optimal for the combinatorial than the single-item auction approach. However, the computational complexity of the system increases in this case as the auctioneer has to understand the nature of tasks and bundle them together.

A recent use of the auction-based approach can be found in [START_REF] Bahgat | A Multi-Level Architecture for Solving the Multi-Robot Task Allocation Problem Using a Market-Based Approach[END_REF]. The authors rely solely on the distance between the robot's current position and the assigning task to compute the bid. In [START_REF] Basile | An auction-based approach to control automated warehouses using smart vehicles[END_REF], heuristics decisions are added to the auction process. Those heuristics include the closest robot to the starting of the mission; and the priority zone association of the robot. In [START_REF] Luo | Distributed Algorithms for Multirobot Task Assignment With Task Deadline Constraints[END_REF], the auction's objective is to maximize total payoffs, meaning maximum delivery of parts for assembly. Since this work is intended for a manufacturing environment, a battery constraint is also imposed in form of the total duration of tasks; this can not exceed the robot's status. In [START_REF] Sullivan | Sequential single-item auction improvements for heterogeneous multi-robot routing[END_REF], a singleitem auctioning method is proposed for the heterogeneous system. The authors focus on minimizing the energy usage as well as the total task completion time. In addition, each robot can obtain partial knowledge of tasks and robots in the environment; they can then decide whether to stay and complete tasks they know or roam around for other tasks. In [START_REF] Baroudi | Dynamic Multi-Objective Auction-Based (DYMO-Auction) Task Allocation[END_REF], more cost factors are added to the objective function. In addition to minimizing the total traveling distance, the authors aim to balance the load between robots as well as to maximize a quality satisfaction. Each task has a level of quality requirement, and so do the robots. To be considered satisfied, the difference in quality metric between the assigning task and the robot has to be minimized.

Optimization-based

Optimization has been used in many various fields. It aims to find an optimal or close to optimal solution within a set of constraints by minimizing a cost or maximizing a profit of a system [START_REF] Khamis | Multi-robot Task Allocation: A Review of the State-of-the-Art[END_REF]. There exists a huge collection of optimization-based approaches for MRTA depending on the nature of the problem.

When the allocation problem is small, with a few tasks and robots, it is possible to find the optimal solution using an exact search algorithm. Mixed-Integer Linear Programming is one of the exact algorithms, for which the allocation problem is formulated as integers and linear equations. In [START_REF] Sundar | An exact algorithm for a heterogeneous, multiple depot, multiple traveling salesman problem[END_REF], this approach is used to solve the heterogeneous mTSP. The authors focus on having the salesman (robot) that starts from different points. Some of the targets are set to require specific robots to visit; this is set to reflect the heterogeneous nature of the robots. The algorithm aims to minimize the sum of all traveling costs, which are computed in a function of the euclidean distance between two points.

Another well-known exact search is the Hungarian algorithm. It is exploited in [START_REF] Xue | An Exact Algorithm for Task Allocation of Multiple Unmanned Surface Vehicles with Minimum Task Time[END_REF] to solve task allocation of unmanned surface vehicles, which have to move from their starting position to different target points. The goal is to minimize the max task time and reduce the total task time. The task time is a combination of the travel time and the turning time at initial and target points.

On the other hand, if the number of tasks and robots becomes too large, the exact solution approach might not be able to sustainably find the optimal solution in a finite amount of time. In this case, approximate search algorithms can be used. They may not find the general optimal solution, but an approximation that is close to the global one. Simulated Annealing (SA), a trajectory-based metaheuristic, is an approximation approach that consists of a single agent that traverses through the search space. In order to avoid being stuck in local minima, the SA accepts poor solutions within a certain probability during the search for the global optimum. An example of the use of SA can be found in [START_REF] Mosteo | Simulated annealing for multirobot hierarchical task allocation with flexible constraints and objective functions[END_REF]. The authors propose a solution to the mTSP using the MinMax cost function, which is based on the traveling cost between target points.

Another type of metaheuristic is population-based optimization, examples of which are Genetic Algorithm (GA), Particle Swarm Optimization (PSO), and Ant Colony Optimization (ACO). Inspired by genetic selection, the GA relies on crossover and mutation operations to find potential solutions, so-called chromosomes. A fitness function is introduced, against which the chromosomes are evaluated. The work in [START_REF] Fai | A Novel Warehouse Multi-Robot Automation System with Semi-Complete and Computationally Efficient Path Planning and Adaptive Genetic Task Allocation Algorithms[END_REF] is one of the MRTA that implements this GA. The authors propose a fitness function that corresponds to the traveling distance of each task for the robot. Similar to GA, PSO relies on evolution over generations to search for optimal solutions. However, it does not have evolutionary operators such as crossover or mutation. Instead, PSO initializes a population, called particles, over a search space. Each particle updates its behavior based on its own trajec-tory as well as the two best-found solutions: personal best and global best. One of the PSO work on MRTA can be found in [START_REF] Wei | Particle Swarm Optimization for Cooperative Multi-Robot Task Allocation: A Multi-Objective Approach[END_REF]. The authors propose a multi-objective PSO, whose cost function tries to minimize the total cost of all robots (MinSum) and the worst cost of a robot (MinMax) at the same time. They are both in the function of travel distance. Last but not least, the ACO introduces the concept of virtual ants. These ants start off to search for food (potential solution) leaving a trail behind, known as pheromone deposition. Other ants update their trajectories taking into account this trail. Over time, this trail can be evaporated leaving the path less attractive. In contrast, the more pheromone deposition there is, the more ants are likely to follow that trail; this induces positive feedback leading to eventually having all ants search on the same path.

Conclusion

In this chapter we have discussed the three different architectures of control used in the multi-robot system: centralized, distributed, and hierarchical. Even though they inherit different advantages and disadvantages, one does not have a clear edge over another. It depends on the actual MRS application considering the environment, number of robots, number of missions, etc.

The formation is a crucial part of any cooperative transportation task. Apart from the leader-follower, virtual structure, and behavior-based, which are the most well-known approaches, there exists also studies that are based on optimization and machine learning. However, not all of them are applied to the transportation mission. In addition to conventional formation control, which includes forming a shape and navigation, extra studies have to be conducted for such tasks; for instance, the load handling or carrying techniques. We have detailed three common strategies: pushing-only, caging, and grasping; they can have an impact on how the formation control method is chosen.

Since our goal is to transport the load directly on top of the robots, a fixed interdistance formation control is required. In this thesis, we base the formation on two different control strategies: the consensus algorithm and the hierarchical quadratic programming approach. We consider using the consensus control because it allows the formation problem to be resolved in a distributed manner, thus increasing the scalability of the system. On the other hand, the hierarchical quadratic programming is a more relevant solution considering our use cases; it allows the formation control to clearly specify priorities for different behaviors. For instance, we can prioritize having a fixed inter-distance formation over team navigation.

Last but not least, we have presented an introduction to the multi-robot task allocation. The type of MRTA is divided into three poles of taxonomy. Since MRTA is a challenge of optimization, various objective cost functions can be formulated. Then a potential optimal solution can be found using widely-known strategies such as auction-based and optimization-based. There is a huge list of MRTA solving strategies that fall into these two categories. These strategies are tailored to specific requirements and assumptions of various applications. However, few of the proposed approaches are validated in an actual real-world environment, and many of them are validated only in simulations.

In this work, the Contract Net Protocol and the Tabu Search are chosen. The CNP represents the auction-based approach, which can solve the allocation problem in a distributed way. However, its solution can be less optimal compared to its optimization-based counterpart. Hence, Tabu Search is our next choice representing the optimization-based allocation because it allows the solver to step a bit out of a minimum in order to find better minima values. These two approaches are then implemented and compared considering our use cases.

Introduction

The aim of this chapter is to present two proposed formation strategies that are based on different control architectures. The consensus-based formation is a distributed controller, whereas the optimization-based formation is a centralized approach. The consensus provides a solution to the formation problem by allowing each robot to react and compute its control velocity locally based on its neighbors. On the other hand, the optimization approach, which is based on the HQP, allows us to set behavior priorities. This results in having a more stable and fixed inter-distance formation.

We will discuss some fundamental mathematical theories that build up to the proposed consensus algorithm. These include graph theory and the consensus theory itself. The later half of this chapter is dedicated to the optimization-based controller. In that section, we introduce the hierarchical quadratic programming approach as well as definitions of sub-tasks for the optimization problem.

The two proposed control laws are validated in both simulations and real-world experiments. The results are presented in their respective controller sections. Our deployment objective for all robots in the team is to cooperatively transport a load. It requires constant inter-distances between them throughout navigation. This is the main attribute we are looking for.

Consensus-based formation

The consensus algorithm is a process of reaching an agreement on some values of a system. It is applied to a wide range of applications in the field of distributed computing and multi-agent systems. For robotics, consensus can be used as a control approach whose objective is to get to an agreement on some control features, for instance, the states of robots in the network [START_REF] Hou | A survey on the formation control of multiple quadrotors[END_REF]. Equation (2.1) is an example of the consensus problem; the goal is to maintain a relative position to the neighbors by minimizing a cost function:

v i = j∈N i ∥p j -p i -p ij ∥ 2 (2.1)
where v i is the control input of robot i, p ij is a desired relative position of robot i and its neighbor j, and p i and p j is the position of robot i and j, respectively. If p ij = 0 0 T , all robots in the group will converge to a single point. Indeed, this relative position can be defined such that a desired shape of formation is obtained. From this simple technique, researchers have been pushing the boundary by introducing weight coefficients and/or designing more complex consensus terms; [START_REF] Falconi | A graph-based collision-free distributed formation control strategy[END_REF] and [START_REF] Wu | Leader-following Consensus and Trajectory Tracking for Nonholonomic Mobile Robots[END_REF] are some examples of that.

Our consensus-based formation interest is to adapt the distributed flocking algorithm, which is introduced for the double integrator system in [START_REF] Saif | Distributed integral control of multiple UAVs: precise flocking and navigation[END_REF], for a single integrator formation system. We also introduce an improved obstacle avoidance, which is inspired by the work of [START_REF] Olfati-Saber | Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory[END_REF]. It considers each obstacle as a virtual robot, then a potential function is used to repel robots from the virtual robots (obstacles). The improvement to the original obstacle avoidance approach is that each robot takes into account its neighbors' obstacle(s) in addition to its own obstacle(s), which is more suitable for preserving the formation compared to the original approach, where the obstacle avoidance is performed independently for each robot. This controller is then applied to a group of wheeled mobile robots, thus requiring a state linearization to overcome the nonholonomic constraint.

Wheeled mobile robots modeling

Let's consider a multi-robot system with n robots. Each robot is a differential drive robot, where (x ri , y ri ) T ∈ R 2 is the center of the i-th robot; θ i , v i and ω i are its heading angle, linear velocity and angular velocity, respectively as shown in Figure 2.1. The kinematic model of this i-th robot can be expressed as follows:

     ẋri ẏri θi      =      cos θ i 0 sin θ i 0 0 1        v i ω i   (2.2) Figure 2.1 -A nonholonomic wheeled mobile robot.
The robot is subjected to nonholonomic constraints. Therefore, a static feedback method is used in order to apply any control law to the robots. An offset point, p i = x i y i T is defined from the robot's center as shown in Figure 2.1; as a result, the problem is shifted from controlling center of the robot to this offset point, which can be a point of interest later. Referenced to this point, the kinematic model is holonomic for l ̸ = 0, and it can be written as follows [START_REF] Ren | Distributed Consensus in Multi-vehicle Cooperative Control[END_REF].

p i =   x i y i   =   x ri + l cos θ i y ri + l sin θ i   (2.3)
Differentiating Equation (2.3) with respect to time, we can get the velocity of this offset in relation robot's linear and angular velocity as follows:

ṗi =   ẋi ẏi   = B(θ i )u i (2.4)
where

B(θ i ) =   cos θ i -l sin θ i sin θ i l cos θ i  
, l ̸ = 0 is the offset length, and

u i = u i ω i T
is the velocity vector of i th robot. Expanding Equation (2.4) to n number of robots, the relation between velocities of each offset point and the robot is expressed as follows:

v = J x u (2.5)
where:

v =         ṗ1 ṗ2 . . . ṗn         , J x =      B(θ 1 ) 0 0 . . . B(θ n )      , u =         u 1 u 2 . . . u n        
The use of the offset point is extended to a mounting point between the load and group formation. Since this point is the control point of interest, it is practical to attach a load support to each robot at this point through a passive revolute joint. Figure 2.2 shows this idea of load placement. By mounting as such, the load's position and heading can be directly controlled since its frame is coincident with the formation frame. Once the payload is mounted, the whole system can be seen as a single, highly overactuated mobile robot. Therefore, it is of prime importance to generate consistent control inputs for all robots such that the formation is kept. Ignoring these would lead to either set high forces on the passive joint or induce slipping or skidding of some robots. In both cases, the general motion of the formation would not be controlled correctly.

Graph theory

A graph is a pair of vertex set V and edge set E [Die05], G = (V, E) where V = {1, 2 . . . , n} and E ⊆ {(i, j) : i, j ∈ V, j ̸ = i}. A vertex represents a node, an agent, or a robot, whereas an edge is formed by two connected vertices. Thus, each element of E is a pair of V.

A(G) =            0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0            (2.6) 1 2 4 5 3 Figure 2.3 -Example of a graph.
The adjacency matrix, A(G), is a symmetric matrix with the dimension of n×n, where n is the number of vertices, that represents the connectivity between neighbors:

[A(G)] ij =    1 if (i, j) ∈ E, 0 otherwise. (2.7)
In a multi-robot system, graph theory is often used to describe its topology. A topology is a description of physical relations between each robot in the group. It can be expressed by either an undirected or directed graph depending on the relations between neighbors. Vertices are symmetrically linked for the undirected graph, whereas the links are asymmetric for the directed graph. The edges indicate a two-way relationship in the undirected graph. For the directed graph, it's a one-way relationship; a robot can obtain information about a neighbor by explicitly communicating with that neighboring robot or by using its onboard sensor(s) to derive the information without actual communication. An example of the undirected and directed graph is illustrated in Figure 2.4a and Figure 2.4b, respectively. Notice that each link (edge) between vertices is represented by an oriented arrow for the directed graph in order to indicate a constraint motion of an agent with respect to another. For instance, in Figure 2.4b the arrow's direction flows from vertex (robot) 1 to vertex (robot) 2 indicating that the motion of robot 1 is constrained to robot 2. On the other hand, the robot 2 is unaware of 1, and its motion is unconstrained. A graph is considered to be connected if there is a path that is linked between any pair of vertices. Otherwise, the graph is defined as disconnected. For the case of undirected graph, the connectivity can only be either connected (Figure 2.5a) or disconnected (Figure 2.5d). The directed graph, however, can be further classified into weakly (Figure 2.5b) and strongly (Figure 2.5c) connected graphs depending on if there exists a directed path between each vertex pair or not.

Another crucial aspect of the graph theory in formation is rigidity. A rigid graph is mainly applicable to an undirected graph, where the formation's shape is maintained throughout the maneuver [START_REF] Ren | Automatic generation of optimally rigid formations using decentralized methods[END_REF]. For instance, if the formation is controlled by interdistances between robots, these distances will have to remain constant at their corresponding desired values. In a rigid graph, the number of edges can grow significantly with respect to the number of vertices or robots. In fact, for a fully-connected graph, the total number of edges is:

n(n -1) 2 (2.8)
where n is the number of robots in the formation. Therefore, a concept of minimally rigid graph is commonly used instead. Minimally rigid graph corresponds to a graph where no edge can be further removed without losing its rigidity, hence the word minimal [START_REF] Fidan | Rigid graph control architectures for autonomous formations[END_REF].

There exists also a more constrained version of rigidity, named infinitesimally rigid. It is when the vertices are allowed to move infinitesimally while still preserving the rigidity.

To achieve this, the motion has to satisfy Equation (2.9) [START_REF] Zelazo | Decentralized rigidity maintenance control with range measurements for multi-robot systems[END_REF].

(v j -v i ) T (p j -p i ) = 0, ∀(i, j) ∈ E (2.9)
For a two-dimensional system, the minimal rigidity can be obtained when the total number of edges in the graph is:

2n -3 (2.10)
where each subgraph of n ′ vertices, where n ′ ≤ n, has no more than 2n ′ -3 edges. The Our system is represented by an undirected graph. Each robot is denoted by a node of the vertices, and the set of neighbors of node i, N i , is defined by:

N i = {j ∈ V : (i, j) ∈ E} = {j ∈ V : ∥p j -p i ∥ < c} (2.11)
where c > 0 is the interaction range between robots, and ∥.∥ denotes the Euclidean norm.

p i and p j are the Cartesian coordinates of robots i and j, respectively.

The desired formation of the system can be expressed as:

∥p j -p i ∥ = d ∀j ∈ N i (p) (2.12)
where d is the desired inter-distance between robot i and j.

Preliminaries

This section discusses the flocking control for the double-integrator system. We start off by introducing the preliminaries and the control algorithm proposed by [START_REF] Olfati-Saber | Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory[END_REF], followed by the modified PID-like controller of [START_REF] Saif | Distributed integral control of multiple UAVs: precise flocking and navigation[END_REF].

Similar to the adjacency matrix of the topological connection in the graph theory, a spatial adjacency matrix A(p) = [a ij (p)]; it is defined in order to reflect on the positionbased connection between robots. The elements a ij of this matrix are given as follows:

a ij (p) =    0 if i = j ρ h (∥p j -p i ∥ σ /∥c∥ σ ) if i ̸ = j (2.13)
where p h is called a bump function and ∥.∥ σ is called σ-norm. The bump function is a smooth scalar function ranging between zero and one: R + → [0, 1]. With h ∈ (0, 1), this function is defined as follows:

ρ h (z) =                1, z ∈ [0, h) 1 2 1 + cos π (z -h) (1 -h) , z ∈ [h, 1] 0, otherwise (2.14)
The σ-norm is a map of a vector to positive value: R n → R + , n ∈ Z + . This norm is defined as follows:

∥z∥ σ = 1 ϵ 1 + ϵ∥z∥ 2 -1 (2.15)
with ϵ > 0, and its gradient can be expressed as:

σ ϵ (z) = ∇∥z∥ σ = z 1 + ϵ∥z∥ 2 = z 1 + ϵ∥z∥ σ (2.16)
Thus unlike ∥z∥, which is not differentiable at z = 0, ∥z∥ σ is differentiable everywhere.

A smooth pairwise attractive/repulsive potential function is defined as:

Ψ α (z) = z ∥d∥σ Φ α (δ)dδ (2.17)
This function is an integration of an action function Φ α that has a minimum at z = ∥d∥ σ and a finite cut-off when z ≥ ∥c∥ σ . An example of this potential function Ψ α (z) is depicted in Figure 2.7. The action function is defined as follows: Therefore, a smooth collective potential function is introduced as:

Φ α (z) = ρ h (z/∥c∥ σ )Φ(z -∥d∥ σ ) Φ(z) = 1 2 [(a + b)σ 1 (z + e) + (a -b)]
V (p) = 1 2 i j̸ =i Ψ α (∥p j -p i ∥ α ) (2.19)
With the above attractive/repulsive characteristic, a control law introduced by [START_REF] Olfati-Saber | Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory[END_REF], which applied on the second-order dynamic of each robot, is defined as follows:

vi = j∈N i [Φ α (∥p j -p i ∥ σ )n ij + a ij (p)(v j -v i )] + f i (v i , p i , v r , p r ) (2.20) where f i (v i , p i , v r , p r ) = -c 1 (p i -p r ) -c 2 (v i -v r ), c 1 , c 2 > 0 and n ij = σ ϵ (p j -p i ).
This control law is made up of three terms: 1) a gradient-based term that regulates the inter-distance between robots, 2) a velocity consensus for flocking, and 3) a navigational feedback control, where p r and p r are the desired position and velocity to be tracked, respectively.

To further improve the system's behavior, a PID-like tunable gains version of this control algorithm is introduced by [START_REF] Saif | Distributed integral control of multiple UAVs: precise flocking and navigation[END_REF]. It is given as follows:

vi = j∈N i [K p Φ α (∥p j -p i ∥ σ )n ij + K ′ p a ij (p)(p j -p i ) + K d a ij (p)(v j -v i ) + K i j∈N i Φ α (∥p j -p i ∥ σ )n ij dt] + f i (v i , p i , v r , p r ) (2.21)
where K p , K ′ p , K d , K i > 0 are the tuning gains of the controller. The authors' perspective of introducing K p , K ′ p , K d is to compensate for the uncertainties when applying to a nonlinear system, whereas the integral term with K i is added in order to overcome the steady-state error problem.

Since this flocking algorithm does not include any obstacle avoidance capability in the control law, we incorporate the obstacle avoidance algorithm from [START_REF] Olfati-Saber | Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory[END_REF].

N α i = j ∈ V α : ∥p j -p i ∥ < c N β i = k ∈ V β : ∥ p i,k -p i ∥ < c ′ (2.22)
Incorporating the agent-to-obstacle constraint into the control law, the overall constraints of the system, thus, consist of:

   ∥p j -p i ∥ = d ∀j ∈ N α i ∥ p i,k -p i ∥ = d ′ ∀k ∈ N β i (2.23)
where c ′ and d ′ are the interaction range and inter-distance between α-agent i and βagent k, respectively. p i,k is an estimated position, and v i,k is an estimated velocity of the closest point from robot i to obstacle k. These estimations of position and velocity can be done using either external or onboard sensors such as lidar and camera. Since obstacles are treated as virtual robots, the avoidance control law is similar to the flocking control law based on a potential function, which is defined as follows:

vβ i = c β 1 k∈N β i Φ β (∥ p i,k -p i ∥ σ ) n i,k + c β 2 k∈N β i b i,k (p)( v i,k -v i ) (2.24)
where c β 1 , c β 2 > 0 are gains, n i,k = σ ϵ ( p i,kp i ), and b i,k (p), which is the heterogeneous adjacency between an α-agent i and its neighboring obstacle k at p i,k , is defined as:

b i,k (p) = ρ h (∥ p i,k -p i ∥ σ /∥d ′ ∥ σ ) (2.25)
with the function defining the repulsive action expressed as follows:

Φ β (z) = ρ h (z/∥d ′ ∥ σ )(σ 1 (z -∥d ′ ∥ σ ) -1) (2.26)

Formation control algorithm

If we combine the flocking control, Equation (2.21), with the obstacle avoidance, Equation (2.24), we get the overall control law as follows:

vi = j∈N α i [K p Φ α (∥p j -p i ∥ σ )n ij + K ′ p a ij (p)(p j -p i ) + K d a ij (p)(v j -v i )] + K i j∈N α i Φ α (∥p j -p i ∥ σ )n ij dt + f i (v i , p i , v r , p r ) + c β 1 k∈N β i Φ β (∥ p i,k -p i ∥ σ ) n i,k + c β 2 k∈N β i b i,k (p)( v i,k -v i ) (2.27)
Since our goal is to apply a formation control to a single-integrator system, we are interested only in the gradient-based term for regulating the inter-distance and not so much in the velocity matching term. The overall control law, Equation (2.27), is thus modified to be as follows:

v i = j∈N α i K p Φ α (∥p j -p i ∥ σ )n ij + K i j∈N α i Φ α (∥p j -p i ∥ σ )n ij dt -sat(c γ 1 (p i -p r )) + v β i (2.28)
where

v β i = c β 1 k∈N β i Φ β (∥ p i,k -p i ∥ σ ) n i,k and sat(.
) is a saturation function defined as:

sat(x) =           
x min , x < x min

x max , x > x max

x, otherwise.

(2.29)

The value of x min and x max are chosen explicitly in order to ensure that the navigation term will not dominate over other control terms when the goal point is too far away.

Moreover, in order to ensure the formation shape while navigating around the obstacle, we propose a new consensus obstacle avoidance scheme. In this approach, each robot will take into account its neighbors' obstacles as well. By doing so, it can anticipate incoming obstacles even if they are not yet in its own detection range. Hence, the robots in the group will synchronously avoid the obstacle. The obstacle avoidance term of Equation (2.28), v β i now takes into account all potential obstacles for all robots, which is expressed as follows:

v β i = c β 1 k∈N β i Φ β (∥ p i,k -p i ∥ σ ) n i,k + j∈N α i k∈N β j Φ β (∥ p j,k -p j ∥ σ ) n j,k (2.30)
Combining Equation (2.28) and (2.30), the overall proposed control law for a single integrator system is as follows:

v i = j∈N α i K p Φ α (∥p j -p i ∥ σ )n ij + K i j∈N α i Φ α (∥p j -p i ∥ σ )n ij dt + c β 1 k∈N β i Φ β (∥ p i,k -p i ∥ σ ) n i,k + j∈N α i k∈N β j Φ β (∥ p j,k -p j ∥ σ ) n j,k -sat(c γ 1 (p i -p r ))
(2.31)

Simulations and experimental results

We validate the proposed control law in simulation as well as in the real experiment. In order to apply the control algorithm to a mobile robot, we use the static state feedback as explained in Section 2.2.1, specifically using Equation (2.4). In both simulation and experiment, ROS 1 is used as the middleware. In the case of simulation, we simulate the control laws from Equation (2.28) and (2.30). For the experiment, we utilize four Huskys2 . The control law from Equation (2.30) is run in each Husky independently, only the obstacle and its own positions, which are estimated using onboard sensors, in a known map are shared within a local network. The aim is to obtain a formation control that can keep its shape throughout the navigation, thus the inter-distances between robots should be constant.

The value of parameters used in the simulation and experiment are shown in Table 2.1. The interaction range, c, for control law from Equation (2.28) is chosen according to the remark of authors in [START_REF] Olfati-Saber | Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory[END_REF], while for Equation (2.30), it is defined such that each robot becomes a neighbor of all others in the team; in another word, a fully-connected graph. The minimum and maximum values of the saturation function are -0.3 and 0.3, respectively. A simulation of Equation (2.28) is shown in Figure 2.11. It can be seen in Figure 2.11b that robot 0 (red) breaks formation in order to avoid the obstacle. More precisely, this robot avoids the obstacle from the left side while the other robots avoid it from the right side. Indeed, in Figure 2.11a it was clear that the inter-distances took a huge amount of time to stabilize. The formation shape is totally distorted and restored only after the obstacle is passed through. This is, indeed, a common behavior as shown in [START_REF] Olfati-Saber | Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory[END_REF]. This behavior is not desirable considering we want the formation to be kept always, which is important for the application of load transportation.

Simulation

The result of the proposed control law, Equation (2.30), is shown in Figure 2.12. In Figure 2.12a, d ij represents the inter-distance between robots i and j, where i, j ∈ {0, 1, 2, 3} and i ̸ = j. The inter-distances between each robot quickly converge and stay stable over time. Moreover, the formation of the team is preserved even during obstacle avoidance motion. As shown in Figure 2.12b, the shape is fixed throughout the navigation. This behavior is desirable, and we will see the actual implementation of this control algorithm in the next section.

Experiment

For the actual experiment, four robots are used; they are all independent of each other in terms of controller and ROS master node. The team is fully connected, meaning each Notice that the resultant inter-distance between robots on each side of the square is not equal to the desired inter-distance; this is because this desired value was set to all neighbors in the team, including those that are diagonal to each other. Hence the consensus tries to reach a compromise between all robots. Therefore, in the following experiment, we introduce a different desired inter-distance value for the diagonal neighbor robots, more specifically it will be a square root of two of that of the side neighbors; it is corresponding to the shape of a perfect square. The formation result can be seen in Figure 2.16. The inter-distances of side and diagonal neighbors converge quickly to the desired ones, and they remain around the desired values even when maneuvering around the obstacle. This is backed by the robots' trajectories; the square shape is obtained at around t = 10s, indicated as a blue square in Figure 2.16b.

Conclusion

In this section, we have revised existing flocking algorithms such that they can be applied in nonholonomic robots systems. A combined consensus control for formation and obstacle avoidance is proposed, and it is able to do formation and navigation of the fleet's barycenter to a goal point without any collision with the obstacle. The validation of this control law shows its effectiveness in simulations as well as real experiments using actual industrial robots, Huskys. A video of these experiments can be found here 4 . However, the nature of this approach is a compromised control, which means the priority of each task (formation, navigation, obstacle avoidance, etc.) is not strictly enforced. This could potentially be a problem as the formation will not be kept if some parts of the controller dominate another. A solution to this issue is to introduce a strict hierarchy of tasks for the controller, which will be discussed in an optimization-based approach in the next section.

Optimization-based approach

In order to ensure the strict priority order of tasks, an optimization approach can be used, namely hierarchical quadratic programming (HQP). This section discusses the proposed formation controller, which is based on the HQP. Tasks are defined as either equality or inequality constraints with different levels of priority. These tasks include rigid shape formation control, group navigation, individual and team obstacle avoidance, and velocity limits.

Task-based control

Let us define s ∈ R ns as a set of control features. The goal of the controller is to drive the value of these features to the desired ones, s * . In order to do this, a relation between the features' rate of changes, ṡ, and the robots' velocities, v, has to be determined, and it can be expressed as follows [START_REF] Kermorgant | Dealing with constraints in sensor-based robot control[END_REF]:

ṡ = J s v (2.32)
where J is the Jacobian matrix that is, generally, as a function of the features.

As the goal is to regulate the feature error e = ss * (2.33) to zero, a proportional controller, ė = -λe, can be used to ensure an exponential decay of e with λ is a positive gain. There the control input of the system, considering Equation (2.32), can be written as follows:

J s v = ṡ * -λe (2.34)
where ṡ * is assumed to be null as the set of desired values is fixed. This Equation (2.34) has a unique solution only if J s is a square and non-singular matrix, which is often not the case. Therefore, an approximation solution can be found using the following control laws:

v = -λ J + s (s -s * ) (2.35)
where J + s is the pseudo-inverse of the estimation of the Jacobian.

Hierarchical quadratic programming

The hierarchical quadratic programming (HQP) framework [START_REF] Oussama Kanoun | Kinematic control of redundant manipulators: Generalizing the task-priority framework to inequality task[END_REF] is used to solve for control input ensuring strict priority order. HQP is a sequence of QP that tries to minimize a cost function subjected to equality and inequality constraints as well as solutions of higher priority tasks. At k-level of priority, HQP can be formulated as follows:

u k = arg min x ∥A k x -b k ∥ 2 s.t. A i x = A i u i , ∀i < k C k x ≤ d k C i x ≤ d i , ∀i < k (2.36)
where u k is the optimal solution that minimizes the cost function of equality task k, x is the optimization variable, matrix A k and vector b k describe the cost function, whereas A i and b i represent the cost function of previous hierarchies. C k , d k and C i , d i are the inequality constraints of the current and previous levels, respectively. The equality constraint ensures that the objective task is minimized at best without disturbing previous higher priority tasks. Note that the equality constraints inherited from previous hierarchy levels are actually

∥A i x -b i ∥ 2 = ∥A i u i -b i ∥ 2 .
Writing them as in Equation (2.36) makes the constraints stronger but keeps them linear. The final solution can be chosen as the minimal-norm one by solving the last hierarchy level with the pseudo-inverse.

Task definitions

The tasks will be generally defined for n robots, and we chose specifically n = 4 for implementation examples. All the defined tasks are applied to the offsets' positions. We recall Equation (2.5) for the case of four robots, the relation between the velocity of the offset point and the control input of each robot in the case of four robots is expressed as follows:

v = J x u
(2.37)

where:

v =      ṗ1 . . . ṗ4      , J x =      B(θ 1 ) 0 0 . . . B(θ 4 )      , u =            v 1 ω 1 . . . v 4 ω 4           
and ṗi , i = 1, 2, 3, 4, is defined as in Equation (2.4).

Geometric formation

The task of forming into a particular geometric shape is one of our specific goals mentioned in the previous Section 2.2. The inter-distances between each robot in the group are used as the control features. With user-defined values of the inter-distances, specific geometric shape formation can be done. If we consider two points as shown in Figure 2.17a with p i , p j ∈ R 2 , i, j = 1, 2..., the distance d ij is as follows:

d ij = ∥p j -p i ∥ (2.38)
By differentiating Equation (2.38) with respect to time, we can get the relation between the change of inter-distance and the change of robots' positions as follows:

ḋij = - (p j -p i ) T d ij (p j -p i ) T d ij   ṗi ṗj   (2.39)
In case of four robots as shown in Figure 2.17b, the formation Jacobian J f can be derived by stacking Equation (2.39):

ḋf = J f v (2.40)
where:

ḋf =               ḋ12 ḋ13 ḋ14 ḋ23 ḋ24 ḋ34               , J f =               -n 12 n 12 0 1×2 0 1×2 -n 13 0 1×2 n 13 0 1×2 -n 14 0 1×2 0 1×2 n 14 0 1×2 -n 23 n 23 0 1×2 0 1×2 -n 24 0 1×2 n 24 0 1×2 0 1×2 -n 34 n 34               6×8 n ij = (p j -p i ) T d ij
From Equation (2.34), the formation task is, thus, defined as follows:

J f v = -λ f (d f -d * f ) (2.41)
where d and d * f are vectors of current and desired inter-distances, respectively. λ f is the formation control gain.

Cooperative navigation

This task focuses on driving the formation's centroid toward a desired point p d = (x d , y d ) T and orientation θ d . The pose (position and orientation) of the centroid is used as the control feature. Figure 2.18 shows the task of team navigation, in which the centroid p c = (x c , y c ) T has to move toward a target point p d as well as to orient its heading to any desired angle, in that case, θ d . The position of formation's centroid is defined as following, with n is the number of robots in the group:

x c = 1 n n i=1 x i and y c = 1 n n i=1 y i (2.42)
The point p h = (x h , y h ) T can be defined anywhere, relatively to each robot in the group. This point can be used to determine the heading of formation, and it can be expressed in relation to robots' positions as follows:

x h = n i=1 a i x i and y h = n i=1 a i y i (2.43)
where a i is the relation coefficient to i th robot, and n i=1 a i = 1. For instance, a 1 = a 2 = 0.5 and a 3 = a 4 = 0 in the configuration shown in Figure 2.18. The group's heading can be found using p c and p h :

θ c = arctan y h -y c x h -x c = arctan n i=1 y i a i -1 n n i=1 x i a i -1 n (2.44)
By differentiating Equation (2.42) and (2.44) with respect to time, the Jacobian of navigation task J n can be determined as follows:

     ẋc ẏc θc      =      1/n 0 • • • 1/n 0 0 1/n • • • 0 1/n -m y 1 m x 1 • • • -m yn m xn           ṗ1 . . . ṗn      (2.45)
where:

m x j = (a j -1/n) n i=1 x i a i -1 n n i=1 x i a i -1 n 2 + n i=1 y i a i -1 n 2 m y j = (a j -1/n) n i=1 y i a i -1 n n i=1 x i a i -1 n 2 + n i=1 y i a i -1 n 2 j = 1, 2, ..

., n

Applying to four robots configuration, we get:

ẋc ẏc θc T = J n v (2.46)
where

J n =      1/4 0 • • • 1/4 0 0 1/4 • • • 0 1/4 -m y 1 m x 1 • • • -m y 4 m x 4     
From Equation (2.34), the navigation task can be derived as follows:

J n v = -   λ p (p c -p d ) λ θ (θ c -θ d )   (2.47)
where λ p and λ θ are the control gains for position and orientation, respectively. Two obstacle avoidance schemes are introduced in the overall control law depending on the situation (Figure 2.19). For instance, individual obstacle avoidance is useful when each robot tries to converge to a defined formation, while the team avoidance is more practical during navigation. They can be seen as sets of inequality constraints whose purpose is to make sure that the distances to the obstacle(s), which are the control features, can never be smaller than the safety distances [START_REF] Héctor | Multi-vehicle coordination based on hierarchical quadratic programming[END_REF]. They can be found as follows:

Individual and team obstacle avoidance

d o i = ∥p o i -p i ∥ and d ot = ∥p o t -p c ∥ (2.48)
Similar to the formation task, we differentiate Equation (2.48) with respect to time. For each obstacle, we get the following:

ḋo i = (p i -p o i ) T d o i ṗi ḋot = (p c -p o t ) T d ot   1/n 0 • • • 1/n 0 0 1/n • • • 0 1/n        ṗ1 . . . ṗn      (2.49)
Consider for our four robots, the individual and team obstacle avoidance Jacobian, J o i and J o t , respectively, are written as follows:

J o i = (p i -p o i ) T d o i J o t = (p c -p o t ) T 4d ot I 2 I 2 I 2 I 2 2×8
(2.50)

The inequality constraints of the obstacle avoidance tasks can be, therefore, expressed as follows:

J o i v i ≥ -λ o i (d o i -d s i ) J o t v t ≥ -λ ot (d o t -d s t ) (2.51)
where λ o i and λ ot are the control gains for individual and team obstacle avoidance, respectively.

The distances can be in the form of vectors or scalars depending on the number of obstacles detected in the workspace, and they can also be null (thus no inequality constraint) if there is no presence of the obstacle.

Velocity limits

An upper and lower velocity limit is imposed on the robot's left and right wheel as inequality constraints. Consider b and r as, respectively, the distance between the two wheels and wheel's radius (as shown in Figure 2.1), the relation of linear and angular velocity (v i , ω i ) to wheel's velocity (ω l,i , ω r,i ) of i th robot can be expressed as follows:

ω l,i = 1 r (v i -0.5bω i ) ω r,i = 1 r (v i + 0.5bω i ) (2.52)
Therefore, the inequality constraint of the velocity limit for four robots can be written as following: (2.53) where:

J lim u ≤ ω lim
J lim is a 16 × 8 block diagonal matrix of G, G = 1 r         1 -0.5b 1 0.5b -1 0.5b -1 -0.5b        
,

ω lim =         H H H H         , H =         ω l,max ω r,max -ω l,min -ω r,min        

Simulation and experimental results

In order to validate the proposed algorithm, the control scheme is decomposed into two behavior states:

-Stage 1 (S1): Initial formation ensures that the desired shape is reached before mounting the payload on top. At this stage, only one level of optimization is needed. Hence, a formation task that is subjected to individual obstacle avoidance and velocity limits constraints, which leads to the initial formation. -Stage 2 (S2): Cooperative navigation is responsible for driving the centroid to a target point, taking into account preservation of formation, team obstacle avoidance, and velocity limit. Therefore, two hierarchies are proposed. A higher level for solving the formation task, and a second priority for the navigation task. From Equation (2.36), the HQP problem can be written as follows:

Level 1 :

u 1 = arg min x ∥A 1 x -b 1 ∥ 2 s.t. C 1 x ≤ d 1 Level 2 : u = arg min x ∥A 2 x -b 2 ∥ 2 s.t. A 1 x = A 1 u 1 C 2 x ≤ d 2 (2.54)
Table 2.2 summarizes the overall control law of the system. The control input is always a solution from the last hierarchy, which is solved using the pseudo-inverse approach in order to avoid having multiple sets of solutions. The hierarchical priority order of the tasks is velocity limits ≻ obstacle avoidance ≻ formation ≻ navigation task. Table 2.2 -Hierarchy levels of tasks for the two behavior states

S1: u ≡ u f S2: u ≡ u n Level 1 min u f ∥J f J x u f + λ f (d f -d * f )∥ 2 s.t. J o i J x u i ≥ -λ o i (d o i -d s i ) J lim u f ≤ ω lim min u f ∥J f J x u f + λ f (d f -d * f )∥ 2 s.t. J lim u f ≤ ω lim Level 2 none min un J n J x u n + λ p (p c -p d ) λ θ (θ c -θ d ) 2 s.t. J f J x u n = J f J x u f J o t J x u n ≥ -λ ot (d o t -d s t ) J lim u n ≤ ω lim
The program always starts from S1 behavior until inter-distance errors between robots fall below a certain threshold before switching to S2. In addition, if there is any sudden increase of the inter-distance errors above a threshold, the controller will transition back to S1 to ensure the formation before moving again.

Similar to the experimental setup in the previous section, ROS and Gazebo are used to simulate the robots and environment for the simulation. For the real experiment, all robots in the team send their localized position to a PC for performing the optimization. The resultant velocities are then broadcast back to each corresponding robot for motion control.

Simulation

Two simulations are done with different numbers of robots in the formation. In both cases, the controller respects the hierarchy levels described previously. In addition, the graphs for the two simulations are fully-connected and rigid. Hence, the number of features for the formation task is six and nine for simulations I and II, respectively. The desired inter-distance for the side neighbors is 2.0m. Simulation I: A group of four robots starts the formation at a less-than-ideal shape. Alongside the robots, there are three obstacles in the environment as shown in Figure 2.20. Figure 2.21a shows the convergence of inter-distances to the desired values at around t = 10s; this marks the end of stage S1 and begins the cooperative navigation phase. Figure 2.21c illustrates the error of inter-distances with respect to the desired values; these inter-distances are well maintained with a very small deviation from the set desired values (±7.5mm) as shown in Figure 2.21d. During this time, the formation heading angle also converges a set value of 90 o as shown in Figure 2.21b, where the error converges nicely to zero. Last but not least, the overall trajectories are demonstrated in Figure 2.21e. The blue square is the formation shape when stage S1 is completed. Simulation II: As shown in six robots and three obstacles are utilized in this simulation. Figure 2.22 shows the simulation environment, in which there are three obstacles: a round, a square, and a rotated square.

From Figure 2.23a, we can see that the inter-distance errors converge to form the formation (S1) at around t = 25s. After that, the robots start to move to a goal point with the desired formation heading of -90 o . The team's orientation error is well-converged with an error of less than 5 o as illustrated in Figure 2.23b. The shape is preserved throughout the navigation as shown in Figure 2.23c. The maximum inter-distance error is around ±0.018m even though they have to navigate through obstacles as demonstrated in Figure 2.23d. Since the readability of the trajectories plot is increased as the number of robots increases, snapshots of the Gazebo are instead provided to aid in visualizing the formation shape; In this experiment, we separate the stages S1 and S2 into two experiments because the group has to first get into a good formation shape, then the payload is manually attached before starting the navigation. In both cases, a square shape formation of sides of 2m is desired. ROS is used as the middleware. Each robot has its own independent ROS_MASTER. There is no external sensor to locate each robot accurately. The selflocalization in a map is done using an onboard lidar sensor. In contrast to the distributed local controller of consensus, the control velocities for each robot are computed by a centralized optimization solver, an architecture of which is shown in Figure 2.25. S1: Figure 2.26 shows the actual initial poses of the robots, which is not yet a square shape. In addition, there exists an obstacle in order to trigger the individual obstacle avoidance inequality constraint. whereas the black square represents the shape midway when the fleet reaches the goal before returning. The team's desired heading angle is also reached for both journeys as the error converges to zero as demonstrated in Figure 2.29c. In order to show the effectiveness of the proposed approach, we also perform more experiments using a reduced number of inter-distance features. As the goal is to see its effectiveness for different formation configurations, we do not need to attach any load to the fleet. Therefore, we can combine the two stages S1 and S2 in one run for each test. As discussed in the rigidity part of Section 2.2.2, one can define a minimally rigid graph and the formation shall still be fixed. To validate this, we try the proposed HQP controller with a team of three, four, and five robots with a reduced number of edges (2n -3). All following experiments start with initial poses that require the fleet to do formation phase S1 first before navigating to a goal point while avoiding one un-mapped obstacle.

Four robots: Figure 2.30 shows the topology of the experimental setup for four robots, which we use the concept of minimally rigid graph resulting in only five (using Equation (2.10)) inter-distances required for the formation, instead of six (using Equation (2.8)). Figure 2.31 shows the testing result of a square formation. The shape is reached at around t = 12s as shown in Figure 2.31d. Then, the fleet starts to move to the goal point without breaking up as the inter-distances errors remain below ±0.05m, illustrated in Figure 2.31a and Figure 2.31b. The team's heading also reaches the desired value since its error converges nicely to zero as demonstrated in Figure 2.31c.

By simply changing the values of desired inter-distances, we can define any formation shape we want. For instance, Figure 2.32 shows a shape that is similar to an antenna can be achieved using the same graph topology as the previous case, but with a different set of values for the inter-distances. The experimental result is shown in Figure 2.33. From a bad initial formation shape, the team of robots reaches the desired shape at around t = 15s. Then they start to navigate to the goal point without any collision with the obstacle. The errors of interdistances remain well under ±0.04m. Three robots: Figure 2.37 shows the inter-distance configuration in the case of three robots. In this case, the required number of connected edges/robots can not be reduced further as apply the Equation (2.8) and (2.10) gives the same result of three. Last but not least, a line formation experiment is done to show that the proposed controller is robust in terms of the different configurations of the formation shape; the result of which can be seen in Figure 2.38. Once again, after reaching the initial formation stage, the fleet can navigate to the goal point while avoiding any collision and keeping the formation shape. The desired orientation converges to zero, while the errors of interdistances are within ±0.08m as shown in

Conclusion

In this section, we present a method for cooperative object transportation with obstacle avoidance based on an optimization approach. Different tasks were formulated to either equality or inequality constraints, which are solved using the hierarchical quadratic programming method. Simulations and actual experiments with different numbers of robots and formation shapes are conducted in order to validate the effectiveness of the proposed approach. Un-mapped obstacles in the environment can be detected and evaded during runtime reactively. Videos of some of the experiments can be found following these links5 .

Conclusion on formation control

We have discussed the two proposed formation controllers in this chapter. The first approach is based on the consensus algorithm in order to reach an equilibrium in terms of inter-distances between robots in the team. Graph theory is presented as a basis for modeling the communication between neighbors, while the concept of static state feedback is used in order to deploy the controllers in real nonholonomic mobile robots. Simulations and experiments are shown to validate the proposed consensus formation controller. In both situations, the fleet can perform the formation to reach a specific shape and keep it during navigating and obstacle avoidance. Despite enjoying the benefit of being a distributed controller, however, this approach suffers a problem of not being able to clearly impose a strict priority for each task; this results in having a fleet behavior that can not ensure precisely desired inter-distances between neighbors.

On the other hand, task priority can be introduced and respected in the hierarchical quadratic programming approach, which corresponds to our second contribution of the chapter. Using the concept of task-based control, we can define the Jacobian matrix that relates the robots' velocities to any feature we want to control, the inter-distances in this case. Tasks defined for this approach are: 1) geometric shape formation, 2) cooperative navigation, 3) individual and team obstacle avoidance, and 4) velocity limits. We introduce two levels of the optimization problem, which can be solved using HQP. Simulations and actual experiments are presented to evaluate the controller performance. Especially for the real experimental part, we have shown that the proposed controller can be used with a different number of robots to achieve various formation shapes. By applying the rules of the minimally rigid graph, the complexity of the optimization problem is linearly proportional to the number of robots in the fleet as the number of connected neighbors required is 2n -3 compared to the full n(n -1)/2 number of edges.

As the formation control enables a group of robots to cooperatively carry a load, it can not decide which robot should be chosen for the formation team; this is why multi-robot task allocation is needed in order to adequately choose and team up robots in a group ready for the cooperative transporting task. This will be the main purpose of the next chapter.

Introduction

Task allocation is a requirement for multi-robot systems working in dynamic environments. An efficient task allocation model allows the robots to adjust their workloads in response to other robots' actions or system's missions to increase overall system performance.

This chapter presents an allocation problem that deals with tasks that requires single or multiple robots to complete. The tasks can be allocated statically at a fixed interval or dynamically as soon as they arrive. Two existing task allocation techniques were compared in order to find the most suitable approach for our application. The first technique is based on the market-based approach, namely Contract Net Protocol (CNP). CNP is a distributed allocation approach that relies on each robot to bid in order to compete for obtaining the task. Tabu Search (TS) is the second technique, which we look into. It is a centralized optimization-based approach.

The chapter starts with the problem statement, which can be found in Section 3.2. Section 3.3 describes the algorithms of task allocation techniques we use. Last but not least, simulation results of a various number of robots and tasks are detailed in Section 3.4.

Problem definition

Let us consider a team of n robots, R = {R 1 , R 2 , • • • , R n }, and a set of m tasks

T = {T 1 , T 2 , • • • , T m }
, the potential solution for allocation shall reflect an optimal list of allocations; an example of which can be as

[R 1 T 1 T 2 R 2 T 3 T 4 T 5 • • • ].
Multi-robot task allocation (MRTA) is an optimization problem aiming to solve this allocation by minimizing a cost function or maximizing a profit. Therefore, such a problem can be expressed mathematically as follows:

min n i=1 m j=1 w ij f ij or max n i=1 m j=1 w ij f ij f ij ∈ {0, 1}, ∀i ∈ [1, n], ∀j ∈ [1, m] (3.1)
where w ij is the cost, which can be the distance to travel, time for completion, etc., or reward, depending on the optimization type, for assigning robot i to task j. f ij is equal to 1 if the i th robot is assigned to j th task, and 0 otherwise.

The optimization problem shown in Equation (3.1) can be subjected to various constraints depending on the specific application of allocation; some of the most common ones are as follows:

n i=1 f ij = L j , ∀j ∈ [1, m] (3.2) m j=1 f ij ≤ L i , ∀i ∈ [1, n] (3.3)
where L j represents the number of robots required for task j and L i is the maximum number of assignments allowed to each robot. Equation (3.2) ensures that an appropriate amount of robots is allocated to a task; L j = 1 in the case of single-robot task. Depending on nature of the application, L i of Equation (3.3) can be equal to 1; it corresponds to the single-assignment problem [START_REF] Wu | Collisionaware Task Assignment for Multi-Robot Systems[END_REF].

For our application, the task allocation is deployed for logistics in warehouse environments. The problem focuses on having a list of tasks executed in less time possible. In addition, it has to be able to deal with tasks that are added in real-time. We focus on an environment with up to 10 robots and 40 tasks. The robots are single-task robots, thus they can do only one task at a time, but they are able to have multiple tasks in the queue. We assume that each robot has the same skills and velocity. Tasks are pick-up and drop-off missions. The robots need to pick up an object, move to a new location, and drop them off. The tasks can also require several robots working together to complete. Therefore, they can be either single-robot or multi-robot tasks. We assume that the time for picking and dropping an object is negligible compared to the travel time. Each task has a priority level to indicate the urgency for completion.

The allocation of tasks can be done on two levels. Initially, there is a set of tasks to be assigned, hence static allocation. Then, tasks can be added online for allocation dynamically. This dynamic allocation assigns high-priority tasks to available robots as soon as the task is introduced; this is level one allocation. The remaining unassigned tasks are added to the level two allocation loop, namely static allocation, which runs at a fixed slower frequency In order to evaluate the two approaches: CNP and TS, we focus on optimizing the overall time needed to perform the task. Therefore, the travel time of each robot for the tasks is considered as the cost objective.

Methodology

In this section, we discuss the formulation of the cost function that is used for allocating tasks, which is based on the estimated travel time of each robot. Then we discuss in detail the Contract Net Protocol and Tabu Search algorithm, as well as a simplified Local Search approach. The idea is to use CNP as the set of initial solutions for the TS, which could enable us to better optimize the solutions with less search iteration.

Objective function

The objective function is a minimization problem with a cost that is based on the traveling time of the robots. From Equation (3.1), the function can be expressed as follows:

min n i=1 m j=1 w ij f ij f ij ∈ {0, 1}, ∀i ∈ [1, n], ∀j ∈ [1, m] (3.4)
where w ij is the estimated time for robot i to complete task j. The traveling distance can also be chosen, but we have decided to work with the time because it is able to easily incorporate the waiting time of the robot when dealing with multi-robot tasks (tasks that require more than one robot to complete). If one robot arrives first, it has to wait for others in order to start performing the mission together. Therefore, the estimated time w ij includes: the time to travel from the current position to the pick-up point, the time to travel from the pick-up point to the drop-off point, and the waiting time in case of the multi-robot tasks.

Contract Net Protocol approach

The first algorithm to be tested to solve this Multi-Robot Task Allocation (MRTA) problem is the Contract Net Protocol (CNP). It is an auction-based approach that consists of four stages [START_REF] Basile | An auction-based approach to control automated warehouses using smart vehicles[END_REF]:

1. Announcement: an auctioneer broadcasts the task to other robots.

2. Submission: each robot computes a cost for performing that task based on a defined cost function.

3. Selection: the auctioneer chooses a winner with the lowest bid.

4. Contract: information of who is the winner announced by the auctioneer.

Figure 3.1 presents the flowchart of the CNP algorithm. It runs each time an allocation of one task to the robots is needed. Thus, the input of this function is the task to allocate. This process is repeated as many times as the number of tasks to allocate. The bids are made by all the robots that are available for the tasks. A robot is set to be available if it has not started moving or has just finished a task. The bids of robots are added to a list of bids that are then sorted to select the lowest bid(s). There are as many bids selected as the number of robots required by the task (in the case of multi-robot tasks). one, the notion of Tabu is introduced. A Tabu is set to make it impossible to invert the two elements of the current solution that would lead to the past solution. This Tabu is kept for several iterations of the Tabu Search and is then removed to free some memory. By doing this, cycling on a local minimum is avoided. However, if this local minimum is the best solution found by the algorithm when it comes across it, it is set as being the global best solution. Each time a local optimum is found it is compared to the global best solution to know if it should be kept in memory or not.

Simplified Local Search approach

The iterations of Tabu Search require a lot of computational resources and time. Indeed, finding all the neighbors of a solution requires m 2 operations, where m is the number of tasks. The initialization solution can be random or not. In order to improve

Experimental results

In this section, we present a series of multi-robot task allocation results using the Tabu Search and Contract Net Protocol approach. The experiments that are done aim to find the best values for those criteria and obtain a function giving these values depending on some parameters such as the number of robots and the number of tasks. These experiments also compare the use of the TS algorithm with the CNP. With these comparisons, we can introduce a dynamic task allocator, which is able to switch between using CNP and TS depending on different criteria. The objective is to minimize the traveling time of all the robots while having the smallest computational time possible. We consider the following equations to compare the allocation method with respect to the CNP. Equation (3.5) expresses the overall execution time, which is an addition of the computation or allocation time of the algorithm and the traveling time of the robots to complete all tasks. Generally, centralized search algorithms tend to a give better solution, but they also require more computational time. This is why we are going to talk about the gain which will be the time gained from one solution to another taking into account both the computational time and the traveling time. The comparisons are always going to be done with the results obtained using CNP as a reference, as shown in Equation (3.6) and (3.7). Then the overall gain can be determined using Equation (3.8)

Experimental setups

Environment

The warehouse environment is simulated with a configuration as shown in Figure 3.5. Robots can only move in the white area, which represents free space. They can be at and start from any point of the map that is in the white area. The grey part represents walls, obstacles, or picking racks. Using this environment, the comparison of allocation algorithms includes a range between 2 and 10 robots, and up to 40 tasks.

Simulated robots

Good communication between vehicles, the ability to pick up and drop off objects, and good precision of the localization system are all assumed. The capacity to avoid obstacles or other robots is not taken into account in the simulation. Thus, no collision between vehicles is taken into account in the simulation. This ability or the notion of safety distances between the robots can be added. The robots can modify their velocity for this matter if needed. They are identical and take the same time to complete the tasks once they have reached the starting position of the task. The actual picking up and dropping off actions are not studied; it is assumed that they can perform them correctly. The robots that are not required for the tasks are idle. A list of assumptions is as follows:

Pre-estimated cost matrix

The values of estimated time to go from an ending point of a task to the starting point of another task are stored in a matrix to avoid recomputing them several times. The time estimation is based on a path that is generated by the A* path planning algorithm assuming there is no obstacle in the map. This path is then converted into time through an estimation of travel velocity. For algorithms such as TS, it appears that this estimated time is called many times in order to compute the traveling time of all neighbors of one solution. Therefore, the values of travel time from one task to another are the same as tasks to allocate do not change. For this reason, it is beneficial to pre-compute and stores these values in the memory. The time matrix is defined as follows:

M =      t 1,1 • • • t 1,n . . . . . . t n,1 • • • t n,n      (3.9)
where t i,i is the time to travel task i from start to end and t i,j is the travel time from the endpoint of task i to the start point of task j.

In practice, the pre-computation can be done automatically by storing the estimated time to go from point A to B. If the same computation is required later on, then the cached value is recalled without any computation.

Preliminary experiments

Advantage of pre-computed cost values

To verify the advantage of using such matrix, an experiment is done comparing the computational time required for the allocation of 10 tasks to 5 robots through a TS algorithm with one iteration without storing the results of the estimate function in a cost matrix presented in Figure 3.6 and with storing the results of the estimate function in a cost matrix presented in Figure 3.7. Comparing those two figures it appears that thirty seconds per iteration of the TS algorithm can be gained from storing the estimated cost in the matrix. Indeed, each iteration of TS algorithm will call one time each value of the cost matrix. Therefore, computing the same cost each time is an imprudent use of the resource. A pre-computed cost matrix for tasks is used in the following experiments.

Comparison between Dijkstra and A* for path planning

It is possible to use several path-finding algorithms to select the best path taken by the robots and minimize the computational cost of the path-finding algorithm and the traveling distance of the robots. A comparison is made using the Dijkstra algorithm or A* algorithm in the allocation of 10 tasks to 5 robots.

-Results for 10 tasks, 5 robots using the CNP and Dijkstra algorithm:

-Computation Time: 23s -Traveling Time: 1260s -Results for 10 tasks, 5 robots using the CNP and A* algorithm:

-Computation Time: 56s -Traveling Time: 1737s The impact of the choice of the path-finding algorithm is on the computational time of the estimate function and on the traveling distance of the robots. It appears that both the computational time and the traveling time increase using the A* algorithm for our simulation. Therefore, the Dijkstra algorithm is used in the following simulations.

Impact of the number of tasks on the computation and traveling time

The impact of the number of tasks on the computational time and on the traveling is studied for the case where 5 robots are available using either the CNP or the TS algorithm with 1, 2, 4, or 10 iterations. The impact of the number of tasks on the computational time is presented in Figure 3.8. The impact of the number of tasks on the traveling time is presented in Figure 3.9.

It can be observed in Figure 3.8 that for all allocation methods, the computational time increases with the number of tasks that have to be allocated. This increase in Figure 3.8 -Impact of the number of tasks to allocate to 5 robots on the computational time of the studied algorithms computational time is faster for the TS algorithm than for the CNP, and it is faster when many iterations of the TS are done. Indeed, it can be observed that 91.26s are required to allocate 5 tasks and for 10 iterations of the TS algorithm, 8777.51s of computation are required to allocate 40 tasks with the same algorithm. This is an increase of 9519% of the time required for 5 tasks. When using the CNP 5.13s are required to allocate 5 tasks and 67.78s are required to allocate 40 tasks. This is an increase of 1220%. The explanation of the impact of the number of tasks on the allocation algorithms is the increasing number of operations that comes with the increasing number of tasks. This is greater for the TS algorithm as this algorithm calls a loop on the number of tasks inside a loop on the number of tasks which means it has approximately m 2 operations to do, where m is the number of tasks.

It can be observed in Figure 3.9 that for all allocation methods, the total traveling time increases with the number of tasks that are allocated. As an example, the total traveling time for the 5 robots is 2980.62s when they are doing 40 tasks that were allocated through Figure 3.9 -Impact of the number of tasks allocated to 5 robots on the traveling time of the robots depending on the studied algorithms a TS algorithm with 10 iterations and 259.53s when they are doing 5 tasks allocated through the same algorithm. It is 4844.45s for 40 tasks allocated through the CNP and 264.64s for 5 tasks allocated through the CNP. It can also be seen that the total traveling time is lower with the TS algorithm than with the CNP and when many iterations of the TS algorithm are used. Indeed, the solution that is found reduces the cost function value, although it requires more computational time as it was previously highlighted. This improvement of the cost function value is greater when a high number of tasks is allocated. As an example the improvement for the allocation of 5 tasks using the TS with 10 iterations compared to when using the CNP is 1.9%, it is 38% for the allocation of 40 tasks.

Impact of the number of robots on the computation and traveling time

The impact of the number of robots on the computational time and on the traveling time is studied for the case where 10 tasks are allocated to the robots using either the CNP or the TS algorithm with 1, 2, 4, or 10 iterations. The impact of the number of robots on the computational time is presented in Figure 3.10. The impact of the number of robots on the traveling time is presented in Figure 3.11. Figure 3.10 -Impact of the number of robots on the computational time of the studied algorithms for the allocation of 10 tasks It can be observed in Figure 3.10 that for all allocation methods, the computational time increases with the number of robots that are used in the multi-robot system (MRS). This increase in computational time is faster for the TS algorithm than for the CNP, and it is faster when many iterations of the TS are done. Indeed, it can be observed that using the CNP, the computational time required for the allocation of 10 tasks to robots is 4.89s for 2 robots and 24.28s for 10 robots. This is an increase of 396%. Using 4 iterations of the TS algorithm this time is 27.32s for 2 robots and 337.28s for 10 robots. This is an increase of 1134%. Using 10 iterations of the TS algorithm this time is of 58.78s for 2 robots and of 767.12s for 10 robots. This is an increase of 1205%.

It can be observed in Figure 3.11 that for all allocation methods, the total traveling time decreases with the number of robots that are used in the multi-robot system (MRS). Figure 3.11 -Impact of the number of robots on their total traveling time using the studied algorithms for the allocation of 10 tasks This decrease in total traveling time is faster for the CNP than for the TS algorithm, and it is slower when many iterations of the TS are done. Indeed, it can be observed that using the CNP, the total traveling time required to do the 10 tasks is 891.99s for 2 robots and 628.81s for 10 robots. This is a decrease of 29.5%. Using four iterations of the TS algorithm this time is 612.10s for 2 robots and 565.74s for 10 robots. This is a decrease of 8%. Using 10 iterations of the TS algorithm this time is 596.68s for 2 robots and 565.54s for 10 robots. This is a decrease of 5%. It is also observed that, although the decrease is slower for the TS algorithm than for the CNP, the total traveling time is always better when a high number of iterations is done and is better for the TS algorithm than for the CNP. But the more robots are in the MRS, the smallest this improvement is. There is also less improvement from doing one extra iteration of the TS algorithm than from switching from the CNP to the simplified Local Search method, or the TS algorithm with one iteration.

All in all, the more robots there are in the MRS, the less interesting it is to use the TS algorithm in terms of traveling time and computational time. However, the improvement of traveling time using the TS algorithm with one iteration compared to using the CNP is high, about 27% with a 2-robot-MRS and 10% with a 10-robot-MRS. In addition, the increase of the computational time is slow with the increase in the number of robots for one iteration of the TS. Therefore, only the Tabu Search algorithm with one iteration will be compared with the Contract Net Protocol in detail, which is presented in the next section.

Comparison experiments 5 tasks using CNP and Tabu Search algorithm

The first case studied is the allocation of 5 tasks. The results are presented in Figure 3.12. It can be observed that, in the case of the allocation of 5 tasks, the best method of allocation with MRS of 5 and 10 robots is the CNP. Figure 3.12 -Time gain evolution depending on the allocation mode and the number of robots for 5 tasks allocated. Indeed, the gain is immediately negative with the use of the TS algorithm. It decreases even more with the increase in the number of iterations done. This is consistent with the results observed in Section 3.4.2 as the increase in the number of tasks implies an increase in the computational time that is faster for the TS algorithm than for the CNP, while the improvement seen in the value of the cost becomes the smallest when many iterations of the TS algorithm are done when the number of robots used in the MRS is high. Therefore, a high increase of the computation time for a low decrease of the traveling time when using the TS algorithm compared to the CNP for an increasing number of robots. This explains the decrease of the gain that comes with the increase of the number of robots. Moreover, it is seen in Section 3.4.2 that for a low number of tasks the amount of improvement in the traveling time gained from using the TS algorithm is even lower. This explains that in the case of the allocation of 5 tasks the best method is the CNP even when 5 robots are used in the MRS. However, for a MRS with 2 robots, the best method is the Tabu Search algorithm with one iteration. The gain observed for the allocation of 5 tasks to 2 robots using the TS algorithm with one iteration is of 17.2s compared to when using the CNP. This is due to the fact that for a low number of robots, the increase of the computation time using the TS is low and the benefit in the traveling time is high as seen in Section 3.4.2.

tasks using CNP and Tabu Search algorithm

With the number of tasks increased to 10, the allocation results are presented in Figure 3.13. It can be observed that for the use of 2 robots when 10 tasks are allocated, the gain is best for 4 iterations of the Tabu Search algorithm. It is 257.45s for 4 iterations so it corresponds to an improvement of 28.7% of the complete experiment time obtained through the CNP algorithm which is 896.9s. For the use of 5 robots when 10 tasks are allocated, the gain is best for one iteration of the Tabu Search algorithm, corresponding to the simplified Tabu Search algorithm. It is 42.54s for one iteration of the TS algorithm so it corresponds to an improvement of 6% of the complete experiment time obtained through the CNP algorithm, which is 710s. For the use of 10 robots when 10 tasks are allocated, there is no gain using the Tabu Search algorithm. It is best to only use the CNP. Indeed, as seen in Section 3.4.2 the more robots are in the MRS, the less improvement it is in terms of traveling time, and the more computational time is required.

Tasks using CNP and Tabu Search algorithm

The third case of this experiment is for the allocation of 20 tasks. The results are presented in Figure 3.14. As seen in the two previous cases the gain is decreasing with the number of robots in the MRS and with the number of iterations of the TS algorithm. Oppositely to before the gain is very low even for the use of only 2 robots in the MRS. This is due to the impact of the number of tasks to allocate seen in Section 3.4.2. Indeed, the more tasks are added, the more quickly the computational time increases with the number of iterations. In the case of the allocation of 20 tasks, the gain is slightly positive when using one iteration of the TS algorithm for a 2-robot-MRS. It is 56.50s, which corresponds to an improvement of 3% of the total execution time when the CNP is used which is 1760s. For MRS of more robots, the CNP is the best method to use.

Tasks using CNP and Tabu Search algorithm

Last but not least, an allocation of 40 tasks is simulated, whose results are presented in Figure 3.15. The results are similar to the one presented in Figure 3.14 for 20 tasks allocated. The gain is again decreasing with the number of robots and with the number of iterations. The gain is also low for the 2-robot-MRS. As previously explained, this is due to the fact that the more tasks are added the more quickly the computational time increases with the number of iterations as seen in Section 3.4.2. In the case of the allocation of 40 tasks, the gain is slightly positive when using the TS algorithm for a 2-robot-MRS. It is best with 4 iterations of this algorithm. It is 724.10s in this case, which corresponds to an improvement of 14.5% of the total execution time when the CNP is used which is 4987s. For a MRS of more robots, CNP is still the best method to use. The results of which algorithm is best for which case for our MRTA problem are presented in the table in Figure 3.16. It summarizes all the results obtained in Section 3.4.3. For MRS with 5 or more robots, the CNP is the best allocation method. The gain ob-tained with the use of the TS algorithm is either negative or too low to be generalized as being indeed positive with another computing system. However, for MRS with only two robots, the use of the TS algorithm is interesting, although one iteration of the TS algorithm is often enough to benefit from a better allocation compared to CNP. Since it is rarely the case for a warehouse to have less than 5 robots running, the search algorithm such as TS is not suitable for our application.

Conclusion on task allocation

A fundamental principle of task allocation, formulation of the objective function, is discussed in this chapter. We make a performance comparison between two task allocation approaches, namely Contract Net Protocol and Tabu Search. The comparison focuses on transportation tasks, which respond to the actual needs of a warehouse. The comparison criteria chosen is based on the overall total time, which includes the time needed to allocate and to complete a task. In addition, we show that having a pre-estimated cost matrix on travel time can be a benefit in terms of time-saving measure during the allocation process. Tasks are in form of a static list given at the start of allocation and dynamic, which are not pre-defined; they are added online during the runtime. As the number of robots in the environment increases, CNP takes significantly less time to perform the allocation compared to the TS. Therefore, CNP is more suitable for our application. a different number of tasks and robots. Due to the distributed nature of the CNP, it can allocate tasks quickly but is not necessarily optimal. By contrast, even though the objective cost of TS is always equal to or lower than that of CNP, its computational time required is too high compared to that of CNP.

Despite having favorable positive results in this thesis, several potential perspectives for future work can be considered. First of all, the current implementation of the proposed consensus formation control does not include the orientation control of the fleet's heading; future studies could extend the approach to include this part, which could improve navigation and obstacle avoidance behavior. For the optimization-based controller, it is interesting to extend to work to a distributed manner similar to what has been studied for the null-space approach in [START_REF] Trujillo | Priority Task-Based Formation Control and Obstacle Avoidance of Holonomic Agents with Continuous Control Inputs[END_REF]. The authors propose a controller that consists of a local task for obstacle avoidance and a global task for the formation. The individual avoidance task has more priority than the consensus formation control.

Another interesting extension to the formation control as a whole is to include trajectory planning in the multi-robot system. Since the current controllers are the reactive ones, a risk of getting stuck in a local minimum due to the obstacle's shape is prominent. A study of a trajectory planner that considers the geometric shape and constraint of the fleet can solve this issue. Thus, the navigation task of the controllers will just need to track waypoints generated by such a planner.

With recent parallel computing technology, it is compelling to study the improvement parallel computing makes to the Tabu Search algorithm in terms of computational time. In addition, the accuracy of the robot's traveling time estimation can be improved by having feedback on the actual travel time to adapt the estimation process. Last but not least, adding collision avoidance and multi-robot path planning could extend the accuracy of time estimation and increase the overall system's efficiency.

Abstract:

The interest in integrating multirobot systems (MRS) into real-world applications is increasing more and more, especially for performing complex tasks. For loadcarrying tasks, various load-handling strategies have been proposed such as: pushingonly, caging, and grasping. In this thesis, we aim to use a simple handling strategy: placing the carrying object on top of a group of wheeled mobile robots. Thus, it requires a rigid formation control. A consensus algorithm is one of the two formation controllers we apply to the system. We adapt a dynamic flocking controller to be used in the singleintegrator system, and we propose an obsta-cle avoidance that can prevent splitting while evading the obstacles. The second formation control is based on hierarchical quadratic programming (HQP). The problem is decomposed into multiple task objectives: formation, navigation, obstacle avoidance, velocity limits. These tasks are represented by equality and inequality constraints with different levels of priority, which are solved sequentially by the HQP. Lastly, a study on task allocation algorithms (Contract Net Protocol and Tabu Search) is carried out in order to determine an appropriate solution for allocating tasks in the industrial environment.

2. 4

 4 Example of (a) undirected and (b) directed graph. . . . . . . . . . . . . . . 2.5 Example of the connectivity of a graph: (a) connnected, (b) weakly connected, (c) strongly connected, and (d) disconnected graph. . . . . . . . . . 2.6 Example of a graph rigidity in 2D: (a) and (b) flexible/non-rigid, (c) and (d) minimally rigid, and (e) rigid. . . . . . . . . . . . . . . . . . . . . . . .2.7 Smooth pairwise function Ψ α (z) [Olf06]. . . . . . . . . . . . . . . . . . . . 2.8 Obstacles denoted by agent-based approach: (a) wall and (b) spherical obstacles [Olf06]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 Simulated system architecture. . . . . . . . . . . . . . . . . . . . . . . . . . 2.10 Gazebo environment for simulation. . . . . . . . . . . . . . . . . . . . . . . 2.11 Simulation of formation and obstacle avoidance using flocking / avoidance law of Equation (2.28). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Finding a neighborhood flowchart. . . . . . . . . . . . . . . . . . . . . . . . 3.3 Tabu Search flowchart. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Simplified Tabu Search flowchart. . . . . . . . . . . . . . . . . . . . . . . . 3.5 2D map of the simulated environment. . . . . . . . . . . . . . . . . . . . . 3.6 Computational time required for the TS algorithm with one iteration without storing the results of the estimate function in a cost matrix . . . . . . 3.7 Computational time required for the TS algorithm with one iteration with storing the results of the estimate function in a cost matrix . . . . . . . . . 3.8 Impact of the number of tasks to allocate to 5 robots on the computational time of the studied algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Impact of thenumber of tasks allocated to 5 robots on the traveling time of the robots depending on the studied algorithms . . . . . . . . . . . . . . 3.10 Impact of the number of robots on the computational time of the studied algorithms for the allocation of 10 tasks . . . . . . . . . . . . . . . . . . . . 3.11 Impact of the number of robots on their total traveling time using the studied algorithms for the allocation of 10 tasks . . . . . . . . . . . . . . . 3.12 Time gain evolution depending on the allocation mode and the number of robots for 5 tasks allocated. . . . . . . . . . . . . . . . . . . . . . . . . . . 3.13 Time gain evolution depending on the allocation mode and the number of robots for 10 tasks allocated. . . . . . . . . . . . . . . . . . . . . . . . . . . 3.14 Time gain evolution depending on the allocation mode and the number of robots for 20 tasks allocated. . . . . . . . . . . . . . . . . . . . . . . . . . . 3.15 Time gain evolution depending on the allocation mode and the number of robots for 40 tasks allocated. . . . . . . . . . . . . . . . . . . . . . . . . . . 3.16 Best results of different cases of robots and tasks. . . . . . . . . . . . . . .

Figure 1 -

 1 Figure 1 -A use case scenario of the MRS.

1. 3

 3 Formation control . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.1 Leader-follower . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.2 Virtual structure . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3.3 Behavior-based . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.3.4 Other approaches . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.4 Load handling strategy . . . . . . . . . . . . . . . . . . . . . . . 23 1.5 Task allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.5.1 Auction-based . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.5.2 Optimization-based . . . . . . . . . . . . . . . . . . . . . . . . 26 1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Figure 1

 1 Figure 1.1 -A centralized control architecture, where the orange node is the control agent.

Figure 1 . 2 -

 12 Figure 1.2 -A distributed control architecture.

Figure 1

 1 Figure 1.3 -A hierarchical control architecture.

Figure 1

 1 Figure 1.4 -A leader-follower example [LLL15].

Figure 1

 1 Figure 1.6 -A behavior-based controller with different behaviors.

Figure 1 . 7 -

 17 Figure 1.7 -Difference types of load handling techniques.

Figure 1

 1 Figure 1.8 -A process of auction-based task allocation [See+20].

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2 Consensus-based formation . . . . . . . . . . . . . . . . . . . . 32 2.2.1 Wheeled mobile robots modeling . . . . . . . . . . . . . . . . . 33 2.2.2 Graph theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.2.3 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.2.4 Formation control algorithm . . . . . . . . . . . . . . . . . . . . 42 2.2.5 Simulations and experimental results . . . . . . . . . . . . . . . 44 2.2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492.3 Optimization-based approach . . . . . . . . . . . . . . . . . . . 50 2.3.1 Task-based control . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.3.2 Hierarchical quadratic programming . . . . . . . . . . . . . . . 51 2.3.3 Task definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.3.4 Simulation and experimental results . . . . . . . . . . . . . . . 57 2.3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.4 Conclusion on formation control . . . . . . . . . . . . . . . . . 72

Figure 2 . 2 -

 22 Figure 2.2 -Top view of the system. The green square represents a support for load placement that is on top of the formation.

  Figure 2.3 shows an example of the graph consisting of five vertices V = {1, 3, . . . , 5} and three edges E = {{1, 2}, {1, 3}, {4, 5}}. The adjacency relationships of the such graph can be expressed in a matrix as follows:

Figure 2

 2 Figure 2.4 -Example of (a) undirected and (b) directed graph.

Figure 2 . 5 -

 25 Figure 2.5 -Example of the connectivity of a graph: (a) connnected, (b) weakly connected, (c) strongly connected, and (d) disconnected graph.

Figure 2

 2 Figure 2.6 -Example of a graph rigidity in 2D: (a) and (b) flexible/non-rigid, (c) and (d) minimally rigid, and (e) rigid.

( 2 .

 2 18) where σ 1 (z) = z/ √ 1 + z 2 . With 0 < a ≤ b and e = |a -b|/ √ 4ab, the uneven sigmoidal function Φ(z) = 0 when z = 0.

Figure 2 .

 2 Figure 2.7 -Smooth pairwise function Ψ α (z) [Olf06].

Figure 2 .

 2 Figure 2.8 -Obstacles denoted by agent-based approach: (a) wall and (b) spherical obstacles [Olf06].

Figure 2 .

 2 Figure 2.8 shows the agent-based approach of representing obstacles. An α-agent represents actual robots while a β-agent indicates the obstacles. The set of neighbors of node i can be written as:

Figure 2 .Figure 2

 22 Figure 2.9 illustrates the simulation architecture used. Gazebo 3 is used to simulate four robots under one ROS master. Each robot has its own localization, obstacle detection, and formation control node.The simulated environment is shown in Figure2.10. The obstacle is presented as the red cylinder whereas the green one represents the goal point.

Figure 2 .

 2 Figure 2.10 -Gazebo environment for simulation.

Figure 2 .

 2 Figure 2.11 -Simulation of formation and obstacle avoidance using flocking / avoidance law of Equation (2.28).

  Inter-distances between robots. (b) Robots' trajectories.

Figure 2 .

 2 Figure 2.12 -Simulation of formation and obstacle avoidance using the proposed control law, Equation (2.30).

Figure 2 .

 2 Figure 2.13 -Experimental setup of the consensus formation.

Figure 2 .

 2 Figure 2.14 shows the implementation result of the proposed control law. From Figure 2.14a, we can notice the convergence of the inter-distances between robots. In fact, once the inter-distances start to converge and stabilize, the formation shape is kept regardless of the disturbance from an obstacle.Figure 2.14b shows the trajectories of the four

Figure 2 .

 2 Figure 2.14 shows the implementation result of the proposed control law. From Figure 2.14a, we can notice the convergence of the inter-distances between robots. In fact, once the inter-distances start to converge and stabilize, the formation shape is kept regardless of the disturbance from an obstacle.Figure 2.14b shows the trajectories of the four

  Inter-distances between robots. (b) Robots' trajectories.

Figure 2 .

 2 Figure 2.14 -Real experiment of formation and obstacle avoidance using proposed control law, Equation (2.30).

Figure 2 .

 2 Figure 2.15 shows a sequence of snapshots of this experiment, where the fleet has to move from one point to another. An obstacle (a carton box) is placed in between the two points. This obstacle is not already known in the map, hence no initial path planning can try to avoid it; it has to be detected and avoided by the whole fleet during the navigation.

Figure 2 .

 2 Figure 2.15 -Snapshots of the experiment.

  Inter-distances between robots. (b) Robots' trajectories.

Figure 2 .

 2 Figure 2.16 -Experiment of the formation and obstacle avoidance using the proposed control law with square root diagonal neighbor distance.

  (a) Inter-distance between two robots (p i and p j ) denoted by d ij .(b) For four robots (p i , i = 1, 2, 3, 4).

Figure 2 .

 2 Figure 2.17 -Inter-distances diagram of the MRS, each blue node represents a mobile robot in 2D plane.

Figure 2 .

 2 Figure 2.18 -Navigation scheme, the blue nodes represent robots whereas the red node indicates a target point.

Figure 2 .

 2 Figure 2.19 illustrates the two obstacle scheme used to define their respective tasks. The red node represents a closest detected point of obstacle (Figure 2.19a) to robot, p o i and (Figure 2.19b) to group's centroid, p o t . d o i and d ot are the distances from i th robot and team's centroid to the obstacle, while d s i and d st are the safety distances for individual and team obstacle avoidance, respectively.

Figure 2 .

 2 Figure 2.19 -Obstacle avoidance scheme: (a) individual and (b) team avoidance.

Figure 2 .

 2 Figure 2.20 -Environment of simulation I.

  Inter-distances between robots.

Figure 2 .

 2 24a and Figure2.24b show the shape at the end of stage S1 and S2, respectively. Magnified inter-distances errors.

Figure 2 .

 2 Figure 2.23 -Plots of simulation II.

( a )

 a Formation shape at t = 25s. (b) End of the formation.

Figure 2 .Figure 2 .

 22 Figure 2.24 -Formation shape of simulation II.

Figure 2 .

 2 Figure 2.26 -Initial poses at S1.

  Inter-distances between robots.

  Errors of inter-distances.

  Heading error. (d) Robots' trajectories.

Figure 2 .

 2 Figure 2.29 -Plots of S2 experiment.

Figure 2 .

 2 Figure 2.30 -Reduced inter-distances edges of four-robots team.

Figure 2 .

 2 Figure 2.31 -Experiment of four robots with reduced number of inter-distance features.

Figure 2 .

 2 Figure 2.32 -Antenna shape of the formation.

  Errors of inter-distances.

  Magnified inter-distances errors.

Figure 2 .Figure 2 .

 22 Figure 2.33 -Experiment of four robots with reduced number of inter-distance features and modified desired inter-distances.

Figure 2 .

 2 Figure 2.35 shows the testing result of a pentagon formation. Once again, the desired shape is achieved at around t = 15s as shown in Figure 2.31d. While moving to the goal point, the fleet manages to keep the inter-distances close to the desired values as shown by the minimal value of errors in Figure 2.35a and Figure 2.35b.Figure 2.35c shows that the team's heading can reach the desired value with an error of less than 2 o . The trajectories of each robot and the fleet are demonstrated in Figure 2.35d.

Figure 2 .

 2 Figure 2.35 shows the testing result of a pentagon formation. Once again, the desired shape is achieved at around t = 15s as shown in Figure 2.31d. While moving to the goal point, the fleet manages to keep the inter-distances close to the desired values as shown by the minimal value of errors in Figure 2.35a and Figure 2.35b.Figure 2.35c shows that the team's heading can reach the desired value with an error of less than 2 o . The trajectories of each robot and the fleet are demonstrated in Figure 2.35d.

Figure 2 .

 2 Figure 2.35 -Experiment of five robots with reduced number of inter-distance features.

1 2 3 Figure 2 .

 32 Figure 2.36 -Three-robots configuration.

Figure 2 .

 2 Figure 2.37 illustrates the testing result of a triangle formation. At t = 12s, the formation shape in stage S1 is achieved. Then S2 starts to navigate the fleet to the goal point, during which the shape remains fixed as shown in Figure 2.37d. Similar to previous experiments, the inter-distances errors are largely below ±0.06m as demonstrated in Figure 2.31a and Figure 2.31b. The team's heading is eventually reached the desired value as shown in Figure 2.31c.

  Heading error. (d) Robots' trajectories.

Figure 2 .

 2 Figure 2.37 -Experiment of a triangle formation with three robots.

Figure 2 .

 2 38c and Figure 2.38b, respectively.

Figure 2 .

 2 Figure 2.38 -Experiment of a line formation with three robots.

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.2 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.3 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.3.1 Objective function . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.3.2 Contract Net Protocol approach . . . . . . . . . . . . . . . . . 76 3.3.3 Tabu Search approach . . . . . . . . . . . . . . . . . . . . . . . 77 3.3.4 Simplified Local Search approach . . . . . . . . . . . . . . . . . 78 3.4 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . 80 3.4.1 Experimental setups . . . . . . . . . . . . . . . . . . . . . . . . 81 3.4.2 Preliminary experiments . . . . . . . . . . . . . . . . . . . . . . 83 3.4.3 Comparison experiments . . . . . . . . . . . . . . . . . . . . . . 90 3.5 Conclusion on task allocation . . . . . . . . . . . . . . . . . . . 95

Figure 3 . 2 -

 32 Figure 3.2 -Finding a neighborhood flowchart.

Figure 3 .

 3 Figure 3.4 -Simplified Tabu Search flowchart.

Figure 3 .

 3 Figure 3.5 -2D map of the simulated environment.

  battery level.

Figure 3 .

 3 Figure 3.6 -Computational time required for the TS algorithm with one iteration without storing the results of the estimate function in a cost matrix

Figure 3 . 7 -

 37 Figure 3.7 -Computational time required for the TS algorithm with one iteration with storing the results of the estimate function in a cost matrix

Figure 3 .

 3 Figure 3.13 -Time gain evolution depending on the allocation mode and the number of robots for 10 tasks allocated.

Figure 3 .

 3 Figure 3.14 -Time gain evolution depending on the allocation mode and the number of robots for 20 tasks allocated.

Figure 3 .

 3 Figure 3.15 -Time gain evolution depending on the allocation mode and the number of robots for 40 tasks allocated.

Figure 3 .

 3 Figure 3.16 -Best results of different cases of robots and tasks.

Titre:

  Navigation coopérative d'une flotte de robots mobiles Mot clés : Systèmes multi-robots, contrôle de formation, algorithme de consensus, optimisation quadratique hiérarchique, allocation de tâches basée sur l'optimisation et les enchères. Résumé : L'intérêt pour l'intégration des systèmes multi-robots (MRS) dans les applications du monde réel augmente de plus en plus, notamment pour l'exécution de tâches complexes. Pour les tâches de transport de charges, différentes stratégies de manutention de charges ont été proposées telles que : la poussée seule, la mise en cage et la préhension. Dans cette thèse, nous souhaitons utiliser une stratégie de manipulation simple : placer l'objet à transporter au sommet d'un groupe de robots mobiles. Ainsi, cela nécessite un contrôle de formation rigide. Nous proposons deux algorithmes de formation. L'algorithme de consensus est l'un d'entre eux. Nous adaptons un contrôleur de flocking dynamique pour qu'il soit utilisé dans le système à un seul intégrateur, et nous proposons un système d'évitement d'obstacles qui peut empêcher le fractionnement tout en évitant les obstacles. Le deuxième contrôle de formation est basé sur l'optimisation quadratique hiérarchique (HQP). Le problème est décomposé en plusieurs objectifs de tâches : formation, navigation, évitement d'obstacles et limites de vitesse. Ces tâches sont représentées par des contraintes d'égalité et d'inégalité avec différents niveaux de priorité, qui sont résolues séquentiellement par le HQP. Enfin, une étude sur les algorithmes d'allocation des tâches (Contract Net Protocol et Tabu Search) est menée afin de déterminer une solution appropriée pour l'allocation des tâches dans l'environnement industriel. Title: Cooperative navigation of a fleet of mobile robots Keywords: Multi-robot system, formation control, consensus algorithm, hierarchical quadratic programming, optimation-based task allocation, auction-based task allocation.

  Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusion on task allocation . . . . . . . . . . . . . . . . . . . . . . . . . scenario of the MRS. . . . . . . . . . . . . . . . . . . . . . . . . 1.1 A centralized control architecture, where the orange node is the control agent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 A distributed control architecture. . . . . . . . . . . . . . . . . . . . . . . .

		LIST OF FIGURES
	1	A use case
	Conclusion
	Bibliography

3 Task allocation 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Objective function . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Contract Net Protocol approach . . . . . . . . . . . . . . . . . . . . 3.3.3 Tabu Search approach . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.4 Simplified Local Search approach . . . . . . . . . . . . . . . . . . . 3.4 3.4.1 Experimental setups . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Preliminary experiments . . . . . . . . . . . . . . . . . . . . . . . . 3.4.3 Comparison experiments . . . . . . . . . . . . . . . . . . . . . . . . 3.5 1.3 A hierarchical control architecture. . . . . . . . . . . . . . . . . . . . . . . 1.4 A leader-follower example [LLL15]. . . . . . . . . . . . . . . . . . . . . . . 1.5 A virtual structure using (a) virtual center approach [BWN09] and (b) virtual vehicle approach [YN08]. . . . . . . . . . . . . . . . . . . . . . . . . 1.6 A behavior-based controller with different behaviors. . . . . . . . . . . . . 1.7 Difference types of load handling techniques. . . . . . . . . . . . . . . . . . 1.8 A process of auction-based task allocation [See+20]. . . . . . . . . . . . . . 2.1 A nonholonomic wheeled mobile robot. . . . . . . . . . . . . . . . . . . . . 2.2 Top view of the system. The green square represents a support for load placement that is on top of the formation. . . . . . . . . . . . . . . . . . . 2.3 Example of a graph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Contents 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2 Control architecture

  Centralized architecture . . . . . . . . . . . . . . . . . . . . . . 16 1.2.2 Distributed architecture . . . . . . . . . . . . . . . . . . . . . . 17 1.2.3 Hierarchical architecture . . . . . . . . . . . . . . . . . . . . . . 17

. . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2.1

Table 1

 1

		.1 -Taxonomy of MRTA.
	Category	Type 1	Type 2
	Tasks	SR: can be completed by one robot.	MR: requires multiple robots.
	Robots	ST: can perform one task at a time.	MT: can perform multiple tasks at the same time.
	Assignment	IA: a robot is assigned to one task at a time.	TA: a robot are given a schedule of tasks.
	mized is distance and/or time. VRP is a more generalized version of mTSP. In VRP, the
	starting point of each vehicle does not have to be the same. Instead of having a list of
	towns or points to visit, it has sets of pickup and delivery location pairs. It aims to solve
	the problem of distributing goods or transporting passengers. Similar mTSP, vehicles will
	return to their own starting depot at the end.
	Since the MRTA evolves around minimizing an objective function, different techniques
	for representing the cost function have been introduced [G L+05]:

  .

	time experiment	=	time traveling	+	time computation	(3.5)
	gain traveling	=	time traveling method	-	time traveling CN P	(3.6)
	gain computation	=	time computation method	-	time computation CN P	(3.7)
	gain experiment	=	time experiment method	-	time experiment CN P
		=	gain traveling	+	gain computation	(3.8)

https://www.i-scoop.eu/industry-4-0/

https://www.bls.gov/iag/tgs/iag493.htm

https://www.ls2n.fr

https://e-cobot.com

https://e-cobot.com/husky-robot-mobile-intelligent-2/

https://gazebosim.org

https://youtu.be/kS7HrOHnbho

https://youtu.be/LYJWcOHd1L8 https://youtu.be/E1OdhVi11DU

Conference proceeding

Daravuth Koung, Isabelle Fantoni, Olivier Kermorgant, and Lamia Belouaer, "Consensusbased formation control and obstacle avoidance for nonholonomic multi-robot system", International Conf. on Control, Automation, Robotics and Vision (ICARCV), Dec., 2020.

Poster session

Daravuth Koung, Isabelle Fantoni, Olivier Kermorgant, and Lamia Belouaer, "Cooperative navigation of mobile robots fleet", Journées Francophones sur la Planification, la Décision et l'Apprentissage pour la conduite de systèmes (JFPDA), July, 2019. S2: Figure 2.28 shows the navigation scenario of the experiment, in which a plate with a payload of 20kg is added to the system. The team has to reach a target point and come back while trying not to collide with the two un-mapped obstacles. The formation shape is kept during navigation, as demonstrated by the plot of the inter-distance errors in Figure 2.29a. Even though the self-localization, as well as the velocity tracking low-level control of each robot, are not accurately perfect, the maximum error for the inter-distances is just about±0.06m, evidenced in Figure 2.29b. The fleet starts at (2.5m, -2.0m, 0 o ), and moves to a goal pose of (12m, -4.0m, 90 o ). Once it reaches the desired pose at around t = 80s, it has to return to its initial pose. The trajectories of each robot as well as the formation's center can be seen in Figure 2.29d; the blue square indicates the formation shape at the start and end of the navigation,

Tabu Search approach

The second algorithm that is tested is the Tabu Search algorithm. The flowchart of this algorithm is presented in Figure 3.3. This is a Local Search method [START_REF] Laporte | Chapter 4: Heuristics for the Vehicle Routing Problem[END_REF], which starts with a set of solution as initialization. Then, at each iteration of the algorithm, it looks for the neighborhood of this solution. A neighbor of a solution is the solution itself with two elements inverted. The process of finding the neighborhood is described in the flowchart of Figure 3.2. Once the neighborhood is found, the best neighbor is selected as being the new solution. The best neighbor is the one with the lowest cost, so the one that minimizes the most the total traveling time of the robots. Because this process can lead to cycling on a local minimum if the previous solution is the best neighbor of the new the efficiency of the TS algorithm, we start with a set of initial solutions obtained using CNP. Thus, the solution is close to optimal already.

CONCLUSION

Despite the latest advancements and research on formation techniques and the fact that the multi-robot system is more flexible and efficient in terms of huge load transportation tasks, we are yet to see an actual implementation of such systems in real-world environments. This thesis's objective is to bridge this gap between laboratory research and the industry. Three research axes have been conducted:

-Consensus-based formation control -Optimization-based formation control -Determination of task allocation approach for warehouse application Regarding the first pole of research, it is shown that a fleet of nonholonomic robots is able to safely navigate the environment without breaking the formation. Consensus-based formation control is a distributed controller, which opens up the possibility of having a huge number of robots in a fleet. On the other hand, due to the nature of consensus, this approach can not ensure precisely the desired formation as the controller itself is made up of several weighted components (formation, navigation, obstacle avoidance, etc.), which may dominate each other in various scenarios resulting in undesired behaviors.

The optimization-based controller is proposed to solve the mentioned issue. Each control component is defined as a task with a different priority to be respected by the solver. With task priority introduced, a two-level optimization problem is formed and can be solved using hierarchical quadratic programming. This approach shows better performance in terms of being able to keep the formation. In addition to being able to achieve precisely the formation shape and desired inter-distance between robots, we can also control the heading angle of the whole fleet, which improves the navigation behavior.

Simulations and experiments on Huskys provided by E-COBOT are conducted for the two proposed formation algorithms. In the case of the optimization-based controller, we have shown that a sophisticated connection mechanism between the load and the robots is not required. It is because of the desired inter-distances that are well-kept throughout the navigation.

The third pole of this work shows the interest in using the Contract Net Protocol over the Tabu Search for task allocation problems in a simulated warehouse environment with