Large-Scale Multi-Robot Assembly Planning
for Autonomous Manufacturing

Kyle Brown^*<EMAIL_ADDRESS>
Dylan M. Asmar^*<EMAIL_ADDRESS>
Mac Schwager^†<EMAIL_ADDRESS>
Mykel J. Kochenderfer^*<EMAIL_ADDRESS>
^*Stanford Intelligent Systems Laboratory

^†Multi-Robot Systems Lab

Stanford University, 496 Lomita Mall, Stanford, CA 94305, USA

Mobile autonomous robots have the potential to revolutionize manufacturing processes. However, effective employment of large robot fleets in manufacturing requires addressing numerous challenges including the collision-free movement of multiple agents in a shared workspace, effective multi-robot collaboration to manipulate and transport large payloads, complex task allocation due to coupled manufacturing processes, and spatial planning for parallel assembly and transportation of nested subassemblies. In this work, we propose a full algorithmic stack for large-scale multi-robot assembly planning that addresses these challenges and can synthesize construction plans for complex assemblies with thousands of parts in a matter of minutes. Our approach takes in a CAD-like product specification and automatically plans a full-stack assembly procedure for a group of robots to manufacture the product. We propose an algorithmic stack that comprises: (i) an iterative radial layout optimization procedure to define a global staging layout for the manufacturing facility, (ii) a `graph-repair' mixed-integer program formulation and a modified greedy task allocation algorithm to optimally allocate robots and robot sub-teams to assembly and transport tasks, (iii) a geometric heuristic and a hill-climbing algorithm to plan collaborative carrying configurations of robot sub-teams, and (iv) a distributed control policy that enables robots to execute the assembly motion plan without colliding with each other. We also present an open-source multi-robot manufacturing simulator implemented in Julia as a resource to the research community, to test our algorithmic stack and to facilitate multi-robot manufacturing research more broadly.[<https://github.com/sisl/ConstructionBots.jl>] Our empirical results demonstrate the scalability and effectiveness of our approach by generating plans to manufacture a  model of a Saturn V launch vehicle with $1845$ parts, $306$ subassemblies, and $250$ robots in under three minutes on a standard laptop computer.

§ INTRODUCTION

Consider a flexible factory environment in which a team of mobile robots must collaborate to construct a large assembly from a collection of discrete components. An assembly plan is given to the factory, which provides a tree of assembly operations to iteratively combine components into progressively larger subassemblies until the final assembly is complete. To fulfill the assembly plan, the robotic factory must spatially configure a set of construction stations for the subassemblies, culminating in the final assembled product at a final station. The factory then needs to produce a motion plan for the robots to shuttle parts and subassemblies between the stations to realize the abstract assembly plan.  As individual components are combined into larger and larger subassemblies, the plan must allow robots to collaboratively transport the larger payloads, taking into account the load-carrying capacity of individual robots.  Finally, the robots must avoid collisions with each other as they navigate the environment to collect components and deliver them to the appropriate locations. In this paper, we propose an algorithmic stack to solve these robot planning and coordination problems that are central to multi-robot manufacturing. We also present a multi-robot manufacturing simulator, ConstructionBots.jl, implemented in Julia and open-sourced for the research community to facilitate research in multi-robot manufacturing.

An overview of the proposed multi-robot assembly planning system. (a) Starting with a CAD-like project specification, the process evolves to determine (b) the configuration of transport teams, then calculates a (c) hierarchical geometric approximation of parts and transport units. (d) Based on the geometry, a spatial layout for the construction site is designed. (e) Task allocation and team formations are computed, following which (f) a decentralized strategy ensures collision-free execution. (g) The entire planned procedure is simulated, culminating in the (h) final assembled project. The arrows indicate the sequential flow of the planning process.

We consider this multi-robot construction concept as an important facet of Industry 4.0 <cit.>, the widely heralded fourth industrial revolution fueled by advances in autonomy, AI, and ubiquitous wireless connectivity. Although modern assembly lines are optimized to produce complex assemblies at high speeds, they are tailored to a specific product. Reconfiguring an assembly line to manufacture a new product or a custom variation on a product, can be a costly, time-consuming, human labor-intensive effort <cit.>. In contrast, the multi-robot construction system concept described above has the potential to deliver faster, cheaper, more customizable, and more reconfigurable fabrication for a broad range of assemblies.
Such a system would be capable of building any assembly for which (a) the raw materials and subassemblies can be transported by robot teams and (b) the atomic operations required to incorporate each material or subassembly into its parent assembly are supported by the factory tooling. In this work we consider atomic part-to-part fastening operations as existing primitives, hence, we do not present research on the control of contact forces, insertion, screwing, riveting, soldering, welding, etc. Our work is focused on task planning, motion planning, and collaborative teaming.

Collaboration between robots introduces difficulty to the planning and control problem by often increasing computational complexity as the number of robots increases <cit.>.
Various systems have been proposed for “end-to-end” multi-robot assembly planning and execution <cit.>. These approaches perform both high-level task planning, coarse “transit” motion planning, and detailed manipulation planning required to fasten assembly parts together (e.g., screwing and riveting). Other approaches focus on the geometric assembly planning task, which amounts to determining in what order, and along what paths, to assemble a given assembly subject to constraints that all components must move into their goal configurations without interfering (i.e., colliding) with other components <cit.>. <cit.> address the geometric assembly planning process with the added complexity of planning sequences of robot poses to realize the assembly process. Though these works represent significant progress toward the goal of autonomous manufacturing, there are still challenges in scalability, multi-robot coordination, and a system-view integration of the many layers of planning required for this problem.

In contrast to existing work, our system generally approaches multi-robot assembly planning from a higher level of abstraction. We address task planning and transit planning but abstract away the kino-dynamic details of piecing together assemblies. As such, we are able to focus on larger assemblies than those often handled by these more detailed end-to-end approaches.
We address the following specific problems:

* Transport team configuration – How many robots are needed and how should robots be positioned when transporting a particular payload?

* Spatial layout of the construction site – Where will each assembly be built, and where will the components of those assemblies be delivered?

* Sequential task allocation and team forming – Which robots will collect and deliver which payloads? Since there are generally far more payloads than robots, individual robots generally have to transport multiple payloads in sequence.

* Collision avoidance with heterogeneous agent geometry and dynamics – How must laden and unladen robots and robot teams move, subject to motion constraints that depend on the payload size and team configuration, to avoid collision with other robots and the active construction sites in the environment?

We present a proof-of-concept system that can synthesize construction plans for assemblies with thousands of parts in a matter of minutes. To illustrate the environment model and the process of synthesizing a construction plan, we introduce a simple “tractor” project as a running example. This assembly was defined in LeoCAD and is based on  model 10708, Green Creativity Box. The tractor model has a total of 20 individual pieces, which are organized into one final assembly (the tractor) and seven subassemblies. An overview of our proposed process using the tractor model is provided in <ref>.

We review the related literature in <ref> and define the environment model in <ref>.
In <ref>, we introduce an approach for determining multi-robot carrying configurations for transporting objects and then describe our method for generating the spatial layout of a construction site in <ref>. <Ref> introduces our approach to task allocation and team forming and we describe a decentralized strategy for plan execution and collision avoidance in <ref>. <Ref> reports on several simulations demonstrating our system on various assemblies and then we provide limitations and future work in our discussion in <ref>.

§ RELATED WORK

Our problem falls under the umbrella of Task and Motion Planning (TAMP) problems, which combine discrete task planning with multi-modal continuous motion planning <cit.>. TAMP is a broad framework that is applicable when one or more robots must both move through a continuous environment and modify the state of objects in the environment.
General TAMP problems may incorporate geometric, kinodynamic, and modal variables and constraints. Our problem setting involves variables and constraints in these categories, and could theoretically be expressed as a generic TAMP problem and solved by a general-purpose TAMP solver.
However, we start with a project specification in our problem setting and we have developed a method that is tailored to these demands, rather than relying on a general-purpose TAMP solver.

An important element of TAMP is the notion of a kinematic graph, which specifies kinematic constraints between entities in the environment <cit.>. As robots interact with the world, the kinematic graph undergoes mode switches, wherein edges are added, removed, or modified. A kinematic graph is our main tool for modeling the transient “pick up”, “put down”, and “lock into parent assembly” modal switches that occur as robots carry components through the environment and attach them to their parent assemblies.

Full systems.

Previous work has proposed “end-to-end” multi-robot assembly planning and execution. For example, IKEABot is a multi-robot system for furniture assembly <cit.>. IKEABot takes a geometric assembly description as input, then synthesizes an assembly plan and coordinates the actions of delivery robots (which transport materials) and assembly robots (which attach parts to each other as prescribed by the assembly plan). <cit.> propose a system for multi-scale assembly with robot teams. The authors demonstrate their approach with an end-to-end hardware demo wherein a team of robots fastens a mock airplane wing panel to a mock wing box. Our problem setting addresses many of the considerations addressed by these types of systems but ignores others, allowing us to focus on different aspects of the problem. For example, we abstract away the fine manipulation required to actually incorporate each component into its parent assembly and we also ignore mass and structural properties of robots and objects, using purely geometric models instead.

Assembly planning.
Geometric assembly planning is the problem of determining trajectories along which components of an assembly can be brought into (or out of) mating position without interfering with the rest of the assembly. An assembly plan is often generated by first computing a disassembly plan (i.e., begin with a fully assembled model and plan how to remove each component) and then reversing the disassembly plan through time.  introduced the concept of a “non-directional blocking graph” that encodes the geometric interactions/interferences between parts <cit.>. This representation can be used to identify the directions in a part's configuration space in which it may be perturbed without interfering with the rest of the assembly. The non-directional blocking graph fits into the more general motion space framework described by <cit.>. <cit.> use considerations similar to those encoded by the non-directional blocking graph to impose partial ordering constraints in a multi-robot assembly planning problem. Our setting assumes that a feasible geometric assembly plan has already been found for each manufacturing project.

Construction site layout.
The geometric assembly plan specifies how to bring parts together. With large, complex assemblies, it is also important to determine where each subassembly will be constructed. This is closely related to the problem of facility layout planning, a well-studied topic in the literature <cit.>. Discrete facility layout problems include the quadratic assignment problem <cit.>. The design variables correspond to facility locations and the cost function is the sum of pairwise distance costs between facilities. Continuous facility layout (CFL) problems take the form of geometric packing problems (packing many small shapes into a larger shape) with similar pairwise distance costs <cit.>.
In our setting, the quality of a particular construction layout depends not only on the distance between related “facilities” (assembly construction areas) but also on the traversability of the inter-facility spaces through which robots are allowed to travel.

Team forming.
In scenarios where a team of robots must collaborate to transport a large payload, it is necessary to determine the “carrying” configuration of the robots relative to the payload. This problem is related to grasp planning in both single and multi-robot manipulation problems. Four cooperative manipulation protocols are proposed by <cit.> for multi-robot planar manipulation of furniture. A distributed system for multi-robot collaborative transport is proposed by <cit.>. A multi-robot grasp and regrasp planner based on constraint satisfaction programming is proposed by <cit.>, for scenarios where a team of robots must work together to put together an assembly. <cit.> present a grasp coordination method for two-robot load sharing in collaborative transport tasks. They assume that the first agent's grasp has already been selected, and they select (from a finite number of candidate grasps) the second agent's grasp to optimize a load sharing objective function.

<cit.> study the problem of coalition formation with spatial and temporal constraints (CFSTP). Their setting involves a set of tasks with deadlines and service durations and a set of agents that can service those tasks by convening in teams at prescribed spatial locations. Different agents have different “skills”, which determine how effective they are at servicing different kinds of tasks. The size of a coalition required to service a given task depends on the skills of the team members. Though CFSTP involves deadlines and task service durations, it does not include intertask precedence constraints. We build upon the ideas presented by  to include intertask precedence constraints and present algorithms that scale to much larger problems.

Collision-free routing.
A very large body of work exists on distributed collision avoidance in continuous space. Two approaches relevant to our methods are artificial potential fields <cit.> and Reciprocal Velocity Obstacles (RVO) <cit.>. Potential functions define vector fields that can be used to inform robots' continuous control signals. Repulsive potentials can push a robot away from obstacles and other robots, attractive potentials can draw a robot toward goals, rotational potentials can push a robot around obstacles or other robots, etc. Multiple potential functions can be composed to create control laws that simultaneously pursue multiple objectives. For example, <cit.> use various potential field compositions with a finite state controller to enable distributed collaborative object transport.

RVO prevents collisions by placing constraints in neighboring robots' velocity spaces. It assumes that each robot's desired velocity is known to all other robots. In a convex environment where two robots are trying to reach different goals and we wish to minimize the sum of their travel times, RVO is an optimal collision avoidance strategy <cit.>. Though this guarantee of optimality is not assured in scenarios with more than two simultaneously interacting robots, RVO leads to very efficient collision avoidance in sparse interaction settings. Though RVO is prone to gridlock in some scenarios, it can still work in settings with more dense interaction. We use these ideas as key components in our full-stack implementation to achieve a distributed, collision-free execution strategy.

§ ENVIRONMENT

We model the environment as a 3-dimensional Euclidean space. Robots, objects, and assemblies are modeled as rigid bodies. We assume a fleet of identical, cylinder-shaped transport robots. Objects and assemblies may have arbitrary $3$D geometry. The factory floor is a plane perpendicular to the vertical axis of the world coordinate frame $\worldframe.$ Robots are constrained to move only on the $2$D plane of the factory floor, and their orientation remains fixed (a robot's configuration is fully determined by its $x$- and $y$-position on the floor). The joint configuration space of the entire system (all robots and objects together) is the collision-free subset of the Cartesian product of their individual configuration spaces.

§.§ Assemblies

An assembly consists of two or more components, whose prescribed configurations relative to the assembly frame are defined by transformation matrices. A component can be a single object or a subassembly with its own set of components. A project specification details one or more assemblies to be built, and may additionally group subsets of each assembly's components into an ordered sequence of build phases. A component may be added to its parent assembly only if the associated build phase is active. When all components in a build phase have been incorporated, the next build phase becomes active.

In this work, we use  models to evaluate our algorithms.  models offer a convenient framework for defining large assemblies that are often composed of smaller assemblies in addition to individual parts. Throughout this work, we provide illustrations with assemblies that are defined using the [<https://www.ldraw.org>] file specification, an open-source tool for describing  bricks and models. Some of the models used in our examples can be found in the LDraw Official Model Repository.[<https://omr.ldraw.org>] We designed others ourselves using LeoCAD,[<https://www.leocad.org>] an open-source CAD software tool for defining LDraw models.[This work is neither sponsored, authorized, nor endorsed by , , or LeoCAD.] A graphical depiction of the tractor assembly is shown in <ref>.

A visualization of the project specification for our example tractor assembly. The final assembly is composed of three subassemblies and a few individual parts.

§.§ Transport Units

When a single robot or a team of robots transports an object or assembly, the robots and cargo together are referred to as a transport unit. To collect a payload, a robot (or team of robots) must move into carrying formation at a defined pickup location. Once at the pickup location, the cargo moves into its carrying configuration relative to the robots. When the cargo is secured in its carrying configuration, the transport unit may begin to move through the environment.

For a given object or assembly, the environment model employs a geometric heuristic to specify how many robots must participate in the transport unit. The planner must then identify an appropriate carrying formation for the team. Since the geometric “team size” heuristic is closely related to our method for determining transport unit formation, we introduce both in <ref>.

The nominal configuration space of a transport unit is the same as that of a robot—i.e., the transport unit may translate along the floor of the environment, but may not rotate or move vertically. The velocity of the transport unit is constrained according to

\begin{align}
\Vert\posvel\Vert \leq \max (\vmaxrobot{} - \rectvolume{}\cdot\velvolumefactor{}, \vminrobot{}), \label{eqn:transport_unit_speed_limit}
\end{align}

where $\vmaxrobot{}$ denotes the maximum speed permitted for an unladen robot, $\rectvolume$ denotes the volume of the smallest hyperrectangle that completely encloses the transport unit, $\velvolumefactor{}$ is a scaling parameter, and $\vminrobot{}$ is a lower bound on the speed limit. This simple heuristic speed limit law is a proxy for a more sophisticated model that might account for robot and cargo dynamical properties, actuator constraints, and other considerations. The speed limit rule adds a layer of realism and complexity to the problem of collision-free navigation, as moving entities differ both in size and in the speed at which they can travel.

When a transport unit reaches the delivery location for its cargo, the payload is moved into a prescribed staging configuration. The dropoff procedure may not begin until the associated build phase of the cargo's parent assembly is active. After the cargo is moved into its staging configuration, the transport unit disbands, allowing the robots to break from carrying formation and attend to other tasks. Meanwhile, the assembly component is moved from its staging configuration into its final configuration relative to the parent assembly frame. Upon reaching the goal configuration, the component is “captured” and locked into place as part of the parent assembly.

§.§ Methods Overview

In this work, we start with a project specification that details the geometry of the parts and where they are located within the assembly. A graphical representation of a project specification is shown in <ref>. To fulfill a project specification, our autonomous multi-agent robotic assembly system creates and executes a construction plan. An overview of the major components of this process is provided in <ref>. The plan is created in three primary stages and then executed with a distributed collision avoidance strategy.

Configure transport units (<ref>).Our system first determines how many robots will be needed and where each robot will be positioned relative to the payload in order to transport each object and assembly. A few of the transport unit configurations for the tractor project are visualized in <ref>.

Construct staging plan (<ref>).The system determines where to build each assembly and where each component of that assembly will be dropped off. Each assembly is constructed in its own staging area—a circular region on the factory floor. We determine the component dropoff locations by minimizing the distance from the dropoff location within the staging area to the final configuration of the component within the parent assembly. We attempt to arrange the staging areas so that every assembly can be transported in a straight line from its staging area to the staging area of its parent assembly without entering any other staging areas. An example staging plan for the tractor project is depicted in <ref>.

Allocate transport tasks (<ref>).In this phase, we construct a new type of operating schedule, which incorporates collaborative transport tasks and discrete build phases. Partial schedules for the tractor project are visualized in <ref> and <ref>. To allocate tasks to individual robots and robot teams, we build upon the task allocation algorithm described in <cit.>.

Collision avoidance (<ref>).To execute the construction plan, the robots must perform their assigned delivery tasks while avoiding collision with each other. We propose a distributed online strategy where each agent follows a reactive velocity control policy consisting of a switching controller, a dispersion component, and a collision-avoidance controller.

To fulfill a project specification, our autonomous multi-agent robotic assembly system creates and executes a construction plan. The plan is created in three stages:

* Configure transport units (<ref>): in this phase, our system determines how many robots will be needed—and where each robot will be positioned relative to the payload—to tranport each object and assembly. A few of the transport unit configurations for the tractor project are visualized in <ref>.

* Construct staging plan (<ref>): in this phase, the system determines where to build each assembly and where each component of that assembly will be dropped off. Each assembly is constructed in its own staging area—a circular region on the factory floor. The staging areas are arranged so that (a) every subassembly can be transported in a straight line from its staging area to the staging area of its parent assembly without entering any other staging areas, and (b) every object can be transported from its initial location to the staging area of its parent assembly without entering any other staging area. To the extent possible, dropoff locations for objects and assemblies are selected so as to minimize the distance from dropoff location to final configuration within the parent assembly.  An example staging plan for the tractor project is visualized in <ref>.

* Allocate transport tasks (<ref>): in this phase, we construct a new type of operating schedule, which incorporates collaborative transport tasks and discrete build phases. Partial schedules for the tractor project are visualized in <ref> and <ref>. To allocate tasks to individual robots and robot teams, we build upon the task allocation algorithm described in <cit.>.

To execute the construction plan, the robots must perform their assigned delivery tasks while avoiding collision with each other. For this execution phase, we use a combination of local visibility graph path planning, highways, and distributed reactive collision avoidance.

§ CONFIGURING TRANSPORT UNITS

For each payload to be transported, it is necessary to determine (a) how many robots should participate in the transport unit, and (b) where they should be positioned relative to each other and the payload. In a real-life collaborative transport scenario, these considerations would depend on many factors, including total mass and mass distribution of the payload, structural properties of the payload (e.g., would a long, thin object bend or collapse if only supported at the ends?), “grippability” of the payload (i.e., where and how can robots securely grasp the payload?), robot actuator limits, and the shape of both the payload and the robots.

Determining physically realizable transport team sizes and configurations is beyond the scope of this work. However, we employ a heuristic geometric approach to provide plausible answers to both considerations. Intuitively, larger payloads should be carried by more robots. However, the shape of the payload also impacts how many robots can fit in a feasible carrying configuration (i.e., a configuration in which every robot is positioned directly beneath some part of the payload). The remainder of this section describes our heuristic approach.

Given an object $o$, let $c$ represent the convex hull of the projection of $o$ onto the $x$-$y$ plane—i.e., the “footprint” of $o$ on the factory floor. We assume that $o$ has no curved surfaces, or, alternatively, that its geometry has been approximated such that there are no curved surfaces and that the error between true and approximated geometry is very small compared to the size of a robot. Because we assume no curved surfaces in the geometry of $o$, $c$ is a polygon. We define the set of candidate “support points” as the vertices of $c$. These are the locations at which robots may be placed to support the object in a transport unit.
The reason for limiting the candidate carrying positions to the vertices of the convex hull is that the object may have arbitrary non-convex shape; there could, for example, be a gaping hole in the middle of the object, such that a robot placed underneath the hole would not be able to carry any weight. If a robot positions itself at a vertex of the footprint, we can guarantee that it will be directly beneath a solid part of the object.

Let $l$ represent the length of $c$ defined as the maximum distance between any two points in $c$, and let $w$ represent the width defined as the maximum distance between any two points in $c$ projected onto the plane normal to the direction in which $l$ is measured (the values of $l$ and $w$ are the first and second singular values of the matrix whose columns are formed from the coordinates of the vertices of $c$). Let $p$ denote the perimeter of $c$, and let $\robotradius$ denote the robot radius. Finally, let $N$ denote the number of edges in $c$ whose lengths are less than $2\robotradius$ (we cannot place two robots at both ends of any such edge). We wish to find $n$, the number of robots required to transport $o$.

Note that $\minrobots = ( p / (\pi \robotradius) ) \backslash 1$ is a lower bound on the number of disks of radius $\robotradius$ that can fit around the perimeter of $c$, where the backslash operator  $\cdot \backslash  \cdot$ denotes integer division (i.e., $\cdot \backslash 1$ denotes rounding down to the nearest integer).
The value of $n$ is determined by
n =
max(1, min(|c |- N,  min( ,  2 √())) \1),     $\text{if} \ w \geq 2\robotradius$

max(1,  min(,  2) ),       otherwise,

where $\vert c \vert$ denotes the number of vertices of $c$.
The case defined by <ref> applies for payloads where the width of the payload is greater than twice the robot radius. It maximizes the number of robots under the constraint that there must be enough feasible carrying positions $\vert c \vert - N$ and the number of robots must not exceed $\minrobots$ or $2\sqrt{\minrobots}$. This second term is used to ensure that the number of robots grows sublinearly with increasing footprint perimeter for large payloads.
The second case ensures that long skinny objects are carried by just two robots.

If $n=1$, the single robot carrying position is directly below the center of the minimum-radius hypersphere that fully encloses the payload. If $n>1$, the carrying positions are selected from the candidate positions according to the greedy hill climbing optimization procedure outlined in <ref>. The idea is to initialize a vector of indices into the points of $c$, and then iteratively improve those indices by trying all neighboring indices whose elements are within $\pm1$ of the elements of the corresponding current indices. The score of a given set of carrying positions is a linear combination of three terms: the first term (<ref>) measures the minimum distance between consecutive points; the second term (<ref>) measures the sum of these neighbor-neighbor distances; the third term (<ref>) measured the minium distance between any two points in the set. This particular score function is a hand-engineered heuristic to encourage carrying configurations where the robots are as spread out as possible. Examples of generated transport unit configurations for the tractor assembly, subassemblies, and objects are shown in <ref>.

Greedy Carrying Position Optimization
[1]
$n = \vert v \vert$

$\bestidxs \gets$ $n$ indices drawn uniformly from $1{:}\vert v \vert$ without replacement
$\updatedflag = \textsc{true}$
$\updatedflag \gets \textsc{false}$
$\candidateidxs \in \idxneighbors{\bestidxs}$
$\idxscore{c[\candidateidxs]} > \idxscore{c[\bestidxs]}$
$\bestidxs \gets \candidateidxs$
$\updatedflag \gets \textsc{true}$
$c_1 \gets \min_{i \in 1{:}\vert pts \vert}(\Vert pts[i]-pts[i+1] \Vert)$
$c_2 \gets \sum_{i \in 1{:}\vert pts \vert} \Vert pts[i]-pts[i+1] \Vert$
$c_3 \gets \min_{p_1 \in pts, p_2 \in pts}(\Vert p_1-p_2 \Vert)$
$c_1 + \frac{0.5}{\vert pts \vert} c_2 + \frac{0.1}{\vert pts \vert^2} c_3$

$\{\candidateidxs^\prime \mid \Vert \candidateidxs[i] - \candidateidxs^\prime[j] \Vert \leq 1, \forall i,j \in 1{:}\vert \candidateidxs \vert, i \neq j\}$

A visualization of the transport unit configurations for several of the assemblies and objects associated with the tractor project. The payload geometry is shown in black and white. The convex hull is highlighted in green. Robots are shown as blue disks, with their carrying positions highlighted with smaller orange disks.

§ HIERARCHICAL GEOMETRY APPROXIMATION

During the process of creating the construction plan, we often need to reason about the distance between geometric sets representing assemblies, components, and robots. Computing such distances can be time-consuming when the underlying sets can take on arbitrary non-convex geometries (as is the case with the various components that may be part of a given manufacturing project). For this reason, we chose to work instead with convex over-approximations of the base geometry.

We make use of three types of bounding geometries: spheres, vertical cylinders, and vertical octagonal prisms (<ref>). The bounding geometry for each individual object is computed directly from the base geometry. The bounding geometry for an assembly can be computed either from the base geometry of its components or from the approximated geometry of those components (in either case, the geometry of each component must first be transformed to match the assembled configuration of the assembly). Though the latter approach is generally more efficient (and is, therefore, the preferred method with large assemblies) it results in a looser-fitting bounding geometry. For small assemblies like the tractor, we opt for the former, more precise approach. The same approach is used to compute the bounding geometry of each transport unit from the geometry of the associated payload and robot team.

Over-approximated geometries (sphere, vertical cylinder, octagonal prism) for the final tractor assembly (top row) and for a transport unit.

To compute a bounding sphere, we solve a quadratic program to find the point that minimizes the maximum $L_2$ distance to any point in the input set. This can be done more efficiently with algorithms like the one proposed by <cit.>. To compute a bounding vertical cylinder, we solve the same quadratic program used for computing a bounding sphere, but with the input set projected onto the horizontal plane. We then compute the top and bottom of the cylinder by finding the maximum and minimum values of the input set projected onto the vertical axis. This same method is used to determine the top, bottom, and sides of the bounding vertical octagonal prism, but we additionally impose constraints so that each vertical face of the prism has a width of at least some minimum positive value. This ensures that each prism will have all eight of its sides.

§ CONSTRUCTING A STAGING PLAN

The global staging plan defines the staging location of each assembly—that is, where on the factory floor the assembly will be built. For each assembly, the assembly subplan consists of a sequence of build-phase subplans. A build phase subplan prescribes the dropoff location for each component in a given build phase relative to the staging location of its parent assembly.

We begin by constructing each build phase subplan independently. The idea is to select the dropoff locations so as to minimize the distance between each component's dropoff location and its final configuration in the assembly, subject to the constraints that (a) the transport units will not overlap with each other if they simultaneously occupy their prescribed dropoff zones, and (b) the transport units will not overlap with the partial assembly. We also want to ensure that no transport unit will have to wait for another to move before it can access its dropoff location. We select the dropoff locations by solving a convex radial layout optimization problem of the form

\begin{align}
\qquad \qquad & \underset{{\CompAngle{1:n+1}}}{\text{minimize}} &  & \sum_{i = 1}^{n} (\CompAngle{i} - \DesiredCompAngle{i})^2 \label{eqn:ring_opt_obj} \\
& \text{subject to}
& & \CompAngle{i+1} - \CompAngle{i} \geq \HalfWidth{i} + \HalfWidth{i+1}, \ i \in 1{:}n \label{eqn:ring_opt_overlap} \\
& & & 0 \leq \CompAngle{i} \leq 2\pi, \ i \in 1{:}n \\
& & & \CompAngle{n+1} - \CompAngle{1} = 2\pi, \ i \in 1{:}n, \label{eqn:ring_opt_dummy}
\end{align}

where the decision variables $\CompAngle{1:n}$ denote the angular coordinates of the $n$ components' dropoff locations relative to the assembly, $\DesiredCompAngle{i}$ represents the angular coordinate of the goal configuration of component $i$ in the assembly, $\CompRadius{i}$ denotes the radius of component $i$'s bounding cylinder, and $\HalfWidth{i}=\arcsin(\CompRadius{i}/(\CompRadius{i}+\hat{\AssemblyRadius{}}))$ is the radial “half width” of component $i$ (half the width of component $i$'s “slice of the pie”), where $\hat{\AssemblyRadius{}}$ represents the radius of the assembly bounding cylinder. The $n$ components are first sorted in order of increasing $\DesiredCompAngle{}$, so the non-overlap constraints around the rim of the assembly cylinder can be encoded in the convex form of <ref>.
The constraint in <ref> is a “wrap around” constraint that uses the dummy variable $\CompRadius{n+1}$ to apply the non-overlap constraint between component $n$ and component $1$. A radial layout problem is shown in <ref>.

every node/.style=inner sep=0.5pt,outer sep=0pt,
boundingcircle/.style=circle,outer sep=0pt,inner sep=0pt,
(0,0) – (0:4.25cm);

45 0.8cm1.8cm0.501

333    1.00cm1.75cm4.25cm1.35cm51.030.2cm
287    1.25cm1.75cm4.25cm1.35cm40.830.2cm
200    0.75cm1.75cm4.25cm1.35cm30.820.2cm
130    1.10cm1.75cm4.25cm1.35cm20.650.2cm
45     1.00cm1.75cm4.25cm1.35cm10.500.2cm

[assembly,minimum size=3.5cm] (a) at (0,0) ;

An example solution to a radial layout optimization problem. Circles $1$, $2$ and $3$ are placed precisely at their respective desired orientations relative to the center circle. Circles $4$ and $5$, however, are forced to split the difference because they would overlap if placed at their desired orientations.

The bounding cylinder of an assembly is dynamic; it may expand with each build step as more components merge into the structure. For each radial layout optimization iteration, the initial bounding cylinder corresponds to the assembly's state before that particular build step. A build phase staging area is established for each build phase subplan, and it's designed to be the smallest possible cylinder that encompasses: (1) the current state of the assembly's bounding cylinder. (2) all designated drop-off zones, and (3) the staging area from the preceding build step (for the assembly's inaugural build phase, this previous staging area does not exist).

When the bounding cylinder of the assembly doesn't provide enough circumference to accommodate all components, a multi-tiered optimization process becomes essential. We accomplish this by using component prioritization and solving the radial layout problem iteratively. Components are ranked based on their build step sequence and their respective radii, $\CompRadius{}$. Early-stage build components are given spatial priority (positioned closer to the assembly). The maximum feasible set of components that can surround the current bounding cylinder is determined. A radial layout optimization then occurs for this subset of components. Once placed, we recompute the bounding cylinder to include these new drop-off zones and iterate until all components are placed. This layered structuring efficiently uses the factory floor, especially as the assembly and component counts increase.

Following the formulation of all build phase subplans, it is time to position each assembly in relation to its parent. Every leaf assembly (assemblies that lack child assemblies) has its staging area earmarked as its construction zone. We then move up the assembly tree (from initial objects to final assemblies), defining the construction zone of each parent assembly by solving a radial layout optimization problem. In these layout problems, the target angle $\DesiredCompAngle{}$ of each child is defined by the angle of the dropoff zone of that child relative to its parent assembly.

Tractor staging plan with no buffer ($20$ parts, $8$ assemblies).

Tractor staging plan with buffer ($20$ parts, $8$ assemblies).

King's Castle staging plan with no buffer ($761$ parts, $70$ assemblies).

Staging plans for the Tractor and King's Castle projects. Red circles represent the staging areas of the assemblies, blue circles are the final bounding cylinders of the assemblies, and green circles represent the dropoff zones for assembly components. Gray circles are added to show how the nested staging areas fit around each other.

<Ref> shows two staging plans for the tractor project and one staging plan for the King's Castle project (discussed in more detail in <ref>). <Ref> is constructed precisely as described above while <ref> is constructed using the same process, except that an extra buffer radius is added to each construction zone when choosing the assembly staging locations. During our simulations, we found that a buffer can help avoid a crowded workspace and reduce the burden on the collision avoidance logic. King's Castle is composed of $70$ assemblies and $761$ parts. This staging plan is an example where using layered concentric rings results in more efficient use of the factory space versus expanding a single ring to fit all assemblies. The dropoff zones appear to overlap with each other and with bounding circles. This phenomenon is an artifact of displaying all dropoff zones on one image regardless of time. The dropoff zones are also deconflicted based on the stage of the assembly.

§ TEAM FORMING AND TASK ALLOCATION

With a global staging plan that defines where all assemblies will be built, collected, and transported, the next task is to determine which specific robots will be involved in the transport of each object or assembly.

§.§ The Operating Schedule

An operating schedule $\ProjectSchedule = (\ScheduleVertices,\ScheduleEdges)$ is a directed acyclic graph (DAG) <cit.>. Each vertex $\vtx \in \ScheduleVertices$ corresponds to a discrete high-level event or activity.
An edge $(\vtx \rightarrow \vtxTWO) \in \ScheduleEdges$ denotes a precedence constraint, requiring that the activity associated with $\vtx$ must be completed before the activity associated with $\vtxTWO$ may begin. In our setting, the operating schedule includes the following node types:

* $\ObjectStart{}$
defines the initial state of an object.

* $\RobotStart{}$
defines the initial state of a robot.

* $\RobotGo{}$
defines a navigation task for a single robot from one location to another.

* $\AssemblyStart{}$
is a checkpoint node that must be passed before work may begin on an assembly.

* $\OpenBuildStep{}$
is a checkpoint at which the referenced build step becomes active. This checkpoint is reached for the initial build step of an assembly as soon as the  checkpoint is passed. For each subsequent build step, the  checkpoint is reached as soon as the previous build step has been completed.

* $\FormTransportUnit{}$
defines the task of loading a payload onto a team of robots in formation. This task may only begin when the robots are in carrying formation. During the  task, the robots remain in place as the payload is lowered into its carrying configuration.

* $\TransportUnitGo{}$
defines the task of transporting a payload to its dropoff zone. During transport the robots and payload remain in rigid formation.

* $\DepositCargo{}$
defines the task of unloading a payload from a transport unit. The robots remain in formation until the payload has been lifted into its staging configuration, at which time the transport unit disbands and the robots are free to break from formation and attend to other tasks.

* $\LiftIntoPlace{}$
defines the task of moving an assembly component from its staging configuration to its target configuration in the assembly. This task is accomplished without participation of any robots. We assume that a manipulator robot is available to move the component from its staging configuration to its final configuration.

* $\CloseBuildStep{}$
is a checkpoint at which the build step is completed. This checkpoint is reached once all  tasks associated with the referenced build step have been completed.

* $\AssemblyComplete{}$
is a checkpoint that marks an assembly as complete, meaning that it is ready to be collected by a transport unit.

* $\ProjectComplete{}$
is a checkpoint marking the project as complete.

§.§ Task allocation and Team Forming as a Graph Repair Problem

In the original task assignment formulation of <cit.>, a single-robot-per-task structure is hard-coded into the  constraints. In that work,  encoded the decision variable as a binary assignment matrix $A \in \textbf{B}^{(n+m) \times m}$, where $n$ is the number of robots, $m$ is the number of assignments, and $A_{ij}=1$ indicates that robot $i$ is assigned to transport object $j$. The first $n$ rows of $A$ corresponded to real robots while the last $m$ rows corresponded to the robots after they performed a previous assignment. For example, if $A_{ij}=1$ and $A_{j+n, k}=1$ then robot $i$ is assigned to deliver object $j$ and then assigned to deliver object $k$. Hence this formulation cannot be directly applied to our setting where robots are frequently required to work together as part of a transport unit.

The partial schedule Tractor operating schedule. This schedule encodes all tasks that need to be performed and the precedence constraints between them. The partial schedule does not yet encode any assignments of robots to tasks.  and  nodes are hidden to emphasize the structure of the transport tasks.

We introduce a more generic task assignment  formulation that makes it straightforward to deal with arbitrary project schedule structures—including those that incorporate collaborative transport tasks with varying numbers and configurations of robot teams. Our new formulation can be thought of as a graph repair problem: an initial graph is specified, but some required edges (in our setting, the assignment edges) are missing from the graph. A solver must determine where to add edges so as to satisfy the problem constraints and minimize some performance objective (in our setting, the makespan or, for multi-head projects, the sum of makespans).

Instead of solving for an assignment matrix, we solve for the adjacency matrix $\adjacencyMatrix{}{}$ of the project schedule, which directly encodes the edges of the project schedule. That is, the adjacency matrix $\adjacencyMatrix{}{}$ is the symmetric $|\ScheduleVertices| \times |\ScheduleVertices|$ matrix encoding of the adjacency relationships in our schedule graph

\begin{equation}
\adjacencyMatrix{i}{j} =
\begin{cases}
1 & \text{if } (i \rightarrow j) \in \ScheduleEdges \\
0              & \text{otherwise}.
\end{cases}
\end{equation}

We first specify an initial schedule graph by adding edges corresponding to the various transport tasks. The structure of this initial schedule encodes the partial ordering of all tasks that need to be accomplished. However, the initial schedule is missing the assignment edges, which encode the assignments of tasks to robots. The sets of allowable edges to and from a given node are encoded by the helper functions $\EligiblePredecessors$ and $\EligibleSuccessors$, respectively. The sets of required edges to and from a given node are defined by the functions $\RequiredPredecessors$ and $\RequiredSuccessors$, respectively. The suffixes $\textsc{-Pred}$ and $\textsc{-Succ}$ are short for predecessors and successors.
A graph is valid if and only if the predecessors and successors of each node form supersets of the respective $\textsc{Required-}$ sets and subsets of the respective $\textsc{Eligible-}$ sets. In other words, each node must have at least the required number of edges to and from the right types of nodes, and no more than the allowable number of edges to and from the right types of nodes. The outputs of these four functions for each type of schedule node are shown in <ref>.
The initial schedule for the tractor project is shown in <ref>.

Since some transport units have multi-robot teams, it is necessary to identify which role (i.e., which carrying position) a given robot is being assigned to. We provide this extra information by adding  nodes. For each carrying position in a transport unit, one  node is added as a predecessor to the associated  node, and one is added as a successor of the associated  node. Each placeholder  node stores the destination or origin of its associated carrying position. These placeholder nodes are omitted from <ref> so as not to distract from the structure of the transport tasks. However, they are included in the visualization of the assembly $6$ subgraph in <ref>. In this subgraph, there is a  node as a predecessor of the  node for object $15$ and two  nodes as predecessors for the  node for object $14$ (this object requires $2$ robots for transport). Similarly,  nodes follow the $\DepositCargo{}$ nodes for those objects as well.

Assembly $6$ subgraph of the partial Tractor operating schedule. Nodes associated with a particular object or assembly are annotated with the ID of that object/assembly. Several free - pairs are also shown, emphasizing that tasks have not yet been allocated to specific robots.

Required predecessors and successors for schedule node types. The asterisk denotes that the number of predecessors/successors for a given type can vary between instances of that node type.

2*Node Type     2cEligible $/$ Required

Predecessors     Successors

$/$    $^*$

$^*$     $/$

$/$, $^*$

,     , $^*$

Given an initial schedule (e.g. <ref>) and the helper functions as defined by <ref>, the new  formulation can be written as

where <ref> defines the sum-of-makespans objective, $\StartTime[]$ and $\CompletionTime[]$ encode the start and end times, respectively, for all vertices,
<ref> encodes all existing edges,
<ref> disqualifies “illegal” edges, and
<ref> prevents any single edge from creating a cycle in the graph.
It is still possible for multiple added edges to create a cycle, but this does not occur in solutions because it has infinite cost. <Ref> ensure that each vertex has at least the required number of incoming and outgoing edges,
<ref> ensure that each vertex has no more than the maximum allowable number of incoming and outgoing edges, and
<ref> enforces the duration of each vertex.
<Ref> encode “big $M$” inequality constraints that are activated/deactivate by the value of the associated binary variable—
<ref> enforces precedence constraints between vertices only if there is an edge between them, and
<ref> encodes the duration of vertex $i$ if that vertex is updated by adding an edge from $\idxA$ to $\idxB$ ($\processtime[\idxA](\idxB)$ encodes the duration if the edge is added). This last constraint is necessary because the duration of a  node depends on its destination (which is defined by the successor of the  node).

§.§ Comparing Matrix Formulations

If we consider the operating schedules that arise in the original  formulation of <cit.>, we recognize that the size of a schedule's adjacency matrix is greater than the size of the assignment matrix used to create the schedule. Hence, the number of discrete and continuous optimization variables is greater in an adjacency matrix  formulation than in a comparable assignment matrix  formulation. This prompts the question, “how much does solver runtime increase with the adjacency matrix formulation compared to the original assignment matrix formulation?”
To quantify the slowdown that occurs when solving an “assignment ” vs. an “adjacency ”, we evaluate three  variants:

*  is the original task assignment  formulation proposed by <cit.>.

*  is the new, generic  formulation described above.

*  implements the same  formulation as , but employs sparse variable containers and a pre-processing routine that instantiates optimization variables only for allowable edges.

Since  is limited to single-robot-per-task settings, we compare these three  variants on the  subproblems of the original  problem set used for the experiments in <cit.>. In our current problem setting, we require the added flexibility to allow for teaming of robots to transport objects. We evaluate the different approaches in a single-robot-per-task setting to demonstrate the computational cost associated with the increased flexibility.

node distance = 0.1cm and 0.1cm,
inner sep = 0pt,
outer sep = 0pt,
/pgfplots/label style = font=,
/pgfplots/legend style = font=,
/pgfplots/every axis/.append style = ymajorgrids,
/pgfplots/ymax = 100,
/pgfplots/ymin = 0.02,
[] (a) ;
[above = of a] (a title)  Runtime (s);
[left = of a] (b) ;
[above = of b] (b title)  Runtime (s);

Absolute runtime plotted for  (left) and  (right).

node distance = 0.1cm and 0.1cm,
inner sep = 0pt,
outer sep = 0pt,
/pgfplots/label style = font=,
/pgfplots/legend style = font=,
/pgfplots/every axis/.append style = ymajorgrids,
/pgfplots/ymax = 100,
/pgfplots/ymin = 1.0,
[] (a) ;
[above = of a] (a title) / Runtime Ratio;
[left = of a] (b) ;
[above = of b] (b title) / Runtime Ratio;

Runtime ratio plotted for  (left) and  (right) compared to . Some results for high $\numtasks$, low $\numrobots$ categories are not very meaningful because both  and the  variant reached the time limit.

The absolute runtimes for  and  are plotted in <ref>. <Ref> shows how the distribution over runtime ratios for / and / vary between problem classes. <Ref> summarizes the runtime ratios of the two  variants aggregated across all problem classes. Both variants are slower than  and the slowdown becomes more pronounced for $\numtasks \gg \numrobots$. However,  scales better than .

Histograms summarizing the distributions of runtime ratios for / (left) and / (right) aggregated over all problem instances.

We have explored several pre-processing approaches to reduce the problem size (and hence, the solve time) of the adjacency matrix  formulation.  represents the most successful of those approaches. Though the increase in runtime compared to  is unfortunate, it is a necessary burden in exchange for the added flexibility to support robot teaming for transport tasks in our current problem set. We hope to explore alternative formulations and extensions of the  formulation to mutli-robot-per-task scenarios in the future.

§.§ Modified Greedy Task Allocation

We demonstrated that the  solver struggles when $\numtasks \gg \numrobots$. This effect becomes even more pronounced for  than for . For very large assemblies, optimal task assignment is intractable. This does not necessarily mean that the  solver cannot be used for large assemblies. On the contrary, it is frequently the case that the  solver identifies multiple feasible—though not necessarily optimal—solutions in its search for a certifiably optimal solution. If at least one such solution has been found before the time or iteration limit is reached, the solver will return the best feasible solution found so far along with an upper bound on the optimality gap.

Nevertheless, we also wish to have a suboptimal task assignment algorithm with runtime guarantees. To this end, we propose a greedy precedence-constrained coalition formation () algorithm (<ref>) that accounts for collaborative transport tasks and the precedence constraints associated with build phases and nested subassemblies. This algorithm produces a suboptimal, yet feasible solution. In scenarios were time allows, we can then use this feasible solution to warm-start our optimization process for the  problem.

adds assignments for an entire transport unit (which may include multiple agents) at each iteration by a greedy selection of the transport unit-task pair. The transport unit is selected via the EarliestArrival subroutine of  (<ref>), which is similar to the earliest completion first algorithm proposed by <cit.> for multi-agent coalition forming with spatial and temporal constraints.

For each available transport task, a candidate transport unit is selected by greedily assigning robots to the designated carrying formation positions. The transport unit's lower bound pickup time is the maximum over the candidate robot team of the time required for each robot to reach its assigned pickup configuration. The transport unit and associated robot team with the lowest pickup time are added to the schedule.

Greedy assignment algorithm for collaborative transport tasks.

[1]

$\ActiveAssemblies \gets $ all assemblies in project
$\AvailableRobots \gets $ all robots
$\AvailableComponents \gets $ all raw materials
$\ActiveAssemblies$ is not empty
$\TeamAssignment \gets nothing$
$t_{\min} \gets \infty$
$target \gets nothing$
$assembly \in \ActiveAssemblies$
$\cargo \in assembly.active\_step.unassigned\_components$
$\cargo \in \AvailableComponents$
$\goals \gets \cargo.pickup\_positions$
$\assignmentlist \gets \emptyset$
$\ft \gets 0$
$\goals$ is not empty
$(robot,goal), t \gets \textsc{EarliestArrival}(\AvailableRobots,goals)$
$\ft \gets \max(\ft,t)$
$\ft \geq t_{\min}$
$\assignmentlist \gets \assignmentlist \cup (robot,goal)$
$\AvailableRobots \gets \AvailableRobots \setminus \{robot\}$
$\goals \gets \goals \setminus \{goal\}$
$(robot,goal) \in \assignmentlist$
$\AvailableRobots \gets \AvailableRobots \cup \{robot\}$
$\ft < t_{\min}$
$\TeamAssignment \gets (\cargo,\assignmentlist)$
$t_{\min} \gets \ft$
$target \gets assembly$
Add $\TeamAssignment$ to operating schedule
all component transport tasks for $target.active\_step$ are assigned
$target.active\_step = target.terminal\_step$
$\ActiveAssemblies \gets \ActiveAssemblies \setminus \{target\}$
$\AvailableComponents \gets \AvailableComponents \cup \{target\}$
$target.active\_step \gets $ next build step

Earliest Arrival Subroutine called by .

[1]
$assignment \gets nothing$
$t_{\min} \gets \infty$
$robot \in robots$
$goal \in goals$
$t \gets $ earliest time at which $robot$ can reach $goal$
$t < t_{\min}$
$assignment \gets (robot,goal)$
$t_{\min} \gets t$
$assignment, t_{\min}$

In the original  setting, an unassigned task was considered available if all of its predecessors had been assigned. In our setting, availability of a task additionally requires that its build step be active. We require this modification because each  node is preceded by both a  node and an  node. Hence, the  task may not begin until its associated build phase becomes active. Therefore, if  were to prematurely assign all robots to “downstream” build phases, it would essentially consign the whole fleet to wait with their cargo indefinitely (because no robots would be available to attend to the previous build phases). Hence,  limits the set of available tasks at a given assignment iteration to the tasks that belong to active build steps.

§ PLAN EXECUTION AND COLLISION AVOIDANCE

With a staging plan defined, all transport tasks allocated to robots and robot teams, and the transport units configured, we now need to execute the construction plan. This requires robots to move through the environment, collecting, transporting, and depositing their cargo, all while avoiding collision with each other and the various assemblies under construction throughout the factory.

At any given moment in the construction process, a subset of the assembly build phases are active. Each active staging area is treated as a “soft” obstacle for all agents that are not directly involved in the activities of that staging area. More precisely, an agent should only enter an active staging area if (a) the agent's current task requires it to enter the staging area, and (b) the build step associated with the task is active. Otherwise, an agent may only enter a staging area if “pushed” into the staging area by another agent. Recall that the staging area for each build phase is defined as the minimum radius cylinder that fully encloses the assembly's current bounding cylinder, all dropoff zones associated with the build step, and the staging area of the previous build phase. Thus, when a non-terminal build phase is completed, a larger staging area becomes active. The robot fleet must therefore navigate through an environment where virtual obstacles appear and disappear over time.

One approach would be to precompute an execution plan, consisting of the trajectories of all agents from time zero to the completion of the project. Such an approach would be analogous to the pre-execution route planning method used in <cit.>. A pre-computation approach is attractive because it allows the possibility of finding—with an appropriate global optimization method—a makespan-optimal execution plan (that is, optimal with respect to the construction plan). <cit.> propose a prioritized multi-robot trajectory optimization scheme that could be applicable here. However, a long-horizon plan can easily break down due to delays caused by unforeseen disturbances in the environment. Moreover, a precomputation approach would need to account for the appearances and disappearances of virtual obstacles, which in turn depend on the times at which different tasks are completed.

Instead of precomputing an execution plan, we propose a distributed online navigation strategy wherein each agent follows a reactive velocity control policy where we use the term agent to mean either a robot or a transport unit.

The reactive policy consists of three layers. The first layer is a simple switching controller that plans a nominal velocity vector meant to move the agent toward its goal while avoiding active staging areas that the agent should not enter.
The second layer of the reactive policy adds a dispersion component—based on weighted, pairwise repulsive artificial potential fields—to the nominal velocity. The resulting velocity vector is called the preferred velocity.
The third and final layer is a collision-avoidance controller that computes an updated velocity vector if the preferred velocity vector would lead to collision with other agents. The output of this final layer is the commanded velocity.

The three-level distributed velocity controller.

$\vnom \gets \textsc{\TangentBugPolicy}(\x)$
$\vpref \gets \textsc{\DispersionProtocol}(\x,\vnom)$
$\vcom \gets \textsc{\RVO}(\x,\vpref)$

§.§ Level 1: Modified Tangent Bug Algorithm

Given the current set of staging area obstacles, each robot computes its own nominal velocity using a variation of the Tangent Bug algorithm <cit.>. The agent's waypoint is initialized as its goal location. If the straight path from the agent's current position toward the waypoint is unobstructed up to some lookahead distance, the nominal velocity is simply set to a vector pointing along that path. If the robot is far from the goal, the vector's magnitude is the maximum permissible speed of that agent, as defined by <ref>. If the robot is within a single time step of reaching the goal, the velocity is scaled so that the robot will not overshoot the goal.

If the path from start to waypoint is blocked by one or more obstacles at a closer proximity than the lookahead distance, the closest of these obstacles is designated as the target. The waypoint is set to the right-hand tangent point (i.e., the robot aims to “skim” the obstacle by passing along its right side) of the circle created by inflating the target by the agent's own radius. If the path to this new waypoint is obstructed by another obstacle, the waypoint is instead set to the first point on the inflated target's boundary that the agent would reach if it were to travel straight toward its goal location. The nominal velocity is then set as a vector of maximum permissible magnitude in the direction of the waypoint.

If the agent's position is within some $\epsilon$ of the inflated target's boundary, the agent selects a nominal velocity that will move it along the boundary in the counter-clockwise direction. When the agent reaches a point on the boundary at which the target no longer obstructs a straight path to the agent's goal, the target is discarded and the agent selects a new waypoint.

As agents switch tasks and new build steps become active, an agent will occasionally find itself within a staging area in which it is not permitted to be. In this case, the agent simply selects a velocity that follows the shortest path to the outside of the staging area. In the event that the agent is at the exact center of the staging area, its exit path points in the direction of the agent's goal.

Our modified tangent bug algorithm always leads to counter-clockwise detours around obstacles. This helps to reduce congestion that would occur if two agents tried to navigate around the same obstacle in opposite directions. That said, the nominal velocities computed by the tangent bug policy might lead to collisions if executed directly by the agents.

The modified tangent bug controller.

$\target \gets$ first obstacle intersected by ray $\bugline$
$\target \neq nothing$
$\waypoint \gets$ point at which $\bugline$ first intersects $\target$
$d \gets$ signed distance from $\bugpos$ to boundary of $\target$
$d \approx 0$ $\bugpos$ is on boundary of $\target$
$mode \gets \textsc{move\_ccw\_along\_boundary}$
$d > 0$ $\bugpos$ is outside of $\target$
$d > \bugradius$
$mode \gets \textsc{move\_toward\_waypoint}$
$o \gets$ first obstacle intersected by ray $\bugpos \rightarrow \waypoint$

$o = nothing$
$mode \gets \textsc{move\_toward\_right\_hand\_tangent\_point}$
$mode \gets \textsc{move\_toward\_waypoint}$
$d < 0$ $\bugpos$ is inside of $\target$
$mode \gets \textsc{exit\_target}$
$\waypoint \gets \buggoal$
$mode \gets \textsc{move\_toward\_waypoint}$

§.§ Level 2: Prioritized Dispersion Protocol

The second level of the velocity controller defines active agents as follows: a transport unit is designated as active if it is carrying cargo that belongs to an active build step. A robot is designated as active if the next task in the robot's itinerary is to join a transport unit whose cargo (a) is available for pickup and (b) belongs to an active build step.

When an active agent reaches the staging circle within which its goal lies, the agent may enter immediately. Inactive agents, on the other hand, must wait outside of the circle. When multiple inactive agents are waiting outside of a circle, there may not be enough room for an active agent to make its way through the crowd. Intuitively, inactive agents need to make room for an active agent when the active agent needs to pass.

The prioritized dispersion protocol causes inactive agents to move away from other agents when an active agent is close. This allows active agents to “push through” crowds of inactive agents. The dispersion protocol is based on virtual pairwise repulsive potential fields. Each inactive agent is subject to repulsive fields emanating from other nearby agents. A dynamic priority scheme (<ref>) is used to determine higher priority (lower $\alpha$ is higher priority). An agent with higher priority is not affected by the repulsive fields of other agents.
The repulsive force exerted by agent $j$ on agent $i$ is defined by

\begin{align}
\potentialfield_1(\x_i, \x_j,\agentRadius_i,\agentRadius_j,\bufferRadius_j) &= \max(0, \bufferRadius_j + \agentRadius_i + \agentRadius_j - \Vert \x_i - \x_j \Vert), \label{eqn:cone_potential} \\
\potentialfield_2(\x_i, \x_j,\agentRadius_i,\agentRadius_j,\bufferRadius_j) &= \max(0, 1 / (\Vert \x_i - \x_j \Vert - \bufferRadius_j) - 1 / (\agentRadius_i + \agentRadius_j), \label{eqn:barrier_potential} \\
\potentialfield(\cdot) &= \potentialfield_1(\cdot) + \potentialfield_2(\cdot), \label{eqn:composite_potential} \\
f &= \nabla_{\x_i} \potentialfield(\x_i, \x_j,\agentRadius_i,\agentRadius_j,\bufferRadius_j) \label{eqn:repulsive_force}
\end{align}

where $\x_i$ and $\x_j$ denote the agents' position vectors, $\agentRadius_i$ and $\agentRadius_j$ denote the radii of the agents' bounding spheres, $\bufferRadius_j$ denotes the field radius of agent $j$, <ref> encodes a cone-shaped potential $\potentialfield_1$, <ref> encodes a log barrier-shaped potential $\potentialfield_2$, <ref> defines the overall potential $\potentialfield$ as the sum of the cone and barrier potentials, and <ref> defines the repulsive force $f$ as the gradient of the potential field with respect to $\x_i$.

The field radius $\bufferRadius_j$ determines how far the potential field extends from agent $j$. For a small value of $\bufferRadius_j$, agent $j$ only exerts a repulsive force on agents that are very close to it. Increasing $\bufferRadius_j$ has the effect of expanding the neighborhood in which other agents are affected by the repulsive force from $j$. The value of $\bufferRadius_j$ depends inversely on the distance from agent $j$ to the nearest active agent, according to

\begin{align}
& d_j = \min_{k \in active\_agents} \Vert \x_j - \x_k \Vert - (\agentRadius_k + \agentRadius_j), \label{eqn:dist_to_nearest_active_agent} \\
& \bufferRadius_j = \min(\maxbufferRadius,\bufferMultiplier / d_j), \label{eqn:define_buffer_radius}
\end{align}

where $d_j$ denotes the distance from agent $j$ to the nearest active agent, $\bufferRadius_{\textsc{max}}$ is an upper bound on the field radius, and $\bufferMultiplier$ is a scaling hyperparameter (we use $\maxbufferRadius=2.5\robotradius$ and $\bufferMultiplier=\robotradius$). If agent $j$ is an active agent, its field radius is equal to $\maxbufferRadius$.

Note that the force exerted on $i$ by $j$ is not necessarily equal in magnitude to the force exerted on $j$ by $i$. As previously noted, active agents are not affected by the potential fields. Between inactive agents, the field radius will be larger for the agent that is closer to an active agent.

The overall virtual force experienced by agent $i$ is the sum of the forces exerted by all other agents within its vicinity. The preferred velocity of agent $i$ is computed by blending the nominal velocity with the virtual force, and clipping the resulting velocity vector if its magnitude exceeds the maximum permissible speed:

\begin{align}
& \hat{\vel} = a \vnom - b  \sum_j \nabla_{\x_i}\potentialfield(\x_i, \x_j,\agentRadius_i,\agentRadius_j,\bufferRadius_j) \\
& \vpref = \frac{\vel}{\Vert \hat{\vel} \Vert} \min(\vel_{\textsc{max}}, \Vert \hat{\vel} \Vert)
\end{align}

where $a$ and $b$ are blending coefficients. We use $a=1$ and $b=1$ in our experiments.

§.§ Level 3: Generalized RVO with Dynamic Prioritization

The final layer of the velocity controller is based on reciprocal velocity obstacles (RVO).
A velocity obstacle is created by translating the relative position vector between two robots and the desired velocity vector of the first robot into a set of two inequality constraints on the velocity of second robot. Any velocity vector in the second robot's velocity envelope that satisfies either of these constraints will not lead to collision with the first robot. Reciprocal velocity obstacles extend the velocity obstacle concept by having pairs of robots share responsibility for avoiding collision with each other. Generalized reciprocal velocity obstacles extend this notion further by allowing two agents to share collision-avoidance responsibility unevenly. The parameter $\alpha^{i}_{j} \in [0,1]$ denotes the share of the responsibility that agent $i$ takes to avoid collision with agent $j$ (agent $j$'s share of the responsibility is $\alpha^j_i = 1 - \alpha^i_j$) <cit.>.

We use generalized RVO with a dynamic priority scheme (<ref>) that assigns to each agent its own non-negative $\alpha$-value. Each time any agent completes a task, the $\alpha$-values of all agents are recomputed. For any two agents $i$ and $j$, we compute $\alpha^i_j = \alpha_i / (\alpha_i + \alpha_j)$. If $\alpha_i = \alpha_j = 0$, we simply set $\alpha^i_j$ to $0.5$. The priority scheme is designed to prioritize robots and transport units that are engaged in active build phases, so that they can more easily push past other agents who are waiting for their own build phases to begin. Within the active build phases, transport units are given higher priority than unladen robots because they are “ahead” of the robots in completing their tasks (the unladen robots are on their way to form transport units).

The dynamic priority scheme for setting an agent's $\alpha$-value (priority).

$\rvoagent$ is a transport unit
current task is $\FormTransportUnit$ or $\DepositCargo$
$\alpha \gets 0$ must remain stationary
task is $\TransportUnitGo$
$cargoScale \gets cargoID / (10 \cdot maxCargoID)$ provide priority based on cargo
current task's build phase is active
$\alpha \gets 0 + cargoScale$
$\alpha \gets 1$
$\rvoagent$ is an unladen robot
current task's build phase is active
current task's cargo is ready for pickup
$\alpha \gets 0.1$
$\alpha \gets 0.5$
$\alpha \gets 1$

§.§ Task Swapping

In some cases, a member of a transport unit is unable to reach its carrying position because other members of the robot team are already waiting in their assigned pickup locations. When such deadlocks occur, we simply allow the stuck robot to swap tasks with the nearest team member that is closer to the stuck robot's goal than the stuck robot.

§.§ Sit-And-Wait Subroutine for Inactive Agents

In experiments with the distributed execution controller described above, we find that inactive robots tended to oscillate, pushing each other back and forth while tightly gathered around a staging area. To avoid this needless dancing, we added a sit-and-wait subroutine that sets the nominal velocity to zero for inactive agents within a specific distance from their destinations. With this feature enabled, inactive agents within stopping range of their goal will not move unless the $\DispersionProtocol$ or $\RVO$ policy layers require it to deviate from its zeroed nominal velocity. This prevents most of the undesirable oscillations observed without the sit-and-wait feature, though some oscillation is still observed when an inactive robot far from its goal tries to move through a large group of other waiting inactive agents.

§ DEMONSTRATIONS

We demonstrate our system's performance in a simulated environment, which is shown in <ref>. The initial robot positions are drawn from a uniform distribution over a grid of locations around the center of the environment. The final assembly staging area is always at the origin. All assemblies are constructed in the air above the robots. When a transport unit deposits its cargo, the cargo rises into the air until it reaches its pre-lift-into-place configuration. Once the cargo reaches this location, the task is complete and then the item is moved into its location within the assembly. The initial locations of all raw materials are placed at random locations outside of the staging areas dictated by the staging plan.

All simulator code is written in Julia <cit.> and the optimization was performed with Gurobi <cit.>. Rendering is done by MeshCat.[<https://github.com/rdeits/MeshCat.jl>] We use Julia's PyCall package to access the Python bindings to a modified version of the RV02 Library[The RVO2 C++ Library is available at <https://gamma.cs.unc.edu/RVO2>] (our modified RVO2 library incorporates the $\alpha$ prioritization levels described in <ref>).

We demonstrate our framework on nine different assemblies which span different complexities in terms of number of parts and assemblies (<ref>):

* Tractor: The tractor project that has been used as a running example throughout this paper. This model is based on  model 10708, Green Creativity Box. It consists of $20$ pieces organized into $8$ assemblies.

* X-Wing Mini: Based on  model 30051, X-wing Fighter - Mini, from the  Star Wars collection. It consists of 61 parts organized into $12$ assemblies.

* Imperial Shuttle: Based on  model 4494, Imperial Shuttle - Mini, from the  Star Wars collection. It consists of $84$ parts organized into $5$ assemblies.

* AT-TE Walker: Based on  model 20009, AT-TE Walker - Mini, from the  Star Wars collection. AT-TE Walker consists of $100$ parts organized into $22$ assemblies.

* X-Wing: Based on  model 7140, X-wing Fighter from the  Star Wars collection. X-Wing is a more complex assembly than X-Wing Mini, with 309 parts organized into 28 assemblies.

* Airplane: Based on  model 3181, Passenger Plane, from the  City collection. It consists of $326$ parts organized into $28$ assemblies.

* Star Destroyer: Based on  model 8099, Midi-Scale Imperial Star Destroyer from the  Star Wars collection. It consists of $418$ parts organized into 11 assemblies.

* King's Castle: Based on  model 6080, King's Castle. This model consists of $761$ parts organized into $70$ assemblies.

* Saturn V: Based on  model 21309, NASA Apollo Saturn V. The Saturn V rocket has $1845$ pieces organized into $306$ assemblies.

Nine assemblies we use to test our algorithm with different levels of complexity.

§.§ Full Stack Simulations

For each assembly, we ran a full stack simulation with different parameters. The execution for all parts of the simulation occurred on a system using an Intel$^{\text{\textregistered}}$ Core$\text{\texttrademark}$ i9-9900KF processor and $\SI{64}{\giga\byte}$ of RAM.
Images from the Tractor and X-Wing Mini projects are shown in <ref> and <ref> respectively.

Screenshots from the Tractor construction in the simulated environment: (a) Components of a tire assembly are carried by two robots; (b) The chassis is transported by a team of four robots; (c) The rear axle is lifted into place, while some of the final components are seen on board robots in the background; (d) The final pieces of the Tractor assembly are lifted into place.

Screenshots from the X-Wing Mini construction in the simulated environment: (a) The bounding hyperrectangles of the subassemblies are shown at the assembly build locations (this snapshot was taken prior to the beginning of the simulation). (b) Essentially all of the robots are congregated around the penultimate staging area, waiting for their turn to enter; (c) A birds eye view shows the crowding from a different angle. The bounding hyperspheres for some of the transport units are shown to convey the tightness of the crowding; (d) A group of six robots waits in hexagonal carrying formation as the completed assembly is lowered into its carrying configuration.

<Ref> reports metrics from the simulation runs on all nine assemblies and various numbers of robots. The model names are listed with the number of parts and assemblies. The simulations in <ref> use  for task assignments and perform execution using the three components of the collision avoidance strategy discussed, , , and . The following metrics are used in <ref> and throughout this section:

* Transport Unit Configuration Time (T.U. Config): The total time spent configuring all transport units (<ref>).

* Staging Plan Generation Time (Staging Plan): The time spent generating the global staging plan (<ref>).

* Task Allocation Time (Assignment):  The time spent forming coalitions and allocating tasks (<ref>).

* Predicted Makespan: The predicted makespan of the project based on the output of the task assignment solution. This makespan is the metric used for the optimization and does not involve collision avoidance maneuvers.

* Execution Makespan: The makespan of the actual execution run. This value is longer than the predicted makespan due to the avoidance of staging circles and the collision avoidance logic.

* Execution Runtime (Runtime): The amount of time required to run the simulator to completion of the project. This time does not include the preprocessing steps.

The total preprocessing time of the three components listed using  assignment for each of the projects is less than three minutes. The entire construction plan for the two smallest projects is computed in less than a second, whereas the largest project (Saturn V with $250$ robots) takes approximately $2$ minutes and $49$ seconds. Task allocation is the largest preprocessing computational burden. Configuring transport units and the staging plan generation are independent of the number of robots and both are fast, taking less than three seconds for the largest project.

The distributed execution strategy successfully completes all projects. However, there are no guarantees to prevent deadlock. The combination of the control strategies we discussed can still cause deadlocks, especially as the buffer size between staging areas is reduced. We discuss potential improvement ideas in <ref>. We also note that it is clear from <ref> that the simulator runtime scales quite poorly with project size. This runtime is an artifact of our implementation strategy and not a factor of our distributed execution strategy. We currently are processing all agent and component actions and updates on a single thread. The runtime would improve by taking advantage of a multi-threaded simulation environment and implementing more efficient data structures.

§.§ Task Allocation Comparison

The  task allocation produced feasible solutions. To further evaluate the quality of the solutions, we compared  to the  and  with a  warm-start task allocation methods. An optimizer time limit was used with . All but Tractor with $15$ robots reached the optimizer time limit before finding an optimal solution. We used a time limit of 6000 for all problems except King's Castle and Saturn V where we used 12000. On Saturn V, the  formulation with a warm-start was unable to find a feasible solution to improve upon the  solution with a 12000 optimizer time limit. Therefore, we did not include Saturn V in the table.  with and without a warm-start were run with the Gurobi MIPFocus parameter set to focus on feasible solutions. The results of these experiments are provided in <ref>.

As expected,  outperformed  when it was able to find a solution. However, the increased performance comes at the cost of an increase in computation time, especially for larger projects. Using the  solution as a feasible warm-start for the  formulation improved the  solution and was able to find an improved feasible solution in all experiments except for Saturn V. These results suggest that  can provide quality solutions quickly, but when time allows, those solutions can be further refined when used as a feasible starting point for the  formulation using modern MILP solvers.

§ DISCUSSION AND CONCLUSION

As previously noted, our framework abstracts away many important details that would need to be considered in the real world. Here, we identify some of those considerations and point to the relevant literature and/or discuss how our approach could be extended in future work.

Our framework does not address the fine manipulation and geometric path planning required to piece together complex assemblies. The closest we come to addressing this is to have each robot deposit each assembly component on the side of the staging area that is closest to the component's destination configuration within the assembly. We assume, rather, that these planning and control tasks are handled by some lower-level system. As noted in <ref>, existing work in multi-scale manipulation and collaborative grasp planning is particularly relevant in this regard <cit.>.

Our method for configuring robot teams is based on a geometric heuristic. A more principled approach would consider factors like payload mass and mass distribution, structural properties, grasping locations, and the quality thereof. Existing work on multi-robot grasp planning offers a good starting point for the development of a more rigorous approach <cit.>.

Our staging plan layout procedure produces a global staging plan with at least one attractive property: the layout is such that each assembly can be transported in a straight path from its own staging area to its prescribed dropoff zone in the parent assembly's staging area without crossing through any other staging areas. However, even with the layered optimization approach, deeply nested assemblies quickly lead to an inefficient use of space. It is surely possible to achieve a more space-efficient layout. One approach might be to construct a Voronoi diagram from the circles, and “pull” all the staging errors toward each other as if connected by springs. This approach could result in a more compact construction zone without violating constraints on interstitial space or breaking the line-of-sight property mentioned above. Also, our use of cylindrical staging zones can be wasteful for certain geometries of parts and assemblies. For example, a long, skinny assembly should have a long, skinny (although inflated relative to the assembly) staging area. We point out that though our iterative layout approach was described in terms of circles and cylinders, it could easily be generalized to other geometric shapes. One particularly promising shape is the octagonal prism. With eight sides at fixed angular offsets from each other, the octagon can approximate round parts as well as skinny parts. Thus, it would be straightforward to adapt the radial layout optimization problem to an octagonal layout optimization problem. Another consideration is that our layout approach is based purely on the assembly specification, and does not account for the starting locations of raw materials. In a real factory, it is likely important to place some staging areas in close proximity to the place where their raw materials are stored.

Another important layout consideration is that our approach does not account for the temporal aspect of the assembly process. Staging areas only need to be separate from each other if they are being used simultaneously. In an environment with limited floor space, it might not be desirable or feasible to define a staging plan with no overlap between staging circles. Just as we allow deposit zones to overlap with the deposit zones from previous and future build steps, it would be useful to allow staging circles to overlap if their assembly construction timelines are far apart. Promising approaches to address these considerations might be found in the literature on facilities planning <cit.>.

Our three-layer distributed execution strategy works well in practice. In particular, the dispersion protocol is crucial to enable deadlock-free execution—our early experiments without the dispersion protocol (i.e, just +) were characterized by frequent deadlock due to crowding of inactive agents around the assembly staging areas. Task-swapping (<ref>) prevents deadlock that might otherwise occur when an agent is blocked from reaching its carrying position by other robots that are participating in the same transport unit. This idea might be extended to a full online task allocation and coalition-forming approach (i.e., assign tasks and form teams on the fly, rather than making all assignments before beginning execution). The sit-and-wait subroutine avoids most undesirable “dancing” behavior, but could surely be replaced by a more elegant solution.

It is important to note that we have not identified any theoretical guarantees on the performance of our execution strategy. Though our solution is effective for the projects considered, it may be vulnerable to edge cases that do not appear in our set of demo projects. Thus an important direction for future work is the development of continuous space-distributed execution strategies that are certifiably free from deadlocks. The concept of dynamic prioritization, which is present in the second and third layers of our distributed controller, is a promising starting point. Potential avenues for improvement include more sophisticated potential field methods, such as the method proposed by <cit.> for decentralized multi-robot caging and pushing of planar objects. Another approach would involve the definition of virtual highways in which agents would be required to move, along with rules about when and where agents could enter and exit the highway. This line of work could build on existing research in automated guided vehicles <cit.>.

The application of multi-robot systems in the domain of assembly and manufacturing has the potential to revolutionize the speed, efficiency, and adaptability of the production process. We have presented a proof-of-concept system for multi-robot assembly planning. Given a project specification that specifies an assembly tree and a set of build phases, our algorithm is capable of synthesizing and executing construction plans involving assemblies with hundreds of parts. This process includes planning the carrying configurations of robot teams that will move objects and assemblies through the factory, setting up staging zones where each assembly will be incrementally pieced together, assigning robots to both solo and collaborative transport tasks, and enabling the robots to execute the staging plan in a distributed manner. Our main contribution is the sum total of these components. We feel that our work lays a solid foundation for future studies in the domain of multi-robot assembly systems.

The authors would like to thank Ahmed Sadek, Mohammad Naghshvar, and the team at Qualcomm Corporate Research for their insightful feedback. This work was supported by Qualcomm, Siemens AG, by the National Science Foundation under grant No. DGE – 1656518.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

abstractBridging cultures that have often been distant, Julia combines expertise from the diverse helds of computer science and computational science to create a new approach to numerical computing. Julia is designed to be easy and fast and questions notions generally held to be "laws of nature" by practitioners of numerical computing: 1. High-level dynamic programs have to be slow. 2. One must prototype in one language and then rewrite in another language for speed or deployment. 3. There are parts of a system appropriate for the programmer, and other parts that are best left untouched as they have been built by the experts. We introduce the Julia programming language and its design-a dance between specialization and abstraction. Specialization allows for custom treatment. Multiple dispatch, a technique from computer science, picks the right algorithm for the right circumstance. Abstraction, which is what good computation is really about, recognizes what remains the same after differences are stripped away. Abstractions in mathematics are captured as code through another technique from computer science, generic programming. Julia shows that one can achieve machine performance without sacrificing human convenience.
journaltitleSIAM Review
titleJulia: A fresh approach to numerical computing
Julia,Numerical,Parallel,Scientific computing

journaltitleIEEE International Conference on Robotics and Automation (ICRA)
titleOptimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning

journaltitleIEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
titleMulti-Robot Assembly Sequencing via Discrete Optimization

journaltitleThe International Journal of Robotics Research
titleMulti-scale assembly with robot teams
Robotic assembly,distributed control,multi-scale assembly,multi-scale perception,robot teams,robotic manufacturing

Springer US

journaltitleAutonomous Robots
titleMulti-robot grasp planning for sequential assembly operations
family=Ani Hsieh,

abstractWe present a decentralized approach to multi-robot manipulation where the team of robots surround and trap an object and transport it, by dragging or pushing, to the goal configuration in an environment with obstacles. The proposed feedback controllers are obtained by sequentially composing vector fields or behaviors and are decentralized in the sense that robots do not exchange each other's state information. Rather, cooperative manipulation is achieved by relying solely on each robot's local information and a global knowledge of the task. We present computer simulations and experimental results obtained using our multi-robot testbed. ©2008 IEEE.
journaltitleIEEE International Conference on Robotics and Automation (ICRA)
titleMulti-robot manipulation via caging in environments with obstacles

abstractThe problem of planning for a robot that operates in environments containing a large number of objects, taking actions to move itself through the world as well as to change the state of the objects, is known as task and motion planning (TAMP). TAMP problems contain elements of discrete task planning, discrete–continuous mathematical programming, and continuous motion planning and thus cannot be effectively addressed by any of these fields directly. In this article, we define a class of TAMP problems and survey algorithms for solving them, characterizing the solution methods in terms of their strategies for solving the continuous-space subproblems and their techniques for integrating the discrete and continuous components of the search.
journaltitleAnnual Review of Control, Robotics, and Autonomous Systems
titleIntegrated Task and Motion Planning
Automated planning,Manipulation planning,Motion planning,Robotics,Task and motion planning
family=Gurobi Optimization, LLC,

titleGurobi Optimizer Reference Manual

abstractAssembly planning is the problem of finding a sequence of motions to assemble a product from its parts. We present a general framework for finding assembly motions based on the concept of motion space. Assembly motions are parameterized such that each point in motion space represents a mating motion that is independent of the moving part set. For each motion we derive blocking relations that explicitly state which parts collide with other parts; each subassembly (rigid subset of parts) that does not collide with the rest of the assembly can easily be derived from the blocking relations. Motion space is partitioned into an arrangement of cells such that the blocking relations are fixed within each cell. We apply the approach to assembly motions of several useful types, including one-step translations, multistep translations, and infinitesimal rigid motions. Several efficiency improvements are described, as well as methods to include additional assembly constraints into the framework. The resulting algorithms have been implemented and tested extensively on complex assemblies. We conclude by describing some remaining open problems.
titleA general framework for assembly planning: The motion space approach
Assembly planning,Assembly sequencing,Manufacturing,Motion space,Nondirectional blocking graph

Taylor & Francis

journaltitleInternational Journal of Production Research
titleMachine layout: an optimization and knowledge-based approach

journaltitleThe International Journal of Robotics Research
titleTangentBug : A Range-Sensor-Based Navigation Algorithm

journaltitleIEEE International Conference on Robotics and Automation (ICRA)
titleReal-time obstacle avoidance for manipulators and mobile robots

abstractWe present an automated assembly system that directs the actions of a team of heterogeneous robots in the completion of an assembly task. From an initial user-supplied geometric specification, the system applies reasoning about the geometry of individual parts in order to deduce how they fit together. The task is then automatically transformed to a symbolic description of the assembly-a sort of blueprint. A symbolic planner generates an assembly sequence that can be executed by a team of collaborating robots. Each robot fulfills one of two roles: parts delivery or parts assembly. The latter are equipped with specialized tools to aid in the assembly process. Additionally, the robots engage in coordinated co-manipulation of large, heavy assemblies. We provide details of an example furniture kit assembled by the system.
journaltitleIEEE International Conference on Robotics and Automation (ICRA)
titleIkeaBot: An autonomous multi-robot coordinated furniture assembly system

[Wiley, Econometric Society]

abstractTwo problems in the allocation of indivisible resources are discussed. Both can be interpreted as problems of assigning plants to locations. The first problem, in which cost of transportation between plants is ignored, is found to be a linear programming problem, with which is associated a system of rents that sustains an optimal assignment. The recognition of cost of interplant transportation in the second problem introduces complications which call for more laborious and largely unexplored computations and which also appear to defeat the price system as a means of sustaining an optimal assignment.
issn00129682, 14680262
titleAssignment Problems and the Location of Economic Activities

journaltitleJournal of Manufacturing Systems
titleDesign of reconfigurable manufacturing systems

abstractBounding spheres are utilized frequently in many computer graph- ics and visualization applications, and it is not unusual that the com- putation of the spheres has to be done during run-time at real-time rates. In this paper, an attractive algorithm for computing bounding spheres under such conditions is proposed. The method is based on selecting a set of k extremal points along s = k/2 input directions. In general, the method is able to compute better fitting spheres than Ritter's algorithm at roughly the same speed. Furthermore, the al- gorithm computes almost optimal spheres significantly faster than the best known smallest enclosing ball methods. Experimental evi- dence is provided which illustrates the qualities of the approach as compared to five other competing methods. Also, the experimental result gives insight into how the parameter s affects the tightness of fit and computation speed. CRCategories:
journaltitleProceedings of The Annual SIGRAD Conference. 2008.
titleFast and Tight Fitting Bounding Spheres
bounding sphere,computational geometry,computer graphics,enclosing ball,external points

journaltitleBusiness & information systems engineering
titleIndustry 4.0

Cambridge University Press

titlePlanning Algorithms

abstractIn this paper we present a novel approach to efficiently generate collision-free optimal trajectories for multiple non-holonomic mobile robots in obstacle-rich environments. Our approach first employs a graph-based multi-agent path planner to find an initial discrete solution, and then refines this solution into smooth trajectories using nonlinear optimization. We divide the robot team into small groups and propose a prioritized trajectory optimization method to improve the scalability of the algorithm. Infeasible sub-problems may arise in some scenarios because of the decoupled optimization framework. To handle this problem, a novel grouping and priority assignment strategy is developed to increase the probability of finding feasible trajectories. Compared to the coupled trajectory optimization, the proposed approach reduces the computation time considerably with a small impact on the optimality of the plans. Simulations and hardware experiments verified the effectiveness and superiority of the proposed approach.
journaltitleIEEE Robotics and Automation Letters
titleEfficient trajectory planning for multiple non-holonomic mobile robots via prioritized trajectory optimization
Collision avoidance,Motion and path planning,Multi-robot systems

MDPI AG

titleA Review of Path-Planning Approaches for Multiple Mobile Robots

Springer Science
Business Media LLC

journaltitleJournal of Intelligent Manufacturing
titleReconfigurable manufacturing systems: Key to future manufacturing

abstractGrasp planning in multi-robot systems is usually studied in a centralized setting with all robots sharing common knowledge about the overall system. Relaxing this assumption would allow multiple mobile manipulators to cooperate even without strict and precise coordination. Moreover, most typical tasks for cooperative settings, such as transporting heavy objects, require certain forces/torques to be exerted along/around particular directions, for instance, compensating for the weight of the transported object. In this paper, we propose task specific multi-robot grasp planning strategies that allow decentralized planning. Each agent plans its own actions without precise information about the other's plans. The approach is based on analysing a task specific grasp quality metric in a probabilistic context, compensating thus for the incomplete knowledge. Results from simulation experiments demonstrate that task independent planning is clearly inferior when task characteristics are known and thus task specific quality measures should be used. Furthermore, the proposed decentralized planning approaches clearly outperform the baseline and show close to globally optimal performance.
journaltitleIEEE International Conference on Robotics and Automation (ICRA)
titleTask specific cooperative grasp planning for decentralized multi-robot systems

abstractThe coordination of emergency responders and robots to undertake a number of tasks in disaster scenarios is a grand challenge for multi-agent systems. Central to this endeavour is the problem of forming the best teams (coalitions) of responders to perform the various tasks in the area where the disaster has struck. Moreover, these teams may have to form, disband, and reform in different areas of the disaster region. This is because in most cases there will be more tasks than agents. Hence, agents need to schedule themselves to attempt each task in turn. Second, the tasks themselves can be very complex: requiring the agents to work on them for different lengths of time and having deadlines by when they need to be completed. The problem is complicated still further when different coalitions perform tasks with different levels of efficiency. Given all these facets, we define this as The Coalition Formation with Spatial and Temporal constraints problem (CFSTP). We show that this problem is NP-hard-in particular, it contains the well-known complex combinatorial problem of Team Orienteering as a special case. Based on this, we design a Mixed Integer Program to optimally solve small-scale instances of the CFSTP and develop new anytime heuristics that can, on average, complete 97% of the tasks for large problems (20 agents and 300 tasks). In so doing, our solutions represent the first results for CFSTP. Copyright © 2010, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
journaltitleProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
titleCoalition formation with spatial and temporal constraints
Coalition Formation,RoboCupRescue,Routing and Scheduling

abstractWe wish to organize furniture in a room with a team of robots that can push objects. We show how coordinated pushing by robots can change the pose (position and orientation) of objects and then we ask whether planning, global control, and explicit communication are necessary for cooperatively changing the pose of objects. We answer in the negative and present, as witnesses, four cooperative manipulation protocols that use different amount of state, sensing, and communication. We analyze these protocols in the information invariant framework. We formalize the notion of resource tradeoffs for robot protocols and give the tradeoffs for the specific protocols discussed here.
journaltitleIEEE International Conference on Intelligent Robots and Systems
titleMoving furniture with teams of autonomous robots

abstractIn near future, robots are envisioned to work alongside humans in unstructured professional and domestic environments. In such setups, collaborative manipulation is a fundamental skill that allows manipulation of heavy loads by load sharing between agents. Grasp planning plays a pivotal role for load sharing but it has not received attention in the literature. This work proposes a grasp analysis approach for collaborative manipulation that allows load sharing by minimizing exerted grasp wrenches in a task specific way. The manipulation task is defined as expected external wrenches acting on the target object. The analysis approach is demonstrated in a two-agent decentralized set-up with unknown objects. After the first agent has grasped the target, the second agent observes the first agent's grasp location and plans its own grasp according to optimal load sharing. The method was verified in a human robot collaborative lifting task. Experiments with multiple objects show that the proposed method results in optimal load sharing despite limited information and partial observability.
journaltitleIEEE International Conference on Robotics and Automation (ICRA)
titleGrasp Planning for Load Sharing in Collaborative Manipulation

John Wiley & Sons

titleFacilities planning
family=Van Berg,

abstractIn this paper, we propose a new concept - the "Reciprocal Velocity Obstacle"- for real-time multi-agent navigation. We consider the case in which each agent navigates independently without explicit communication with other agents. Our formulation is an extension of the Velocity Obstacle concept [3], which was introduced for navigation among (passively) moving obstacles. Our approach takes into account the reactive behavior of the other agents by implicitly assuming that the other agents make a similar collision-avoidance reasoning. We show that this method guarantees safe and oscillation-free motions for each of the agents. We apply our concept to navigation of hundreds of agents in densely populated environments containing both static and moving obstacles, and we show that real-time and scalable performance is achieved in such challenging scenarios. ©2008 IEEE.
journaltitleIEEE International Conference on Robotics and Automation (ICRA)
titleReciprocal velocity obstacles for real-time multi-agent navigation

abstractAutomated guided vehicles (AGVs) are used for the internal and external transport of materials. Traditionally, AGVs were mostly used at manufacturing systems. Currently, AGVs are also used for repeating transportation tasks in other areas, such as warehouses, container terminals and external (underground) transportation systems. This paper discusses literature related to design and control issues of AGV systems at manufacturing, distribution, transshipment and transportation systems. It is concluded that most models can be applied for design problems at manufacturing centres. Some of these models and new models already proved to be successful in large AGV systems. In fact, new analytical and simulation models need to be developed for large AGV systems to overcome large computation times, NP-completeness, congestion, deadlocks and delays in the system and finite planning horizons. We specify more specific research perspectives in the design and control of AGV systems in distribution, transshipment and transportation systems. © 2004 Elsevier B.V. All rights reserved.
journaltitleEuropean Journal of Operational Research
titleSurvey of research in the design and control of automated guided vehicle systems
Automated guided vehicle systems,Design and control,Distribution,Literature survey,Transshipment and transportation systems

Stanford University Department of Computer Science

titleOn Geometric Assembly Planning

abstractIn which order can a product be assembled or disassembled? How many hands are required? How many degrees of freedom? What parts should be withdrawn to allow the removal of a specified subassembly? To answer such questions automatically, important theoretical issues in geometric reasoning must be addressed. This paper investigates the planning of assembly algorithms specifying (dis)assembly operations on the components of a product and the ordering of these operations. It also presents measures to evaluate the complexity of these algorithms and techniques to estimate the inherent complexity of a product. The central concept underlying these planning and complexity evaluation techniques is that of a "non-directional blocking graph", a qualitative representation of the internal structure of an assembly product. This representation describes the combinatorial set of parts interactions in polynomial space. It is obtained by identifying physical criticalities where geometric interferences among parts change. It is generated from an input geometric description of the product. The main application considered in the paper is the creation of smart environments to help designers create products that are easier to manufacture and service. Other possible applications include planning for rapid prototyping and autonomous robots.
journaltitleArtificial Intelligence
titleGeometric reasoning about mechanical assembly

journaltitleAAAI Conference on Artificial Intelligence (AAAI)
titleStructure and Intractability of Optimal Multi-Robot Path Planning on Graphs

abstractBridging cultures that have often been distant, Julia combines expertise from the diverse helds of computer science and computational science to create a new approach to numerical computing. Julia is designed to be easy and fast and questions notions generally held to be "laws of nature" by practitioners of numerical computing: 1. High-level dynamic programs have to be slow. 2. One must prototype in one language and then rewrite in another language for speed or deployment. 3. There are parts of a system appropriate for the programmer, and other parts that are best left untouched as they have been built by the experts. We introduce the Julia programming language and its design-a dance between specialization and abstraction. Specialization allows for custom treatment. Multiple dispatch, a technique from computer science, picks the right algorithm for the right circumstance. Abstraction, which is what good computation is really about, recognizes what remains the same after differences are stripped away. Abstractions in mathematics are captured as code through another technique from computer science, generic programming. Julia shows that one can achieve machine performance without sacrificing human convenience.
journaltitleSIAM Review
titleJulia: A fresh approach to numerical computing
Julia,Numerical,Parallel,Scientific computing

journaltitleIEEE International Conference on Robotics and Automation (ICRA)
titleOptimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning

journaltitleIEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
titleMulti-Robot Assembly Sequencing via Discrete Optimization

journaltitleThe International Journal of Robotics Research
titleMulti-scale assembly with robot teams
Robotic assembly,distributed control,multi-scale assembly,multi-scale perception,robot teams,robotic manufacturing

Springer US

journaltitleAutonomous Robots
titleMulti-robot grasp planning for sequential assembly operations
family=Ani Hsieh,

abstractWe present a decentralized approach to multi-robot manipulation where the team of robots surround and trap an object and transport it, by dragging or pushing, to the goal configuration in an environment with obstacles. The proposed feedback controllers are obtained by sequentially composing vector fields or behaviors and are decentralized in the sense that robots do not exchange each other's state information. Rather, cooperative manipulation is achieved by relying solely on each robot's local information and a global knowledge of the task. We present computer simulations and experimental results obtained using our multi-robot testbed. ©2008 IEEE.
journaltitleIEEE International Conference on Robotics and Automation (ICRA)
titleMulti-robot manipulation via caging in environments with obstacles

abstractThe problem of planning for a robot that operates in environments containing a large number of objects, taking actions to move itself through the world as well as to change the state of the objects, is known as task and motion planning (TAMP). TAMP problems contain elements of discrete task planning, discrete–continuous mathematical programming, and continuous motion planning and thus cannot be effectively addressed by any of these fields directly. In this article, we define a class of TAMP problems and survey algorithms for solving them, characterizing the solution methods in terms of their strategies for solving the continuous-space subproblems and their techniques for integrating the discrete and continuous components of the search.
journaltitleAnnual Review of Control, Robotics, and Autonomous Systems
titleIntegrated Task and Motion Planning
Automated planning,Manipulation planning,Motion planning,Robotics,Task and motion planning
family=Gurobi Optimization, LLC,

titleGurobi Optimizer Reference Manual

abstractAssembly planning is the problem of finding a sequence of motions to assemble a product from its parts. We present a general framework for finding assembly motions based on the concept of motion space. Assembly motions are parameterized such that each point in motion space represents a mating motion that is independent of the moving part set. For each motion we derive blocking relations that explicitly state which parts collide with other parts; each subassembly (rigid subset of parts) that does not collide with the rest of the assembly can easily be derived from the blocking relations. Motion space is partitioned into an arrangement of cells such that the blocking relations are fixed within each cell. We apply the approach to assembly motions of several useful types, including one-step translations, multistep translations, and infinitesimal rigid motions. Several efficiency improvements are described, as well as methods to include additional assembly constraints into the framework. The resulting algorithms have been implemented and tested extensively on complex assemblies. We conclude by describing some remaining open problems.
titleA general framework for assembly planning: The motion space approach
Assembly planning,Assembly sequencing,Manufacturing,Motion space,Nondirectional blocking graph

Taylor & Francis

journaltitleInternational Journal of Production Research
titleMachine layout: an optimization and knowledge-based approach

journaltitleThe International Journal of Robotics Research
titleTangentBug : A Range-Sensor-Based Navigation Algorithm

journaltitleIEEE International Conference on Robotics and Automation (ICRA)
titleReal-time obstacle avoidance for manipulators and mobile robots

abstractWe present an automated assembly system that directs the actions of a team of heterogeneous robots in the completion of an assembly task. From an initial user-supplied geometric specification, the system applies reasoning about the geometry of individual parts in order to deduce how they fit together. The task is then automatically transformed to a symbolic description of the assembly-a sort of blueprint. A symbolic planner generates an assembly sequence that can be executed by a team of collaborating robots. Each robot fulfills one of two roles: parts delivery or parts assembly. The latter are equipped with specialized tools to aid in the assembly process. Additionally, the robots engage in coordinated co-manipulation of large, heavy assemblies. We provide details of an example furniture kit assembled by the system.
journaltitleIEEE International Conference on Robotics and Automation (ICRA)
titleIkeaBot: An autonomous multi-robot coordinated furniture assembly system

[Wiley, Econometric Society]

abstractTwo problems in the allocation of indivisible resources are discussed. Both can be interpreted as problems of assigning plants to locations. The first problem, in which cost of transportation between plants is ignored, is found to be a linear programming problem, with which is associated a system of rents that sustains an optimal assignment. The recognition of cost of interplant transportation in the second problem introduces complications which call for more laborious and largely unexplored computations and which also appear to defeat the price system as a means of sustaining an optimal assignment.
issn00129682, 14680262
titleAssignment Problems and the Location of Economic Activities

journaltitleJournal of Manufacturing Systems
titleDesign of reconfigurable manufacturing systems

abstractBounding spheres are utilized frequently in many computer graph- ics and visualization applications, and it is not unusual that the com- putation of the spheres has to be done during run-time at real-time rates. In this paper, an attractive algorithm for computing bounding spheres under such conditions is proposed. The method is based on selecting a set of k extremal points along s = k/2 input directions. In general, the method is able to compute better fitting spheres than Ritter's algorithm at roughly the same speed. Furthermore, the al- gorithm computes almost optimal spheres significantly faster than the best known smallest enclosing ball methods. Experimental evi- dence is provided which illustrates the qualities of the approach as compared to five other competing methods. Also, the experimental result gives insight into how the parameter s affects the tightness of fit and computation speed. CRCategories:
journaltitleProceedings of The Annual SIGRAD Conference. 2008.
titleFast and Tight Fitting Bounding Spheres
bounding sphere,computational geometry,computer graphics,enclosing ball,external points

journaltitleBusiness & information systems engineering
titleIndustry 4.0

Cambridge University Press

titlePlanning Algorithms

abstractIn this paper we present a novel approach to efficiently generate collision-free optimal trajectories for multiple non-holonomic mobile robots in obstacle-rich environments. Our approach first employs a graph-based multi-agent path planner to find an initial discrete solution, and then refines this solution into smooth trajectories using nonlinear optimization. We divide the robot team into small groups and propose a prioritized trajectory optimization method to improve the scalability of the algorithm. Infeasible sub-problems may arise in some scenarios because of the decoupled optimization framework. To handle this problem, a novel grouping and priority assignment strategy is developed to increase the probability of finding feasible trajectories. Compared to the coupled trajectory optimization, the proposed approach reduces the computation time considerably with a small impact on the optimality of the plans. Simulations and hardware experiments verified the effectiveness and superiority of the proposed approach.
journaltitleIEEE Robotics and Automation Letters
titleEfficient trajectory planning for multiple non-holonomic mobile robots via prioritized trajectory optimization
Collision avoidance,Motion and path planning,Multi-robot systems

MDPI AG

titleA Review of Path-Planning Approaches for Multiple Mobile Robots

Springer Science
Business Media LLC

journaltitleJournal of Intelligent Manufacturing
titleReconfigurable manufacturing systems: Key to future manufacturing

abstractGrasp planning in multi-robot systems is usually studied in a centralized setting with all robots sharing common knowledge about the overall system. Relaxing this assumption would allow multiple mobile manipulators to cooperate even without strict and precise coordination. Moreover, most typical tasks for cooperative settings, such as transporting heavy objects, require certain forces/torques to be exerted along/around particular directions, for instance, compensating for the weight of the transported object. In this paper, we propose task specific multi-robot grasp planning strategies that allow decentralized planning. Each agent plans its own actions without precise information about the other's plans. The approach is based on analysing a task specific grasp quality metric in a probabilistic context, compensating thus for the incomplete knowledge. Results from simulation experiments demonstrate that task independent planning is clearly inferior when task characteristics are known and thus task specific quality measures should be used. Furthermore, the proposed decentralized planning approaches clearly outperform the baseline and show close to globally optimal performance.
journaltitleIEEE International Conference on Robotics and Automation (ICRA)
titleTask specific cooperative grasp planning for decentralized multi-robot systems

abstractThe coordination of emergency responders and robots to undertake a number of tasks in disaster scenarios is a grand challenge for multi-agent systems. Central to this endeavour is the problem of forming the best teams (coalitions) of responders to perform the various tasks in the area where the disaster has struck. Moreover, these teams may have to form, disband, and reform in different areas of the disaster region. This is because in most cases there will be more tasks than agents. Hence, agents need to schedule themselves to attempt each task in turn. Second, the tasks themselves can be very complex: requiring the agents to work on them for different lengths of time and having deadlines by when they need to be completed. The problem is complicated still further when different coalitions perform tasks with different levels of efficiency. Given all these facets, we define this as The Coalition Formation with Spatial and Temporal constraints problem (CFSTP). We show that this problem is NP-hard-in particular, it contains the well-known complex combinatorial problem of Team Orienteering as a special case. Based on this, we design a Mixed Integer Program to optimally solve small-scale instances of the CFSTP and develop new anytime heuristics that can, on average, complete 97% of the tasks for large problems (20 agents and 300 tasks). In so doing, our solutions represent the first results for CFSTP. Copyright © 2010, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
journaltitleProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
titleCoalition formation with spatial and temporal constraints
Coalition Formation,RoboCupRescue,Routing and Scheduling

abstractWe wish to organize furniture in a room with a team of robots that can push objects. We show how coordinated pushing by robots can change the pose (position and orientation) of objects and then we ask whether planning, global control, and explicit communication are necessary for cooperatively changing the pose of objects. We answer in the negative and present, as witnesses, four cooperative manipulation protocols that use different amount of state, sensing, and communication. We analyze these protocols in the information invariant framework. We formalize the notion of resource tradeoffs for robot protocols and give the tradeoffs for the specific protocols discussed here.
journaltitleIEEE International Conference on Intelligent Robots and Systems
titleMoving furniture with teams of autonomous robots

abstractIn near future, robots are envisioned to work alongside humans in unstructured professional and domestic environments. In such setups, collaborative manipulation is a fundamental skill that allows manipulation of heavy loads by load sharing between agents. Grasp planning plays a pivotal role for load sharing but it has not received attention in the literature. This work proposes a grasp analysis approach for collaborative manipulation that allows load sharing by minimizing exerted grasp wrenches in a task specific way. The manipulation task is defined as expected external wrenches acting on the target object. The analysis approach is demonstrated in a two-agent decentralized set-up with unknown objects. After the first agent has grasped the target, the second agent observes the first agent's grasp location and plans its own grasp according to optimal load sharing. The method was verified in a human robot collaborative lifting task. Experiments with multiple objects show that the proposed method results in optimal load sharing despite limited information and partial observability.
journaltitleIEEE International Conference on Robotics and Automation (ICRA)
titleGrasp Planning for Load Sharing in Collaborative Manipulation

John Wiley & Sons

titleFacilities planning
family=Van Berg,

abstractIn this paper, we propose a new concept - the "Reciprocal Velocity Obstacle"- for real-time multi-agent navigation. We consider the case in which each agent navigates independently without explicit communication with other agents. Our formulation is an extension of the Velocity Obstacle concept [3], which was introduced for navigation among (passively) moving obstacles. Our approach takes into account the reactive behavior of the other agents by implicitly assuming that the other agents make a similar collision-avoidance reasoning. We show that this method guarantees safe and oscillation-free motions for each of the agents. We apply our concept to navigation of hundreds of agents in densely populated environments containing both static and moving obstacles, and we show that real-time and scalable performance is achieved in such challenging scenarios. ©2008 IEEE.
journaltitleIEEE International Conference on Robotics and Automation (ICRA)
titleReciprocal velocity obstacles for real-time multi-agent navigation

abstractAutomated guided vehicles (AGVs) are used for the internal and external transport of materials. Traditionally, AGVs were mostly used at manufacturing systems. Currently, AGVs are also used for repeating transportation tasks in other areas, such as warehouses, container terminals and external (underground) transportation systems. This paper discusses literature related to design and control issues of AGV systems at manufacturing, distribution, transshipment and transportation systems. It is concluded that most models can be applied for design problems at manufacturing centres. Some of these models and new models already proved to be successful in large AGV systems. In fact, new analytical and simulation models need to be developed for large AGV systems to overcome large computation times, NP-completeness, congestion, deadlocks and delays in the system and finite planning horizons. We specify more specific research perspectives in the design and control of AGV systems in distribution, transshipment and transportation systems. © 2004 Elsevier B.V. All rights reserved.
journaltitleEuropean Journal of Operational Research
titleSurvey of research in the design and control of automated guided vehicle systems
Automated guided vehicle systems,Design and control,Distribution,Literature survey,Transshipment and transportation systems

Stanford University Department of Computer Science

titleOn Geometric Assembly Planning