Search

In a round-trip carsharing system, stations must be located in such a way that allow for maximum user coverage with the least walking distance as well as offer certain degrees of flexibility for returning. Therefore, a balance must be stricken between these factors. Providing a satisfactory system can be translated into an optimization problem and belongs to an NP-hard class. In this article, a novel optimization model for the round-trip carsharing fleet placement problem, called Fleet Placement Problem (FPP), is proposed. The optimization in this work is multiobjective and its NP-hard nature is proven. Three different optimization algorithms: PolySCIP (exact method), heuristics, and NSGA-II (metaheuristic) are investigated. This work adopts three real instances for the study, instead of their abstracts where they are most commonly used. They are two instance:, in the city of Luxembourg (smaller and larger) and a much larger instance in the city of Munich. Results from each algorithm are validated and compared with solution from human experts. Superiority of the proposed FPP model over the traditional methods is also demonstrated.

International audience; This paper presents an experimental platform and a simulation-based one for the implementation of a method enabling mobile anonymous robots self-localization. The proposed method, theoretically validated in a previous work, is based on the comparison between global information obtained through periodical aerial pictures and local information stemmed from odometry. The process analyzes robots' coordinates evolution between two consecutive pictures and compares these changes with odometric measures. On each picture, robots are anonymous and their identification is impossible without extra information. In this work, measures obtained with actual robots on the experimental platform are compared with the ones obtained on the simulation-based platform reproducing experimental conditions. We show that success rates, defined as the percentage of time robots successfully localize themselves, obtained on both platforms are qualitatively similar while quantitatively different in regard with algorithm performances. Sources responsible for this gap are identified and analyzed. It leads to the conclusion that, in the context of our study, using a simulation-based platform is a valid alternative to actual robots experiments.

International audience; When a disaster occurs, during a long period of time people suffer to have no means to communicate with their relatives. The presented work aims at proposing a solution composed of a ground station located nearby the damaged area coupled with a swarm of drones. The ground station plays the role of a gateway between cellular networks, that are still up but out of reach of people, with drones that carry messages from and to people located in the disastered region. We analyze the possibility of deploying drones with fixed positions and a more flexible solution allowing drones to move but at the cost of intermittent communications, allowing only sms-like messages. We show that using the same number of drones, allowing drones to move improves dramatically the coverage of people with respect to a FANET in which drones stay at a fixed position. We also show that even for a very restricted number of drones, for reasonable communication ranges, almost all the people benefit from an important average connected time.

International audience; There are numerous advantages of flying in group over using single robot in mission execution. However this implies solving a crucial issue: the coordination between drones. Moreover, according to the targeted application, it may be necessary or desirable that drones fly following a given geometric shape (line, diamond, etc.), a problem known as formation control. Building and maintaining a spatial geometric shape while evolving within the environment usually requires extensive communications between the robots for coordinating their movements. In this work we focus on the use of an Image-Based Visual Servoing (IBVS) technique for building and maintaining a Leader-Follower (LF) configuration of multi aerial vehicles (UAVs) without communication. While most IBVS techniques either require rigor camera calibration or can not regulate the error according to the three robot axes, our approach avoids the calibration phase by relying on image moments features to provide a vision-based predictive compensation method. The follower robot's solution works in GNSS-denied conditions and can run using only on-board sensors. The method is validated through simulations for a group of three quadrotors.

International audience; The main contribution of this paper is the design of a decentralized and tuning-less high level controller able to maintain without tracking errors a Leader-Follower (LF) configuration in case of lack or degraded communications (latencies, loss…) between the leader and followers UAVs. The high level controller only requires simple tunings and rests on a predictive filtering algorithm and a first order dynamic model to recover an estimation of the leader UAV velocities and avoid the tracking errors.

This paper presents a decentralized method for aligning three robots without communication and without explicit localization. Each robot is assumed to be equipped with an omnidirectional camera and is assumed to be able to detect the two other robots in the images produced by its own camera. Each robot decides of its own movements based on the continuous measures of angles between itself and the others. We present both the algorithm that performs such a task and its theoretical analysis. We prove the correctness of the algorithm when the robots are reduced to points, when collisions are not considered and when the initial formation is not an equilateral triangle. When collisions are considered, the probability for the algorithm to be successful is greater than $1 - \displaystyle \frac {1}{36}$. We then present some simulation for which a security distance $d_{\sec }$ has been introduced. During the execution of the algorithm by each robot, if the distance between any two robots is lower than this security distance we suppose that a collision is likely to occur and consider that the Algorithm has failed. Simulation results report that the larger $d_{\sec }$, the bigger the percentage of failures. However runs are always successful when $d_{\sec } = 0$ which suggests that the theoretical bound is not tight and could be improved. In addition, simulations reveal that the main source of failures was not the one expected by the theoretical analysis.

International audience; The goal of Mobile Wireless Sensor Networks (M-WSN) is to sense a specific environment. A commonly considered objective is to organize the work of the sensors such that they monitor the environment as long as possible and cover a surface as large as possible. While most of the time this problem is formulated as a multi-objective optimization problem we present a new decentralized approach for building a connected dominating set (CDS) coupled with attractive and repulsive forces for the movement of sensors in order to maintain the network connectivity. The approach is implemented as a hybrid decentralized algorithm: DACYCLEM (Decentralized Algorithm under Connectivity constraint with mobilitY for Coverage and LifEtime Maximiza-tion). The lifetime and the coverage achieved by our approach are the results of the local interactions between the sensors and were not obtained by the application of a direct optimization method. We also introduce a new metric , the speed of coverage, to evaluate the balance between coverage and lifetime. Finally, our simulation results show that one single parameter of DACYCLEM is responsible for the balancing between coverage and lifetime.

International audience; This paper presents three methods for anonymous mobile robots localization within a global frame. An aerial camera takes, at regular time intervals, pictures of the area in which robots are moving. The camera determines the coordinates of each robot. Each robot receives the whole set of coordinates extracted from each picture. Mobile Robots are all identical, they do not have any identifier and they can neither communicate with each other nor they can detect themselves. The first localization method is based on the analysis of the angular variation between two images. The second method relies on the analysis of the distances stemmed from three successive pictures. The last one determines if there exists an orientation allowing a specific robot to travel the path between two successive positions. A simulation plateform using augmented reality and the multi-robot software Player-Stage are presented. This plateform is used for validating the different localization methods. Tests and results are presented and compared.

International audience; Monitoring some sites using a wireless sensor network (WSN) may be hampered by the di culty of recharging or renewing the batteries of the sensing devices. Mechanisms aiming at improving the energy usage at any moment while ful lling the application requirements are thus key for maximizing the lifetime of such networks. Among the di erent methods for achieving such a goal, we focus on energy management methods based on duty-cycling allowing the sensors to switch between two modes: a high-energy mode (active) and a low- energy mode (sleep). In this paper we propose two new sched- uling heuristics for addressing the problem of maximizing the lifetime of a WSN under the constraint of coverage of a subset of xed targets. The rst one is a stochastic greedy algorithm and the second one is based on applying Simulated Annealing (SA). Both heuristics use a speci c knowledge about the problem. Experimental results show that while both algorithms perform well, greedy algorithm is preferable for small and medium sizes networks, and SA algorithm has competitive advantages for larger networks.

Drones (aerial, terrestrial, marine, underwater, etc.) are more and more widely used in both civilian and military scenario. Still, they remain complex systems for which training, operation preparation and execution of effective operations require adapted tools and support. In this paper we propose such a tool, that we call Thunderbird, based on a shadow drone that is used to control and to get feedback form a drone on an effective field of operation. In this position paper we detail a number of issues that we have identified in the design of such a tool and we describe additional problems that arise when considering not only a single drone but a swarm of possibly heterogeneous drones. We also suggest some possible ways to cope with the identified issues. We eventually present a first prototype/proof of concept that we have developed.

International audience; This paper investigates a self-organized critical approach for dynamically load-balancing computational workloads. The proposed model is based on the Bak-Tang-Wiesenfeld sandpile: a cellular automaton that works in a critical regime at the edge of chaos. In analogy to grains of sand, tasks arrive and pile up on the different processing elements or sites of the system. When a pile exceeds a certain threshold, it collapses and initiates an avalanche of migrating tasks, i.e. producing load-balancing. We show that the frequency of such avalanches is in power-law relation with their sizes, a scale-invariant fingerprint of self-organized criticality that emerges without any tuning of parameters. Such an emergent pattern has organic properties such as the self-organization of tasks into resources or the self-optimization of the computing performance. The conducted experimentation also reveals that the system has a critical attractor in the point in which the arrival rate of tasks equals the processing power of the system. Taking advantage of this fact, we hypothesize that the processing elements can be turned on and off depending on the state of the workload as to maximize the utilization of resources. An interesting side effect is that the overall energy consumption of the system is minimized without compromising the quality of service.

In this paper we consider Maximal Lifetime Coverage Problem in Wireless Sensor Networks which is formulated as a scheduling problem related to activity of sensors equipped at battery units and monitoring a two-dimensional space in time. The problem is known as an NP-hard and to solve it we propose two heuristics which use specific knowledge about the problem. The first one is proposed by us stochastic greedy algorithm and the second one is metaheuristic known as Simulated Annealing. The performance of both algorithms is verified by a number of numerical experiments. Comparison of the results show that while both algorithms provide results of similar quality, but greedy algorithm is slightly better in the sense of computational time complexity.

Control of a set of sensors disseminated in the environment to monitor activity is a subject of the presented research. Due to redundancy in the areas covered by sensor monitoring ranges a satisfying level of coverage can be obtained even if not all the sensors are on. Sleeping sensors save their energy, thus, one can propose schedules defining activity for each of sensors over time which offer a satisfying level of coverage for a period of time longer than a lifetime of a single sensor. A new heuristic algorithm is proposed which searches for such schedules maximizing the lifetime of the sensor network under a coverage constraint. The algorithm is experimentally tested on a set of test cases and effectiveness of its components is presented and statistically verified.

We present in this paper a novel warehouse inventory scheme. The main purpose of this work is to make the inventory process completely autonomous. To this end, an Unmanned Ground Vehicle (UGV) and an Unmanned Aerial Vehicle (UAV) work cooperatively. The UGV is used as the carrying platform, and considered as a ground reference for the indoor flight of the UAV. While the UAV is used as the mobile scanner. The UGV navigates among rows of racks carrying the UAV. At each rack to be scanned, the UGV stops, and the UAV takes off to fly vertically scanning goods in that rack. Once the UAV at the top, the UGV moves to the next rack, and since the UAV takes the UGV as the ground reference, it will follow it autonomously, this results in placing the UAV at the top of the second rack, and scanning goods from top to bottom starts. the process is repeated until the row of racks is fully scanned. The UAV then lands on the UGV, and recharge its batteries while the UGV moves to the next row of racks. We present in this paper the proposed architecture, as well as the first experimental results of the proposed scheme

International audience; In this paper we study differences between contiguous and non-contiguous parallel task schedules. Parallel tasks can be executed on more than one processor simultaneously. In the contiguous schedules, indices of the processors assigned to a task must be a sequence of consecutive numbers. In the non-contiguous schedules, processor indices may be arbitrary. Optimum non-preemptive schedules are considered. Given a parallel task instance, the optimum contiguous and non-contiguous schedules can be of different lengths. We analyze minimal instances where such a difference may arise, provide bounds on the difference of the two schedules lengths, and prove that deciding whether the difference in schedule length exists is NP-complete.

International audience; — We present in this paper a decentralized multi-robot (aerial and ground) cooperation scheme for objects transportation. A team of ground mobile robots guided by a drone and a human operator moves in a coordinated way keeping a predefined formation in order to carry objects (tools, gas masks,...) in unsafe industrial areas. One ground mobile robot (leader) navigates among obstacles thanks to the waypoints provided by the drone and the human operator. The other ground mobile robots (followers) use a predictive vision based target tracking controller to keep a certain distance and bearing to the leader.

Open access: https://www.sciencedirect.com/science/article/pii/S1571066106001010; International audience; Mobile Ad hoc NETworks (MANETs) are dynamic networks populated by mobile stations. Stations in MANETs are usually laptops, PDAs or mobile phones. These devices feature Bluetooth and/or IEEE 802.11 (WiFi) network interfaces and communicate in a decentralized manner. Mobility is a key feature of MANETs. Because of their high cost and their lack of flexibility of such networks, experimentation is mostly achievable through simulation. Numerous tools exist for MANETs simulation, including ns-2 and GloMoSim which are the two most popular ones. This paper provides a State of the Art of MANETs simulators and associated simulation techniques. First it gives an overview of the domain. Then it provides a map of the main characteristics that MANETs simulation tools should feature and the current support of these. Finally, a description for each simulator is provided, including an explanation of what make them appealing solutions.

In this paper we study the scheduling of multiple divisible loads on a star network of processors. We show that this problem is computationally hard. Special cases solvable in polynomial time are identified.

This paper is concerned with scheduling when the data are not fully known before the execution. In that case computing a complete schedule off-line with estimated data may lead to poor perfor- mances. Some flexibility must be added to the scheduling process. We propose to start from a partial schedule and to postpone the complete scheduling until execution, thus introducing what we call a stabilization scheme. This is applied to the m machine problem with communication delays: in our model an estimation of the delay is known at compile time; but disturbances due to network contention, link failures, ... may occur at execution time. Hence the processor assignment and a partial sequencing on each processor are determined off-line. Some theoretical results for tree-like precedence constraints and an experimental study show the interest of this approach compared with fully on-line sched- uling.

This paper studies a self-organized criticality model called sandpile for dynamically load-balancing tasks arriving in the form of Bag-of-Tasks in large-scale decentralized system. The sandpile is designed as a decentralized agent system characterizing a cellular automaton, which works in a critical state at the edge of chaos. Depending on the state of the cellular automaton, different responses may occur when a new task is assigned to a resource: it may change nothing or generate avalanches that reconfigure the state of the system. The abundance of such avalanches is in power-law relation with their sizes, a scale-invariant behavior that emerges without requiring tuning or control parameters. That means that large--catastrophic--avalanches are very rare but small ones occur very often. Such emergent pattern can be efficiently adapted for non-clairvoyant scheduling, where tasks are load balanced in computing resources trying to maximize the performance but without assuming any knowledge on the tasks features. The algorithm design is experimentally validated showing that the sandpile is able to find near-optimal schedules by reacting differently to different conditions of workloads and architectures.

In this paper, we present a new linear time algorithm for scheduling UECT (Unit Execution and Communication Time) trees on two identical processors. The chosen criterion is the makespan. The used strategy is based on clustering of tasks. We show that this algorithm builds optimal schedules. Some extensions are discussed for non UECT tasks.

In this paper, a problem of scheduling an arbitrarily divisible task is considered. Taking into account both communication delays and computation time we propose a scheduling method which minimizes total execution time. We focus on two dimensional processor networks assuming a circuit-switching routing mechanism. The scheduling method uses a scattering scheme proposed in Peters and Syska (IEEE Trans. Parallel Distributed Systems 7(3) (1996) 246–255) to distribute parts of the task to processors in a minimum time. We show how to model and solve this problem with a set of algebraic equations. A solution of the latter allows one to analyze the performance of the network depending on various actual parameters of the task and the parallel machine. Though the method is defined for a particular architecture and scattering scheme it can be generalized to analyze other architectures of parallel computer systems.

The aim of this paper is to present and analyze models for designing parallel programs. In the context of some extensions of the most popular execution models (precedence graphs, dataflow, PRAM), we describe scheduling techniques which take into account the communication delays. We illustrate all these models by two families of representative precedence graphs, namely, grids and complete trees.

We address the problem of building and maintaining distributed spanning trees in highly dynamic networks, in which topological events can occur at any time and any rate, and no stable periods can be assumed. In these harsh environments, we strive to preserve some properties such as cycle-freeness or the existence of a root in each tree, in order to make it possible to keep using the trees uninterruptedly (to a possible extent). Our algorithm operates at a coarse-grain level, using atomic pairwise interactions in a way akin to recent population protocol models. The algorithm relies on a perpetual alternation of \emph{topology-induced splittings} and \emph{computation-induced mergings} of a forest of spanning trees. Each tree in the forest hosts exactly one token (also called root) that performs a random walk {\em inside} the tree, switching parent-child relationships as it crosses edges. When two tokens are located on both sides of a same edge, their trees are merged upon this edge and one token disappears. Whenever an edge that belongs to a tree disappears, its child endpoint regenerates a new token instantly. The main features of this approach is that both \emph{merging} and \emph{splitting} are purely localized phenomenons. In this paper, we present and motivate the algorithm, and we prove its correctness in arbitrary dynamic networks. Then we discuss several implementation choices around this general principle. Preliminary results regarding its analysis are also discussed, in particular an analytical expression of the expected merging time for two given trees in a static context., Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks, Poland (2013)

This paper is devoted to the study of tree-scheduling problems within the execution model described by Anderson, Beame and Ruzzo. We first prove the NP-completeness of the problem of minimizing the overhead for scheduling trees on m processors, and then we propose an algorithm that provides optimal schedules when complete trees are considered.

We consider the problem of finding and maintaining communication paths in wireless mobile ad hoc networks (MANET). We consider this problem as a bi-objective problem when trying to minimize both the length of the constructed paths and the number link reconnections. We propose two centralized algorithms that help analyse the problem from a dynamic graph point of view. These algorithms give lower bounds for our proposed decentralized ant-based algorithm that constructs and maintains such paths in a MANET.

International audience; What is the impact of obstacles on the graphs of connections between stations in Mobile Ad hoc Networks? In order to answer, at least partially, this question, the first step is to define both an environment with obstacles and a mobility model for the stations in such an environment. The present paper focuses on a new way of considering the mobility within environments with obstacles, while keeping the core ideas of the well-known Random WayPoint mobility model (a.k.a RWP). Based on a mesh-partitioning of the space, we propose a new model called RSP-O-G for which we compute the spatial distribution of stations and analyse how the presence of obstacles impacts this distribution compared to the distribution when no obstacles are present. Coupled with a simple model of radio propagation, and according to the density of stations in the environment, we study the mean degree of the connection graphs corresponding to such mobile ad hoc networks.

International audience; Tree-based backbone establishment and maintenance in Mobile ad hoc Delay Tolerant Networks is often operated throught the use of traversing tokens. A study and framework are proposed here for various token traversal strategies on tree-based backbones. The proposed strategies execute in a distributed and purely decentralized manner, and require only 1-hop knowledge. Aiming at providing the highest robustness and quality of services, these token-traversal strategies are studied in particular with an algorithm for merging and maintaining the different trees based on the quality of the nodes. For the robustness aspect, the use of a trust-based evaluation framework is assumed and the weights of the different nodes are based on their quality of cooperation. Three cost functions are implemented in order to evaluate the trust based framework proposed, including another function for evaluating tree-convergence time. Results and comparison charts are provided to illustrate the trade-off between the various strategies in terms of performances, cost (memory and communication) and robustness.

This paper presents three distributed and decentralized strategies used for token traversal in spanning forest over Mobile Ad Hoc Delay Tolerant Networks. Such networks are characterized by behaviors like disappearance of mobile devices, connection disruptions, network partitioning, etc. Techniques based on tree topologies are well known for increasing the efficiency of network protocols and/or applications, such as Dynamicity Aware - Graph Relabeling System (DA-GRS). One of the main features of these tree based topologies is the existence of a token traversing in every tree. The use of tokens enables the creation and maintenance of spanning trees in dynamic environments. Subsequently, managing tree-based backbones relies heavily on the token behavior. An efficient and optimal token traversal can highly impact the design of the tree and its usage. In this article, we present a comparison of three distributed and decentralized techniques available for token management, which are Randomness, TABU and Depth First Search.

International audience; Multiple sequence alignment is a key process in today's biology, and finding a relevant alignment of several sequences is much more challenging than just optimizing some improbable evaluation functions. Our approach for addressing multiple sequence alignment focuses on the building of structures in a new graph model: the factor graph model. This model relies on block-based formulation of the original problem, formulation that seems to be one of the most suitable ways for capturing evolutionary aspects of alignment. The structures are implicitly built by a colony of ants laying down pheromones in the factor graphs, according to relations between blocks belonging to the different sequences.

The observation and modeling of natural Complex Systems (CSs) like the human nervous system, the evolution or the weather, allows the definition of special abilities and models reusable to solve other problems. For instance, Genetic Algorithms or Ant Colony Optimizations are inspired from natural CSs to solve optimization problems. This paper proposes the use of ant-based systems to solve various problems with a non assessing approach. This means that solutions to some problem are not evaluated. They appear as resultant structures from the activity of the system. Problems are modeled with graphs and such structures are observed directly on these graphs. Problems of Multiple Sequences Alignment and Natural Language Processing are addressed with this approach.

International audience; Large-scale individual-based simulations can benefit a lot from high performance computing environments. The benefit that can be hopped depends greatly on a good load distribution among the processing ressources together with the minimization of the communication overhead. However, minimizing both idle time and communication overhead requires the search for a trade-off. Inspired by complex systems, the approach described in this paper aims at minimizing the volume of data exchanged over the network between tasks of a distributed application, while balancing the load between available computing ressources. The method lies on the trail-laying trail-following paradigm used in algorithms based on artificial ants.

A distributed application may be considered as a set of interacting entities continuously evolving. Such application can be modeled as a graph with one-to-one mappings between vertices and entities and between edges and communications. Performances depend directly on a good load balancing of the entities between available computing devices and on the minimization of the impact of the communications between them. However, both objectives are contradictory and good performances are achieved if and only if a good tradeoff is found. Our method for finding such a tradeoff is new and based on colored ant colonies. Each computing resource is associated to one ant colony characterized by a color, allowing an implicit consideration of the load balancing constraint. Then, using colored pheromones, ants are just seeking for communicating structures. The method operates on graphs which structural and numerical parameters may change dynamically during the execution.

Motivation: A new heuristic algorithm for solving DNA sequencing by hybridization problem with positive and negative errors. Results: A heuristic algorithm providing better solutions than algorithms known from the literature based on tabu search method. Contact: blazewic@sol.put.poznan.pl * To whom correspondence should be addressed.

Topology management for mobile ad hoc networks is usually based on the notion of virtual backbones. We address the notion of quality of such backbones as a multi-objective problem addressing quality of the mobiles composing the backbone and of the connection links. We validate the approach using extensive simulation based on different mobility models and using backbones composed of spanning forests. We provide ways to address the global behaviour of the algorithms by fine-tuning the greedy local decision policy and compare it to the solution quality that could be achieved using global knowledge and metaheuristics.

This paper establishes the exact upper bound for Lawler's heuristic proving that its schedule of a UECT tree on m identical processors does not exceed an optimal solution by more than m/2 time units.