This article proposes a reactive impedance surface (RIS)-loaded, inductively fed full-wave dipole (FWD) UHF RFID tag designed for metal-mounted and concrete-embedded prefabricated component traceability. The tag employs a small copper loop for inductive feeding, effectively matching both the high impedance of the FWD and the large capacitive component of the RFID integrated circuit across the UHF band. Metal tolerance is achieved by employing the RIS, which can compensate the parasitic capacitance and reduce strong interaction between the antenna and the metal plane. Experimental results demonstrate that the proposed single tag achieves a measured bandwidth (|S${_{{11}}} {\unicode {0x007C}}$$\leq -$10 dB) of 700 MHz (76.5%) and a maximal read distance of 22.62 m. When mounted on metal with the RIS, the bandwidth reduces to 632 MHz (69%), and the maximum reading distance decreases to 20.19 m. Additionally, when embedded in concrete, the antenna loading RIS and metal plane maintains a maximum read distance of 4.63 m, demonstrating robust performance in construction material environments.

We present distributed algorithms for multirobot task assignment where the tasks have to be completed within given deadlines. Each robot has a limited battery life and thus there is an upper limit on the amount of time that it has to perform tasks. Performing each task requires certain amount of time (called the task duration) and each robot can have different payoffs for the tasks. Our problem is to assign the tasks to the robots such that the total payoff is maximized while respecting the task deadline constraints and the robot's battery life constraints. Our problem is NP-hard since a special case of our problem is the classical generalized assignment problem (which is NP-hard). There are no known algorithms (distributed or centralized) for this problem with provably good guarantees of performance. We present a distributed algorithm for solving this problem and prove that our algorithm has an approximation ratio of 2. For the special case of constant task duration we present a distributed algorithm that is provably almost optimal. Our distributed algorithms are polynomial in the number of robots and the number of tasks. We also present simulation results to depict the performance of our algorithms. Note to Practitioners-In this paper, we present provably good multirobot task assignment algorithms, while considering practical constraints like task deadlines and limited battery life of robots. Such constraints are relevant in many applications including parts movement by robots in manufacturing, delivery of goods by unmanned vehicles, and search and rescue operations. Our solution is applicable to a group of heterogeneous robots with different suitability (i.e., payoffs) for different tasks. Our distributed approach is independent of the underlying robot communication network topology, and thus can be applied to a wide range of robot network deployments. Finally, our approach is easy to implement, has low communication requirements, and it is scalable, since its running time is linear in the number of robots and tasks.

In this paper, we present provably-good distributed task assignment algorithms for a heterogeneous multi-robot system, in which the tasks form disjoint groups and there are constraints on the number of tasks a robot can do (both within the overall mission and within each task group). Each robot obtains a payoff (or incurs a cost) for each task and the overall objective for task allocation is to maximize (minimize) the total payoff (cost) of the robots. In general, existing algorithms for task allocation either assume that tasks are independent or do not provide performance guarantee for the situation, in which task constraints exist. We present a distributed algorithm to provide an almost optimal solution for our problem. The key aspect of our distributed algorithm is that the overall objective is (almost) maximized by each robot maximizing its own objective iteratively (using a modified payoff function based on an auxiliary variable, called price of a task). Our distributed algorithm is polynomial in the number of tasks, as well as the number of robots.

Robotic swarms are distributed systems whose members interact via local control laws to achieve different behaviors. Practical missions may require a combination of different swarm behaviors, where these behavioral combinations are not known a priori but could arise dynamically due to changes in mission goals. Therefore, human interaction with the swarm (HIS) is needed. In this paper, we introduce, formally define and characterize a novel concept, Neglect Benevolence, that captures the idea that it may be beneficial for system performance if the human operator, after giving a command, waits for some time before giving a subsequent command to the swarm. This raises the important question of the existence and means of calculation of the optimal time for the operator to give input to the swarm in order to optimize swarm behavior. Human operators are limited in their ability to estimate the best time to give input to the swarm. Therefore, automated aids that calculate the optimal input time could help the human operator achieve the best system performance. Our contributions are as follows. First, we formally define the new notion of Neglect Benevolence. Second, we prove the existence of Neglect Benevolence for a class of linear dynamical systems. Third, we provide an analytic characterization and an algorithm for calculating the optimal input time. Fourth, we apply the analysis to the human control of swarm configuration.

In this paper, we present both centralized and distributed algorithms for aligning coordinate frames in multi-robot systems based on inter-robot relative position measurements. Robot orientations are not measured, but are computed by our algorithms. Our algorithms are robust to measurement error and are useful in applications where a group of robots need to establish a common coordinate frame based on relative sensing information. The problem of establishing a common coordinate frame is formulated in a least squares error framework minimizing the total inconsistency of the measurements. We assume that robots that can sense each other can also communicate with each other. In this paper, our key contribution is a novel asynchronous distributed algorithm for multi-robot coordinate frame alignment that does not make any assumptions about the sensor noise model. After minimizing the least squares error (LSE) objective for coordinate frame alignment of two robots, we develop a novel algorithm that out-performs state-of-the-art centralized optimization algorithms for minimizing the LSE objective. Furthermore, we prove that for multi-robot systems (a) with redundant noiseless relative sensing information, we will achieve the globally optimal solution (this is non-trivial because the LSE objective is non-convex for our problem), (b) with noisy information but no redundant sensing (e.g. sensing graph has a tree topology), our algorithm will optimally minimize the LSE objective. We also present preliminary results of the real-world performance of our algorithm on TurtleBots equipped with Kinect sensors.

In this paper, we present provably-good algorithms for multi-robot task assignment, where each task has to be completed within its deadline. Each robot has a upper limit on the maximum number of tasks that it can perform due to its limited battery life, and each task takes the same amount of time to complete. Each robot has a different payoff (or cost) for the tasks and the objective is to assign the tasks to the robots such that the total payoff (cost) is maximized (minimized) while respecting the task deadline constraints. This problem is an extension of a special generalized assignment problem (where each task consumes the same time resource and must be finished), with additional deadline constraints for the time resource assignment. We show that the problem can be reduced to a problem of assigning tasks to robots, where the tasks are organized in overlapping sets, and each robot has a limit on the number of tasks it can perform from each set, which is a variant of multi-robot assignment problem with set precedence constraint (SPC-MAP) discussed in [1].We present a distributed auction-based algorithm for this problem and prove that the solution is almost-optimal. We also present simulation results to depict the performance of our algorithm.

We present a provably-good distributed algorithm for generalized task assignment problem in the context of multirobot systems, where robots cooperate to complete a set of given tasks. In multi-robot generalized assignment problem (MR-GAP), each robot has its own resource constraint (e.g., energy constraint), and needs to consume a certain amount of resource to obtain a payoff for each task. The objective is to find a maximum payoff assignment of tasks to robots such that each task is assigned to at most one robot while respecting robots' resource constraints. MR-GAP is a NP-hard problem. It is an extension of multi-robot linear assignment problem since different robots can use different amount of resource for doing a task (due to the heterogeneity of robots and tasks). We first present an auction-based iterative algorithm for MR-GAP assuming the presence of a shared memory (or centralized auctioneer), where each robot uses a knapsack algorithm as a subroutine to iteratively maximize its own objective (using a modified payoff function based on an auxiliary variable, called price of a task). Our iterative algorithm can be viewed as (an approximation of) best response assignment update rule of each robot to the assignment of other robots at that iteration. We prove that our algorithm converges to an assignment (approximately) at equilibrium under the assignment update rule, with an approximation ratio of 1+α (where α is the approximation ratio for the Knapsack problem). We also combine our algorithm with a message passing mechanism to remove the requirement of a shared memory and make our algorithm totally distributed assuming the robots' communication network is connected. Finally, we present simulation results to depict our algorithm's performance.

We study an online task assignment problem for multi-robot systems where robots can do multiple tasks during their mission and the tasks arrive dynamically in groups. Each robot can do at most one task from a group and the total number of tasks a robot can do is bounded by its limited battery life. There is a payoff for assigning each robot to a task and the objective is to maximize the total payoff. A special case, where each group has one task and each robot can do one task is the online maximum weighted bipartite matching problem (MWBMP). For online MWBMP, it is known that, under some assumptions on the payoffs, a greedy algorithm has a competitive ratio of 1 over 3. Our key result is to prove that for the general problem, under the same assumptions on the payoff as in MWBMP and an assumption on the number of tasks arising in each group, a repeated auction algorithm, where each group of tasks is (near) optimally allocated to the available group of robots has a guaranteed competitive ratio. We also prove that (a) without the assumptions on the payoffs, it is impossible to design an algorithm with any performance guarantee and (b) without the assumption on the task profile, the algorithms that can guarantee a feasible allocation (if one exists) have arbitrarily bad performance in the worst case. Additionally, we present simulation results depicting the average case performance of the repeated greedy auction algorithm.

In this paper, we present task allocation (assignment) algorithms for a multi-robot system where the tasks are divided into disjoint groups and there are precedence constraints between the task groups. Existing auction-based algorithms assume the task independence and hence can not be used directly to solve the class of multi-robot task assignment problems that we consider. In our model, each robot can do a fixed number of tasks and obtains a benefit (or incurs a cost) for each task. The tasks are divided into groups and each robot can do only one task from each group. These constraints arise when the robots have to do a set of tasks that have precedence constraints and each task takes the same time to be completed. We extend the auction algorithm to provide an almost optimal solution to the task assignment problem with set precedence constraints (the theoretical guarantees are the same as that of the original auction algorithm for unconstrained tasks). In other words, we guarantee that we will get a solution within a factor of O(nte) of the optimal solution, where ntis the total number of tasks and ε is a parameter that we choose. We first present our algorithm using a shared memory model and then indicate how consensus algorithms can be used to make the algorithm totally distributed.

Digital microfluidic systems (DMFS) are an emerging class of lab-on-a-chip systems that manipulate individual droplets of chemicals on a planar array of electrodes. The biochemical analyses are performed by repeatedly moving, mixing, and splitting droplets on the electrodes. Mixers and storage units, composed of electrodes, are two important functional resources. Mixers perform droplet mixing and splitting operations, while storage units store droplets that have been produced for subsequent mixings. In this paper, we focus on minimizing the completion time of biochemical analyses by exploiting the binary tree representation of analyses to schedule mixing operations. Using pipelining, we overlap mixing operations with input and transportation operations. We find the lower bound of the mixing completion time based on the tree structure of input analyses, and calculate the minimum number of mixersMlbrequired to achieve the lower bound. We present a scheduling algorithm for the case with a specified number of mixersM, and prove it is optimal to minimize the mixing completion time. We also analyze resource constraint issues for two extreme cases. For the case with just one mixer, we prove that all schedules that keep the mixer busy at all times result in the same mixing completion time and then design algorithms for scheduling and to minimize the number of storage units. For the case with zero storage units, we find the minimum number of mixers required. We extend our analyses and algorithms assuming identical mixing durations to the case of different mixing durations. Finally, we illustrate the benefits of our scheduling methods on an example of DNA polymerase chain reaction (PCR) analysis.

Digital microfluidic systems (DMFS) are an emerging class of lab-on-a-chip systems that manipulate individual droplets of chemicals on a planar array of electrodes. The biochemical analyses are performed by repeatedly moving, mixing, and splitting droplets on the electrodes. In this paper, we focus on minimizing the completion time of biochemical analyses by exploiting the parallelism among the operations. We consider a binary tree representation of chemical analyses to schedule operations. Using pipelining, we overlap mixing operations with input and transportation operations. We find the lower bound of the mixing completion time according to the tree structure of given reactions, and calculate the minimal number of mixers S required to achieve the lower bound. We present a scheduling algorithm for the case with a specified number of mixers no more than S, and prove it is optimal to minimize the mixing completion time. We also analyze resource constraint issues for two extreme cases. For the case with one mixer, we prove that all schedules result in the same mixing completion time as long as the mixer is kept busy at all times and then design a scheduling algorithm to minimize the number of storage units. For the case with zero storage units, we find the minimum number of mixers required. Finally, we demonstrate the benefits of our scheduling methods on an example of DNA polymerase chain reaction (PCR) analysis.