Autonomous robots can survey and monitor large environments. However, these robots often have limited compu-tational and power resources, making it crucial to develop an ef-ficient and adaptive informative path planning (IPP) algorithm. Such an algorithm must quickly adapt to environmental data to maximize the information collected while accommodating path constraints, such as distance budgets and boundary limitations. Current approaches to this problem often rely on maximizing mutual information using methods such as greedy algorithms, Bayesian optimization, and genetic algorithms. These methods can be slow and do not scale well to large or 3D environments. We present an adaptive IPP approach that is fully differentiable, significantly faster than previous methods, and scalable to 3D spaces. Our approach also supports continuous sensing robots, which collect data continuously along the entire path, by leveraging streaming sparse Gaussian processes. Benchmark results on two real-world datasets demonstrate that our approach yields solutions that are on par with or better than baseline methods while being up to two orders of magnitude faster. Additionally, we showcase our adaptive IPP approach in a 3D space using a system-on-chip embedded computer with minimal computational resources. Our code is available in the SGP- Tools Python library with a companion ROS 2 package for deployment on ArduPilot-based robots.

This paper addresses multi-robot informative path planning (IPP) for environmental monitoring. The problem involves determining informative regions in the environment that should be visited by robots to gather the most information about the environment. We propose an efficient sparse Gaussian process-based approach that uses gradient descent to optimize paths in continuous environments. Our approach efficiently scales to both spatially and spatio-temporally correlated environments. Moreover, our approach can simultaneously optimize the informative paths while accounting for routing constraints, such as a distance budget and limits on the robot’s velocity and acceleration. Our approach can be used for IPP with both discrete and continuous sensing robots, with point and non-point field-of-view sensing shapes, and for both single and multi-robot IPP. We demonstrate that the proposed approach is fast and accurate on real-world data.

The line coverage problem involves finding efficient routes for the coverage of linear features by one or more resource-constrained robots. Linear features model environments such as road networks, power lines, and oil and gas pipelines. Two modes of travel are defined for robots: servicing and deadheading. A robot services a feature if it performs task-specific actions, such as taking images, as it traverses the feature; otherwise, it is deadheading. Traversing the environment incurs costs (e.g., travel time) and resource demands (e.g., battery life). Servicing and deadheading can have different cost and demand functions, which can be direction dependent. The environment is modeled as a graph, and an integer linear program is provided. As the problem is NP-hard, we design a fast and efficient heuristic algorithm, Merge-Embed-Merge (MEM). Exploiting the constructive property of the MEM algorithm, algorithms for line coverage of large graphs with multiple depots are developed. Furthermore, turning costs and nonholonomic constraints are efficiently incorporated into the algorithm. The algorithms are benchmarked on 100 road networks and demonstrated in experiments with aerial robots.

This paper addresses the problem of robotic exploration of unknown indoor environments with deadlines. Indoor exploration using mobile robots has typically focused on exploring the entire environment without considering deadlines. The objective of the prioritized exploration in this paper is to rapidly compute the geometric layout of an initially unknown environment by exploring key regions of the environment and returning to the home location within a deadline. This prioritized exploration is useful for time-critical and dangerous environments where rapid robot exploration can provide vital information for subsequent operations. For example, firefighters, for whom time is of the essence, can utilize the map generated by this robotic exploration to navigate a building on fire. In our previous work, we showed that a priority-based greedy algorithm can outperform a cost-based greedy algorithm for exploration under deadlines. This paper models the prioritized exploration problem as an Orienteering Problem (OP) and a Profitable Tour Problem (PTP) in an attempt to generate exploration strategies that can explore a greater percentage of the environment in a given amount of time. The paper presents simulation results on multiple graph-based and Gazebo environments. We found that in many cases the priority-based greedy algorithm performs on par or better than the OP and PTP-based algorithms. We analyze the potential reasons for this counterintuitive result.

Abstract Line coverage is the task of servicing a given set of one‐dimensional features in an environment. It is important for the inspection of linear infrastructure such as road networks, power lines, and oil and gas pipelines. This paper addresses the single robot line coverage problem for aerial and ground robots by modeling it as an optimization problem on a graph. The problem belongs to the broad class of arc routing problems and is closely related to the rural postman problem (RPP) on asymmetric graphs. The paper presents an integer linear programming formulation with proofs of correctness. Using the minimum cost flow problem, we develop approximation algorithms with guarantees on the solution quality. These guarantees also improve the existing results for the asymmetric RPP. The main algorithm partitions the problem into three cases based on the structure of therequired graph, that is, the graph induced by the features that require servicing. We evaluate our algorithms on road networks from the 50 most populous cities in the world, consisting of up to 730 road segments. The algorithms, augmented with improvement heuristics, run within 3 s and generate solutions that are within 10% of the optimum. We experimentally demonstrate our algorithms with commercial UAVs on the UNC Charlotte campus road network.

Indoor exploration using mobile robots has typically focused on exploring the entire environment without considering deadlines. This paper introduces a priority-based exploration algorithm for situations with an initially unknown and dynamically assigned deadline. The goal of our exploration strategy is to determine the geometric structure of an unknown environment as rapidly as possible and return to the home location. This is necessary for dangerous environments where an initial rapid robot exploration provides critical information about the layout for subsequent operations. For example, firefighters, for whom time is of the essence, can utilize the map generated by this robotic exploration to navigate a building on fire. We present a three-part strategy to solve this problem. First, we represent the physical environment as an exploration graph, whose vertices represent the local environment with its geometric and semantic information. Second, we assign priority values to these vertices based on their environment regions. Third, we present a graph exploration algorithm that employs the vertex priorities. Simulation experiments on a set of graph environments and Gazebo environments demonstrate that, in contrast to prior approaches that ignore the semantic information, our priority-based exploration algorithm enables the robot to efficiently explore more of the environment while satisfying its deadline constraints.

The line coverage problem is the coverage of linear environment features (e.g., road networks, power lines), modeled as 1D segments, by one or more robots while respecting resource constraints (e.g., battery capacity, flight time) for each of the robots. The robots incur direction dependent costs and resource demands as they traverse the edges. We treat the line coverage problem as an optimization problem, with the total cost of the tours as the objective, by formulating it as a mixed integer linear program (MILP). The line coverage problem is NP-hard and hence we develop a heuristic algorithm, Merge-Embed-Merge (MEM). We compare it against the optimal MILP approach and a baseline heuristic algorithm, Extended Path Scanning. We show the MEM algorithm is fast and suitable for real-time applications. To tackle large-scale problems, our approach performs graph simplification and graph partitioning, followed by robot tour generation for each of the partitioned subgraphs. We demonstrate our approach on a large graph with 4,658 edges and 4,504 vertices that represents an urban region of about 16 sq. km. We compare the performance of the algorithms on several small road networks and experimentally demonstrate the approach using UAVs on the UNC Charlotte campus road network.

This paper presents algorithms to simultaneously compute the optimal assignments and formation parameters for a team of robots from a given initial formation to a variable goal formation (where the shape of the goal formation is given, and its scale and location parameters must be optimized). We assume the$n$robots are identical spheres. We use the sum of squared travel distances as the objective function to be minimized, which also ensures that the trajectories are collision free. We show that this assignment with variable goal formation problem can be transformed to a linear sum assignment problem (LSAP) with pseudo costs that we establish are independent of the formation parameters. The transformed problem can then be solved using the Hungarian algorithm in O (n3) time. Thus the assignment problem with variable goal formations using this new approach has the same O (n3) time complexity as the standard assignment problem with fixed goal formations. Results from simulations on 200 and 600 robots are presented to show the algorithm is sufficiently fast for practical applications.

We present a trajectory optimization formulation for the design of a sit-to-stand assistive device for humans with motion impairments. We develop a constrained Lagrangian to derive the equations of motion for the trajectory optimization formulation. Such a Lagrangian enables us to impose constraints on joint reaction wrenches in the human, to simulate the motion impairment of human joints due to injury and infirmity. Using trajectory optimization, we compute the optimal sit-to-stand motions of a human as well as the actuation wrenches of the sit-to-stand device. The trajectory of the device as it follows and supports the human, and its actuation wrenches provide necessary inputs for the design of the assistive device. We propose an assistive device capable of following the natural trajectory of the human during sit-to-stand. We show by numerical simulation that the human requires less effort with the device that can follow its trajectory than with an assistive device restricted to only vertical motion to lift up a human. Our formulation provides a systematic approach for the design of such sit-to-stand assistive devices.

In this paper, we present an approach for the stability analysis of mechanical part disassembly considering part motion in the presence of physical forces such as gravity and friction. Our approach uses linear complementarity to analyze stability as parts are moved out of the assembly. As each part is removed from the assembly along a specified path during disassembly, we compute the contact forces between parts in the remaining assembly; positive contact forces throughout the disassembly process imply the disassembly sequence is stable (since the parts remain in contact with one another). However, if the part that is being taken out induces motion of other parts in the remaining subassembly, we conclude the disassembly sequence is unstable. Thus, we are able to simulate the entire disassembly considering physical forces and part motion, which has not previously been done. We then show the influence of part motion on stable disassembly. In contrast to prior work on disassembly that has focused either on planning part motions based on only geometric constraints, or on analyzing the stability of an assembly without considering part motions, we explore the relation between part motion and the selection of stable disassembly sequences in 2-D and 3-D. We establish conditions that characterize path-dependent assemblies, where motion paths can play a significant role in stable disassembly. Since we track the motion of all parts in an assembly, instability inducing motions can be identified and prevented by introducing appropriate fixtures by selecting alternative disassembly sequences or by changing the motion paths. We extend the stability analysis for single part disassembly to stability analysis of subassembly disassembly. We additionally show that in the presence of friction, assembly and disassembly can be noninvertible

Lab-on-a-chip technology scales down multiple laboratory processes to a chip capable of performing automated biochemical analyses. Electrowetting on dielectric (EWOD) is a digital microfluidic lab-on-a-chip technology that uses patterned electrodes for droplet manipulation. The main limitations of EWOD devices are the restrictions in volume and motion of droplets due to the fixed size, layout, and addressing scheme of the electrodes. Optoelectrowetting on dielectric (OEWOD) is a recent technology that uses optical sources and electric fields for droplet actuation on a continuous surface. We describe an open surface light-actuated OEWOD device that can manipulate droplets of multiple volumes ranging from 1 to 50 μL at voltages below 45 V. To achieve lower voltage droplet actuation than previous open configuration devices, we added a dedicated dielectric layer of high dielectric constant (Al2O3with εrof 9.1) and significantly reduced the thickness of the hydrophobic layer. The device is capable of transporting droplets at speeds as high as 12 mm/sec using a data projector as an optical source. We developed a multiple axis contact pad design to apply lateral electric fields along different axes to achieve multi-axis droplet movement. We demonstrated microfluidic operations including droplet merging, mixing, and parallel droplet motion. Further, the OEWOD device is capable of droplet transportation using a tablet computer's LCD screen as an optical source.

A hash tag is defined to be a word or phrase prefixed with the symbol #. It is widely used in current social media sites including Twitter and Google+, and serves as a significant meta tag to categorize users' messages, to propagate ideas and topic trends. The use of hash tags has become an integral part of the social media culture. However, the free-form nature and the varied contexts of hash tags bring challenges: how to understand hash tags and discover their relationships? In this paper, we propose Tag-Latent Dirichlet Allocation (TLDA), a new topic modeling approach to bridge hash tags and topics. TLDA extends Latent Dirichlet Allocation by incorporating the observed hash tags in the generative process. In TLDA, a hash tag is mapped into the form of a mixture of shared topics. This representation further enables the analysis of the relationships between the hash tags. Applying our model to tweet data, we first illustrate the ability of our approach to explain hard-to-understand hash tags with topics. We also demonstrate that our approach enables users to further analyze the relationships between the hash tags.

In this paper we explore the problem of coordinating multiple droplets in light-actuated digital microfluidic systems intended for use as lab-on-a-chip systems. In a light-actuated digital microfluidic system, droplets of chemicals are actuated on a photosensitive chip by moving projected light patterns. Our goal is to perform automated manipulation of multiple droplets in parallel on a microfluidic platform. To achieve collision-free droplet coordination while optimizing completion times, we apply multiple robot coordination techniques. We present a mixed integer linear programming formulation for coordinating droplets given their paths. This approach permits arbitrary droplet formations, and coordination of both individual droplets and batches of droplets. We then present a linear time stepwise approach for batch coordination of droplet matrix layouts.

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.

This paper focuses on the assignment of N discrete points among K geometrically constrained robots and determination of the order in which the points should be processed by the robots. This path planning problem is directly motivated by an industrial laser drilling system with two robots that are constrained to translate along a common line while satisfying collision avoidance constraints. The points lie on a planar base plate that translates normal to the axis of motion of the robots. The geometric constraints on the motions of the robots lead to constraints on points that can be processed simultaneously.We use a two step approach to solve the path planning problem: (1) Splitting Problem: Assign the points to the K robots, subject to geometric constraints, to maximize parallel processing of the points. (2) Ordering Problem: Find an order of processing the split points by formulating and solving a multidimensional Traveling Salesman Problem (TSP) in the if-tuple space with an appropriately defined metric to minimize the total travel cost. For K = 2, we solve the splitting problem optimally in O(N3) time by converting it to a maximum cardinality matching problem. Since this is too slow for large datasets, we also provide a greedy O(N log N) algorithm. We provide computational results showing that the greedy algorithm solution is very close to the optimal solution for large datasets. For the ordering problem we present local search based heuristics to improve the multidimensional TSP tour. We give computational results for the ordering problem and for the overall performance gain obtained (over a single robot system) by using our algorithm. Finally, we extend our approach to a K-robot system and give computational results for K = 4.

In this paper, we present the use of complementarity-based dynamic simulation algorithms for kinodynamic motion planning. Dynamic simulation algorithms are used as local planning methods in sampling-based motion planning algorithms to find inputs that ensure the resulting trajectory satisfies the dynamics constraints. However, the inputs are not guaranteed to give collision-free path segments. The inputs, chosen either by random sampling or from a discretization of the available inputs, are rejected if the path segment is not collision free. In cluttered environments, finding a feasible input is difficult and sensitive to the duration ¿t of application of the input, and to the discretization resolution of the input set. When the collision constraints (or any inequality constraints on the state of the robot) are modeled as a set of complementarity constraints, the dynamic simulation algorithm gives a path segment that touches the obstacles and a set of contact forces whenever the robot makes contact with the obstacles. The sum of the chosen input forces and the contact forces transformed to the input space gives a control input that guarantees a collision-free path segment (provided it is within the actuator bounds). Thus in cluttered environments, using a complementarity-based dynamic simulation algorithm, we can find a feasible input that is relatively insensitive to the choice of ¿t and the discretization resolution of the input set. We present simple simulation examples showing the advantages of our algorithm in cluttered environments.

This paper focuses on the assignment of discrete points to two robots, in the presence of geometric and kinematic constraints between the robots. The individual points have differing processing times, and the goal is to identify an assignment of points to the robots so that the total processing time is minimized. The assignment of points to the robots is the first step in the path generation process for the robots. This work is motivated by an industrial microelectronics manufacturing system with two robots, with square footprints, that are constrained to translate along a common line while satisfying proximity and collision avoidance constraints. The N points lie on a planar base plate that can translate along the plane normal to the direction of motion of the robots. The geometric constraints on the motions of the two robots lead to constraints on points that can be processed simultaneously. We show that the point assignment for processing problem can be converted to a maximum weighted matching problem on a graph and solved optimally in O(N3) time. Since this is too slow for large datasets, we present a O(N2) time greedy algorithm and prove that the greedy solution is within a factor of 3/2 of the optimal solution. Finally, we provide computational results for the greedy algorithm on typical industrial datasets.

This paper presents a general method for exact distance computation between convex objects represented as intersections of implicit surfaces. Exact distance computation algorithms are particularly important for applications involving objects that make intermittent contact, such as in dynamic simulations and in haptic interactions. They can also be used in the narrow phase of hierarchical collision detection. In contrast to geometric approaches developed for polyhedral objects, we formulate the distance computation problem as a convex optimization problem. We use an interior point method to solve the optimization problem and demonstrate that, for general convex objects represented as implicit surfaces, interior point approaches are globally convergent, and fast in practice. Further, they provide polynomial-time guarantees for implicit surface objects when the implicit surfaces have self-concordant barrier functions. We use a primal-dual interior point algorithm that solves the Karush-Kuhn-Tucker (KKT) conditions obtained from the convex programming formulation. For the case of polyhedra and quadrics, we establish a theoretical time complexity of O(n1.5), where n is the number of constraints. We present implementation results for example implicit surface objects, including polyhedra, quadrics, and generalizations of quadrics such as superquadrics and hyperquadrics, as well as intersections of these surfaces. We demonstrate that in practice, the algorithm takes time linear in the number of constraints, and that distance computation rates of about 1 kHz can be achieved. We also extend the approach to proximity queries between deforming convex objects. Finally, we show that continuous collision detection for linearly translating objects can be performed by solving two related convex optimization problems. For polyhedra and quadrics, we establish that the computational complexity of this problem is also O(n1.5).

Digital microfluidic systems (DMFS) are a new class of lab-on-a-chip systems for biochemical analysis. A DMFS uses electro wetting to manipulate discrete droplets on a planar array of electrodes. The chemical analysis is performed by repeatedly moving, mixing, and splitting droplets on the electrodes. Recently, there has been a lot of interest in developing algorithms and computational tools for the design, simulation, and performance evaluation of DMFS. In this paper, we present an algorithm for coordinating droplet movement in batch mode operations on ring layouts with bus-phase addressing. In bus- phase systems, each electrode is not individually addressable, instead a set of electrodes are all controlled by the same signal. Though this hardware design simplifies chip fabrication, it increases the complexity of routing droplets. The presented algorithm allows multiple independent reactions, each with two reactants and one product, and chain reactions with multiple stages, where each stage produces reactants for the next stage, to take place simultaneously on the chip. This algorithm is scalable to different number of reactions within a limit which depends on the size of the layout, placement of sources and number of phases used. It also addresses any sensor constraints under which droplets need to visit sensor locations for specified amounts of time. We present simulation results using our algorithm to coordinate droplet movements for example analyses on a ring layout.

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.

We propose a new method for assembly of 3D microstructures. Hard magnets are arranged in a novel 120deg offset configuration, allowing for in-situ magnetization. The new configuration makes the use of hard magnets feasible in batch fabrication, and hard magnets allow for the use of a uniform external field for application of magnetic torque. A sequential planner was developed to calculate layout and magnet orientations for given assemblies, based on this new magnet configuration. We describe the new magnet configuration, experimentally test the configuration, and present a planner that generates a planar layout and magnet orientations.

In this paper, we present an interior point approach to exact distance computation between convex objects represented as intersections of implicit surfaces. The implicit surfaces considered include planes (polyhedra), quadrics, and generalizations of quadrics including superquadrics and hyperquadrics, as well as intersections of these surfaces. Exact distance computation algorithms are particularly important for applications involving objects that make contact, such as in dynamic simulations and in contact point prediction for dextrous manipulation. They can also be used in the narrow phase of hierarchical collision detection. In contrast to geometric approaches developed for polyhedral objects, we formulate the distance computation problem as a convex optimization problem; this optimization formulation has been previously described for polyhedral objects. We demonstrate that for general convex objects represented as implicit surfaces, interior point approaches are reasonably fast and in some cases, owing to their global convergence properties, are the only probably good choice for solving proximity query problems. We use an interior point algorithm that solves the KKT conditions obtained from the convex programming formulation. We present implementation results for example implicit surface objects and demonstrate that distance computation rates of about 1 kHz can be achieved

This paper describes a computational approach to designing a digital microfluidic system (DMFS) that can be rapidly reconfigured for new biochemical analyses. Such a “lab-on-a-chip” system for biochemical analysis, based on electrowetting or dielectrophoresis, must coordinate the motions of discrete droplets or biological cells using a planar array of electrodes. The authors have earlier introduced a layout-based system and demonstrated its flexibility through simulation, including the system's ability to perform multiple assays simultaneously. Since array-layout design and droplet-routing strategies are closely related in such a DMFS, their goal is to provide designers with algorithms that enable rapid simulation and control of these DMFS devices. In this paper, the effects of variations in the basic array-layout design, droplet-routing control algorithms, and droplet spacing on system performance are characterized. DMFS arrays with hardware limited row-column addressing are considered, and a polynomial-time algorithm for coordinating droplet movement under such hardware limitations is developed. To demonstrate the capabilities of our system, we describe example scenarios, including dilution control and minimalist layouts, in which our system can be successfully applied.

This paper focuses on finding the global minimum time control for the collision-free coordination of multiple robots with double integrator dynamics and with additional robot state constraints and control constraints. We initially assume each robot's path is specified and decompose it into collision segments and collision-free segments. The collision avoidance constraints for pairs of robots and the dynamics constraints can then be combined to formulate the coordination problem as a mixed integer nonlinear program (MINLP). In this paper, we first show convexity of the constraints for an individual robot path segment under certain assumptions. We next establish that we are guaranteed to find the global optimum of the MINLP because each subproblem of the MINLP is a convex program, based on the convexity result on individual robot segments. To the best of our knowledge, this is the first result on directly obtaining the global optimum coordination of multiple (more than two) robots with dynamics constraints. Finally, we extend these results to the task of coordinating robots on a given roadmap, where the roadmap has multiple candidate paths for each robot. We present an approach to simultaneously select each robot's traversal path and generate its continuous velocity profile. These robot velocity profiles satisfy the dynamics constraints, avoid collisions, and globally minimize the completion time. We use the MINLP Solver [25], which combines a branch-and-bound algorithm with a filterSQP algorithm, to solve the MINLP coordination problems. We illustrate the approach with multiple robot coordination examples with up to 156 collision zones.

Coordinating multiple manipulators in a shared workspace while considering their dynamics is an important problem. This problem of collision-free coordination arises in assembly, materials transfer, and welding workcells. Previous approaches that considered robot dynamics have typically been restricted to coordinating just two or three manipulators, even when their paths are specified. We address the task of coordinating the motions of multiple manipulators when either their trajectories or their paths are given. By exploiting a fundamental time scaling law for manipulators based on their dynamics, we identify sufficient conditions for collision-free coordination of the robots when the velocity profiles can be uniformly time-scaled and the robot start times can be varied. We describe an approach that develops mixed integer programming formulations of these problems, where the time scaling factors are linear variables, to automatically minimize completion time. This method can potentially coordinate the motions of many manipulators.

This paper studies optimal control of multiple robot systems with frictional contact. The task is to move the robots into goal regions with specified velocities using external control forces. The robots have nonlinear dynamics, which may arise from the robot body dynamics, friction between robot and environment, and friction between robot and robot. Nonpenetration constraints between robots are imposed, and the robots are assumed rigid. The problem is modeled as a mathematical program with complementarity constraints (MPCC). The MPCC model is solved by using its elastic mode, which is a well-behaved nonlinear programming problem. Preliminary results with this approach are illustrated on example problems. The main contributions of this paper are a novel optimal control model that can deal with friction in the multiple robot system, and application of a new mathematical programming algorithm to solve the MPCC formulation. This optimal control model has potential applications in robot systems with friction, such as multifinger manipulation, manipulation with ropes, and multirobot pushing coordination.

This paper focuses on the coordination of multiple robots with kinodynamic constraints along specified paths. The presented approach generates continuous velocity profiles that avoid collisions and minimize the completion time for the robots. The approach identifies collision segments along each robot's path and then optimizes the motions of the robots along their collision and collision-free segments. For each path segment for each robot, the minimum and maximum possible traversal times that satisfy the dynamics constraints are computed by solving the corresponding two-point boundary value problems. Then the collision avoidance constraints for pairs of robots can be combined to formulate a mixed integer nonlinear programming (MINLP) problem. Since this nonconvex MINLP model is difficult to solve, we describe two related mixed integer linear programming (MILP) formulations that provide schedules that are lower and upper bounds on the optimum; the upper bound schedule is a continuous velocity schedule. The approach is illustrated with robots modeled as double integrators subject to velocity and acceleration constraints. An implementation that coordinates 12 nonholonomic car-like robots is described.

Coordinating the motions of multiple robots operating in a shared workspace without collisions is an important capability. We address the task of coordinating the motions of multiple robots when their trajectories (defined by both the path and velocity along the path) are specified. This problem of collision-free trajectory coordination arises in welding and painting workcells in the automotive industry. We identify sufficient and necessary conditions for collision-free coordination of the robots when only the robot start times can be varied, and define corresponding optimization problems. We develop mixed integer programming formulations of these problems to automatically generate minimum time solutions. This method is applicable to both mobile robots and articulated arms, and places no restrictions on the number of degrees of freedom of the robots. The primary advantage of this method is its ability to coordinate the motions of several robots, with as many as 20 robots being considered. We show that, even when the robot trajectories are specified, minimum time coordination of multiple robots is NP-hard.

This paper presents a simple parts feeder consisting of a grid of retractable pins on a vertical plate to manipulate polygonal parts. This reconfigurable "Pachinko machine" is intended as a parts feeding device for flexible assembly. A part dropped on this device may come to rest on the actuated pins, or bounce out or fall through. We can control the set of equilibrium part configurations by selecting the set of actuated pins. The objective is to automatically compute sequences of pin actuation that bring the part to a goal configuration without predicting the exact object motion between equilibria. Our approach is based on the construction of the capture region of each part equilibrium. Reorienting a part reduces to building a directed graph whose nodes consist of equilibria and whose area link pairs of nodes such that the first equilibrium lies in the capture region of the second one, and then exploring this graph to find paths from initial to goal states. We have implemented an algorithm to generate the capture regions and these paths, and have conducted experiments on a prototype Pachinko machine.

Packaging products such as telephones and two-way radios after assembly is a common manufacturing task. Carton folding is a packaging operation typically performed by human operators or with fixed automation. We present a flexible method to fold cardboard cartons using fixtures; a carton blank is folded by moving it through a fixture with a robot. This method uses interchangeable fixtures to enable rapid changeovers between product models. We outline an approach to design a fixture given a carton and a folding sequence. We present an implemented motion planning algorithm that generates all folding sequences for a carton by modeling it kinematically as a many degree-of-freedom robot manipulator with revolute joints and branching links. Folding fixtures constrain the carton motion to paths consisting of line segments in its configuration space. We characterize the set of valid paths for these carton robots and generate them using the motion planner. To illustrate the method, we selected a folding sequence for an example carton, designed a fixture, and demonstrated folding of the carton from blanks with an industrial robot.

Carton folding is a packaging operation performed by human operators or with fixed automation. We present a flexible method to fold cardboard cartons using fixtures. A carton blank is folded by moving it through a fixture with a robot. This method of using interchangeable fixtures enables rapid changeovers between product models. We outline a procedure to design a fixture given a carton and a folding sequence. We present an implemented motion planning algorithm that generates all folding sequences for a carton by modeling it as a many degree of freedom robot manipulator with revolute joints and branching links. A fixture constrains the carton to move along paths consisting of line segments in its configuration space, and the motion planner generates these paths. To illustrate the method, we selected a folding sequence for an example carton, designed a fixture, and demonstrated folding of the carton from blanks with an industrial robot.

Parts orienting, the process of bringing parts in initially unknown orientations to a goal orientation, is an important aspect of automated assembly. Bowl feeders used in industry rely on a sequence of mechanical operations, without using sensors, to orient parts. In our work, we use partial information sensors along with mechanical operations to eliminate uncertainty in part orientation. We show that sensor based orienting plans need O (m) operations, where m is the maximum number of states with the same sensor value. We characterize the relation between part shape, orientability, and recognizability to identify conditions under which a single plan can orient and recognize multiple part shapes. We describe implemented planners and experiments to demonstrate generated plans.

Parts manufactured to tolerances have shape variations. Most work in robotic manipulation assumes that part shape does not vary. Orienting devices such as bowl feeder frequently fail due to variations in part shape. In this paper we develop techniques to orientate parts with shape uncertainty. We present a shape uncertainty model and describe the nondeterminism in parts orienting that arises from shape uncertainty. We characterize a class of parts that can be reliably oriented with sensor-based and sensorless orienting plans under shape uncertainty. We present implemented planners that generate orienting plans for the entire variational class of part shapes given a nominal part shape and shape uncertainty bounds. We describe experiments to demonstrate generated plans and outline issues for future work.

This paper explores a sensorless technique for orienting planar parts. We follow an approach described in the ours earlier papers (1995), called one joint over conveyor (1JOC), which can perform planar manipulation using a single controlled joint in combination with a constant-velocity conveyor. Our previous work demonstrated that the IJOC approach can orient and feed planar polygonal parts, given a singulated part in a known initial location. This paper shows that a variation called the sensorless IJOC can orient and feed polygonal parts up to symmetries in the underlying mechanics, without knowing the initial location and without sensors.

Programmable parts orienting is an important capability for flexible automation systems. Here we study how a part grasped in an unknown orientation by a force-controlled robot can be oriented by a sequence of push-align actions against a wall followed by sensor measurements of the distance from the grasp point to the wall. This paper concentrates on three issues: planning a sequence of actions to orient a part, exploring design changes that enable the part to be oriented in fewer steps, and the effect of shape uncertainty, due to manufacturing tolerances, on part orientability.

The authors study the use of pushing actions with a fence to orient and translate objects in the plane. They describe a planner which a guaranteed to construct a sequence of pushing actions to move any polygonal object from any initial configuration to any final configuration. This planner, which utilizes an analysis of the mechanics of pushing an object, generates open-loop plans which do not require feedback sensing. These plans are guaranteed to succeed provided certain physical assumptions are met. Results of experiments conducted to demonstrate the generated plans are presented.>