Author name cluster

Arnaud Labourel

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers

2 author rows

I&C Journal 2022 Journal Article

Distance labeling schemes for K4-free bridged graphs

Victor Chepoi
Arnaud Labourel
Sébastien Ratel

k-Approximate distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the k-approximation of the distance between any two vertices u and v can be determined efficiently by merely inspecting the labels of u and v, without using any other information. One of the important problems is finding natural classes of graphs admitting exact or approximate distance labeling schemes with labels of polylogarithmic size. In this paper, we describe a 4-approximate distance labeling scheme for the class of K 4 -free bridged graphs. This scheme uses labels of poly-logarithmic length O ( log ⁡ n 3 ) allowing a constant decoding time. Given the labels of two vertices u and v, the decoding function returns a value between the exact distance d G ( u, v ) and its quadruple 4 d G ( u, v ).

Details DOI

TCS Journal 2021 Journal Article

Collaborative delivery on a fixed path with homogeneous energy-constrained agents

Jérémie Chalopin
Shantanu Das
Yann Disser
Arnaud Labourel
Matúš Mihalák

We consider the problem of collectively delivering a package from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent starts from some vertex of the graph; it can move along the edges of the graph and can pick up the package from a vertex and drop it in another vertex during the course of its movement. However, each agent has limited energy budget allowing it to traverse a path of bounded length B; thus, multiple agents need to collaborate to move the package to its destination. Given the positions of the agents in the graph and their energy budgets, the problem of finding a feasible movement schedule is called the Collaborative Delivery problem and has been studied before. One of the open questions from previous results is what happens when the delivery must follow a fixed path given in advance. Although this special constraint reduces the search space for feasible solutions, the problem remains NP hard, as the general version of the problem. We consider the optimization version of the problem that asks for the optimal energy budget B per agent which allows for a feasible delivery schedule along a fixed path, given the initial positions of the agents. We provide polynomial time approximation algorithms for both directed and undirected graphs, and establish hardness of approximation for the directed case. Note that the fixed path version of collaborative delivery requires completely different techniques since a single agent may be used multiple times, unlike the general version of collaborative delivery studied before. We show that restricting each agent to a single pickup allows better approximations for fixed path collaborative delivery compared to the original problem. Finally, we provide a polynomial time algorithm for determining a feasible delivery strategy, if any exists, for a given budget B when the number of available agents is bounded by a constant.

Details DOI

TCS Journal 2020 Journal Article

Collaborative delivery with energy-constrained mobile robots

Andreas Bärtschi
Jérémie Chalopin
Shantanu Das
Yann Disser
Barbara Geissmann
Daniel Graf
Arnaud Labourel
Matúš Mihalák

We consider the problem of collectively delivering some package from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent has limited energy which constrains the distance it can move. Hence multiple agents need to collaborate to move the package, each agent handing over the package to the next agent to carry it forward. Given the positions of the agents in the graph and their respective budgets, the problem of finding a feasible movement schedule for the agents can be challenging. We consider two variants of the problem: in non-returning delivery, the agents can stop anywhere; whereas in returning delivery, each agent needs to return to its starting location, a variant which has not been studied before. We first provide a polynomial-time algorithm for returning delivery on trees, which is in contrast to the known (weak) NP-hardness of the non-returning version. In addition, we give resource-augmented algorithms for returning delivery in general graphs. Finally, we give tight lower bounds on the required resource augmentation for both variants of the problem. In this sense, our results close the gap left by previous research.

Details DOI

MFCS Conference 2019 Conference Paper

Distance Labeling Schemes for Cube-Free Median Graphs

Victor Chepoi
Arnaud Labourel
Sébastien Ratel

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently by merely inspecting the labels of u and v, without using any other information. One of the important problems is finding natural classes of graphs admitting distance labeling schemes with labels of polylogarithmic size. In this paper, we show that the class of cube-free median graphs on n nodes enjoys distance labeling scheme with labels of O(log^3 n) bits.

Details

TCS Journal 2019 Journal Article

Group search of the plane with faulty robots

Jurek Czyzowicz
Maxime Godon
Evangelos Kranakis
Arnaud Labourel

A collection of k mobile robots, initially placed at the origin of the plane, are searching for a stationary target. Each robot r i has a unit visibility range and can move no faster than its maximal speed v i, for i = 1, 2, .. ., k. The robots can communicate between themselves. We consider two communication models: wireless, in which a message sent by a robot can reach all other robots immediately, regardless of their positions, and face-to-face (F2F), in which robots can only exchange information when they are meeting. We assume that up to f robots, where f < k, may be unreliable. We consider two models of unreliability: (1) crash faults, in which we deal with an absence of some of the robots' capabilities (communication, perception, motion, etc.), and (2) byzantine faults, in which the robots may be malicious in that they may execute a wrong algorithm (e. g. , transmitting wrong information). The goal is to minimize the group search time, which is equal to the time of arrival to the target of the last reliable robot. This is expressed as a function of d, the distance from the origin to the target. Our proposed algorithms for crash faults are asymptotically optimal in d in both communication models. For byzantine faults, our algorithm is asymptotically optimal for the wireless model. In the F2F model, we propose two algorithms: the first one has a competitive ratio of 2, while the second algorithm works for k ≥ 2 f + 2 and is optimal when the robots speeds are all equal.

Details DOI

TCS Journal 2019 Journal Article

On asynchronous rendezvous in general graphs

Evangelos Bampas
Lélia Blin
Jurek Czyzowicz
David Ilcinkas
Arnaud Labourel
Maria Potop-Butucaru
Sébastien Tixeuil

A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced.

Details DOI

TCS Journal 2013 Journal Article

Tight bounds for black hole search with scattered agents in synchronous rings

Jérémie Chalopin
Shantanu Das
Arnaud Labourel
Euripides Markou

We study the problem of locating a particularly dangerous node, the so-called black hole in a synchronous anonymous ring network with mobile agents. A black hole is a harmful stationary process residing in a node of the network and destroying all mobile agents visiting that node without leaving any trace. Unlike most previous research on the black hole search problem which employed a co-located team of agents, we consider the more challenging scenario when the agents are identical and initially scattered within the network. Moreover, we solve the problem with agents that have constant-sized memory and carry a constant number of identical tokens, which can be placed at nodes of the network. In contrast, the only known solutions for the case of scattered agents searching for a black hole, use stronger models where the agents have non-constant memory, can write messages in whiteboards located at nodes or are allowed to mark both the edges and nodes of the network with tokens. This paper solves the problem for ring networks containing a single black hole. We are interested in the minimum resources (number of agents and tokens) necessary for locating all links incident to the black hole. We present deterministic algorithms for ring topologies and provide matching lower and upper bounds for the number of agents and the number of tokens required for deterministic solutions to the black hole search problem, in oriented or unoriented rings, using movable or unmovable tokens.

Details DOI

I&C Journal 2013 Journal Article

Worst-case optimal exploration of terrains with obstacles

Jurek Czyzowicz
David Ilcinkas
Arnaud Labourel
Andrzej Pelc

A mobile robot represented by a point moving in the plane has to explore an unknown flat terrain with impassable obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, when the robot situated at a point p of the terrain explores (sees) all points q of the terrain for which the segment pq belongs to the terrain, and the limited vision, when we require additionally that the distance between p and q is at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm, called its complexity, is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity O ( P + D k ), where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limited vision we show exploration algorithms with complexity O ( P + A + A k ), where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains (if one of the parameters A or k is known) or for c-fat terrains, where c is any constant (unknown to the robot) and no additional knowledge is assumed. (A terrain T with obstacles is c-fat if R / r ⩽ c, where R is the radius of the smallest disc containing T and r is the radius of the largest disc contained in T.) We also prove a matching lower bound Ω ( P + A + A k ) on the complexity of exploration for limited vision, even if the terrain is known to the robot.

Details DOI

TCS Journal 2011 Journal Article

Asynchronous deterministic rendezvous in bounded terrains

Jurek Czyzowicz
David Ilcinkas
Arnaud Labourel
Andrzej Pelc

Two mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Robots are modeled as points, and each of them is equipped with a compass. Compasses of robots may be incoherent. Robots construct their routes, but the actual walk of each robot is decided by the adversary that may, e. g. , speed up or slow down the robot. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both robots agree, or not, (3) robots have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the robots’ trajectories until they meet. For each scenario, we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight.

Details DOI

I&C Journal 2011 Journal Article

Optimality and competitiveness of exploring polygons by mobile robots

Jurek Czyzowicz
Arnaud Labourel
Andrzej Pelc

A mobile robot, represented by a point moving along a polygonal line in the plane, has to explore an unknown polygon and return to the starting point. The robot has a sensing area which can be a circle or a square centered at the robot. This area shifts while the robot moves inside the polygon, and at each point of its trajectory the robot “sees” (explores) all points for which the segment between the robot and the point is contained in the polygon and in the sensing area. We focus on two tasks: exploring the entire polygon and exploring only its boundary. We consider several scenarios: both shapes of the sensing area and the Manhattan and the Euclidean metrics. We focus on two quality benchmarks for exploration performance: optimality (the length of the trajectory of the robot is equal to that of the optimal robot knowing the polygon) and competitiveness (the length of the trajectory of the robot is at most a constant multiple of that of the optimal robot knowing the polygon). Most of our results concern rectilinear polygons. We show that optimal exploration is possible in only one scenario, that of exploring the boundary by a robot with square sensing area, starting at the boundary and using the Manhattan metric. For this case we give an optimal exploration algorithm, and in all other scenarios we prove impossibility of optimal exploration. For competitiveness the situation is more optimistic: we show a competitive exploration algorithm for rectilinear polygons whenever the sensing area is a square, for both tasks, regardless of the metric and of the starting point. Finally, we show a competitive exploration algorithm for arbitrary convex polygons, for both shapes of the sensing area, regardless of the metric and of the starting point.

Details DOI

SODA Conference 2010 Conference Paper

How to Meet Asynchronously (Almost) Everywhere

Jurek Czyzowicz
Arnaud Labourel
Andrzej Pelc

Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent in each segment of its route is continuous, does not leave it and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerful adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. While our algorithms work in a very general setting – agents can, indeed, meet almost everywhere – we show that none of the above few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as above: agents will eventually get at an arbitrarily small positive distance from each other.

Details