CD4+ T cells play a crucial role in adaptive immunity and are a significant component of immunological response in many settings. Computational prediction of which antigenic peptides are presented and bind to T cells is a problem that has been studied for several decades. Current efforts apply supervised learning methods to predict peptide-MHCII binding, but do not incorporate the role of antigen processing. To address this, our group developed the Antigen Processing Likelihood (APL) algorithm, which relies on a free energy-based conformational stability metric known as COREX. COREX requires the analysis of a potentially large conformational ensemble and is thus computationally intensive. In recent prior work, we parallelized this analysis with an algorithm we called pCOREX. pCOREX reduced the computation time from hours/days to minutes, demonstrating a near-ideal speedup on 192 CPU cores. In this paper, we achieve an even more substantial acceleration of the COREX algorithm by making use of GPU cores, and demonstrate a reduction in computation time from minutes to seconds.

Robotic additive manufacturing has the potential to replace traditional production techniques with more flexible, capable and efficient methods. However, this potential has not yet been realized due to the intrinsic physical limitations of extruders. Thus improved speed and efficiency lies in coordinated fabrication by multiple extruders. In this paper, we propose a framework for utilizing multiple extruders to collaboratively fabricate objects in a shared workspace. In contrast to related work, we make use of a Reeb decomposition method of the input model, which dramatically reduces the search space over feasible toolpaths but still results in highly effective allocation of model components to each extruder. We demonstrate superior performance of our approach in simulation as well as in hardware with a two-robot arm extruder system. When compared to a single extruder approach over a benchmark of 14 models, our method achieves a mean improvement of 72% in extruder utilization. When compared to two additional toolpath planning methods for multiple extruders, only our method is able to successfully complete a valid toolpath on all models. Prior methods fail on more than half of our benchmark due to reaching deadlocked states during toolpath planning. On the models for which all methods succeed, our approach achieves mean utilization improvements of 132% over zone-blocking and 12% over contour greedy. We demonstrate that our approach is also suitable for models with non-planar slicings, which yield further improvements in extruder utilization. For more results and information see: https://sites.google.com/view/multi-arm-reeb.

Antigen-presenting cells present peptides derived from foreign pathogens in the form of peptide-MHCII complexes to induce immune response. Two important and interrelated processes that lead to peptide presentation are antigen processing and peptide-MHCII binding. Although the latter phenomenon has been thoroughly studied and incorporated into CD4+ T cell epitope prediction tools, antigen processing has remained under-explored as a means to improve epitope prediction tools. In prior work, our group developed the antigen processing likelihood (APL) metric [1] and showed that it can be used to effectively predict CD4+ T-cell epitopes either alone or in combination with peptide-MHCII binding affinity-based tools. A key component of the APL scoring approach is a residue-wise conformational stability metric known as COREX [2], which estimates the likelihood of unfolding at each residue using a free energy approximation. COREX calculation takes a significant amount of time (6-8 hours) and thus limits our ability to rapidly predict CD4+ T-cell epitopes over large antigen sets. In this paper, we give a parallel algorithm to compute the COREX metric and demonstrate its utility over several benchmarks. We achieve a 196-fold speedup with our parallel algorithm, bringing the overall computation of APL down from hours to minutes.

We present a new algorithm for coordinating the motion of multiple extruders to increase throughput in fused filament fabrication (FFF)/fused deposition modeling (FDM) additive manufacturing. Platforms based on FFF are commonly available and advantageous to several industries, but are limited by slow fabrication time and could be could be significantly improved through efficient use of multiple extruders. We propose the coordinated toolpath planning problem for systems of extruders mounted as end-effectors on robot arms with the objective of maximizing utilization and avoiding collisions. Building on the idea of dependency graphs introduced in our earlier work, we develop a planning and control framework that precomputes a set of multi-layer toolpath segments from the input model and efficiently assigns them to individual extruders such that executed toolpaths are collision-free. Our method overcomes key limitations of existing methods, including utilization loss from workspace partitioning, precomputed toolpaths subject to collisions with the partially fabricated object, and wasted motion resulting from strict layer-by-layer fabrication. We report simulation results that show a major increase in utilization compared to single and multi-extruder methods, and favorable fabrication results using commodity hardware that demonstrate the feasibility of our method in practice.

Gaussian processes (GPs) enable a probabilistic approach to important estimation and classification tasks that arise in robotics applications. Meanwhile, most GP-based methods are often prohibitively slow, thereby posing a substantial barrier to practical applications. Existing "sparse" methods to speed up GPs seek to either make the model more sparse, or find ways to more efficiently manage a large covariance matrix. In this paper, we present an orthogonal approach that memoises (i.e. reuses) previous computations in GP inference. We demonstrate that a substantial speedup can be achieved by incorporating memoisation into applications in which GPs must be updated frequently. Moreover, we derive a novel online update scheme for sparse GPs that can be used in conjunction with our memoisation approach for a synergistic improvement in performance. Across three robotic vision applications, we demonstrate between 40-100% speed-up over the standard method for inference in GP mixtures.

The most widely used methods for toolpath planning in 3D printing slice the input model into successive 2D layers to construct the toolpath. Unfortunately the methods can incur a substantial amount of wasted motion (i.e., the extruder is moving while not printing). In recent years we have introduced a new paradigm that characterizes the space of feasible toolpaths using a dependency graph on the input model, along with several algorithms that optimize objective functions (wasted motion or print time). A natural question that arises is, under what circumstances can we efficiently compute an optimal toolpath? In this paper, we give an algorithm for computing fused deposition modeling (FDM) toolpaths that utilizes Monte Carlo Tree Search (MCTS), a powerful generalpurpose method for navigating large search spaces that is guaranteed to converge to the optimal solution. Under reasonable assumptions on printer geometry that allow us to compress the dependency graph, our MCTS-based algorithm converges to find the optimal toolpath. We validate our algorithm on a dataset of 75 models and examine the performance on MCTS against our previous best local search-based algorithm in terms of toolpath quality. We show that a relatively short time budget for MCTS yields results on par with local search, while a larger time budget yields a 15% improvement in quality over local search. Additionally, we examine the properties of the models and MCTS executions that lead to better or worse results.

We present an algorithm for selecting when to communicate during online planning phases of coordinated multi-robot missions. The key idea is that a robot decides to request communication from another robot by reasoning over the predicted information value of communication messages over a sliding time-horizon, where communication messages are probability distributions over action sequences. We formulate this problem in the context of the recently proposed decentralised Monte Carlo tree search (Dec-MCTS) algorithm for online, decentralised multi-robot coordination. We propose a particle filter for predicting the information value, and a polynomial-time belief-space planning algorithm for finding the optimal communication schedules in an online and decentralised manner. We evaluate the benefit of informative communication planning for a multi-robot information gathering scenario with 8 simulated robots. Our results show reductions in channel utilisation of up to four-fifths with surprisingly little impact on coordination performance.

The most widely used methods for toolpath planning in fused deposition 3D printing slice the input model into successive 2D layers in order to construct the toolpath. Unfortunately slicing-based methods can incur a substantial amount of wasted motion (i.e., the extruder is moving while not printing), particularly when features of the model are spatially separated. In recent work we have introduced a new paradigm that constructs the toolpath in 3D and prints local features to minimize wasted motion. Our algorithm is based on a local search and we have demonstrated substantial improvements in the efficiency of the resulting toolpaths. Our approach is amenable to incorporating physical constraints of the 3D printing process, and, in this paper we extend our approach to incorporate kinematic properties into toolpath optimization. With an accurate kinematic model of the extruder, our algorithm is able to model the real-world fabrication time of the model with a high degree of accuracy. To our knowledge, this toolpath optimization algorithm is the first to encode real-world fabrication time as the objective function. We demonstrate the real-world improvement in fabrication time that is possible with our algorithm on a benchmark of almost 600 models. We find improvement in nearly every toolpath generated for our benchmark set (with a mean of 3.2%), but substantially larger improvements for some models. To rationalize these results, we introduce a metric for model characterization that we call “oriented compactness” and show that it correlates positively with our observations. We believe this metric can be an important tool in the setup of fabrication (e.g., by guiding an orientation search of the model).

Widely-used methods for toolpath planning in fused filament fabrication slice the input 3D model into 2D layers and construct a toolpath. In prior work (ICRA 2016) we gave a simple greedy algorithm that changed this paradigm and constructed the toolpath in 3D by printing local features in their entirety. This algorithm significantly improved upon layer-based methods, achieving a 34% mean reduction of wasted motion. In this paper we give a new algorithm that is more robust and achieves significantly better performance than the greedy approach. Our algorithm utilizes local search and nearly doubles our prior improvement, achieving a mean/median reduction of 62% over layer-based methods on the same benchmark of over 400 models. We also study toolpath optimality using a novel integer linear programming formulation. This formulation allows us to solve a linear programming relaxation that, while computationally intensive, can give us a lower bound on the optimal solution quality, giving us the ability to rigorously characterize solution quality for a given input model.

Fused filament fabrication (FFF) is gaining traction for rapid prototyping and custom fabrication. Existing toolpath generation methods for FFF printers take as input a three-dimensional model of the target object and construct a layered toolpath that will fabricate the object in 2D slices of a chosen thickness. While this approach is computationally straightforward, it can produce toolpaths that can contain significant, yet unnecessary, extrusionless travel. In this paper we propose a novel 3D toolpath generation paradigm that leverages local feature independence in the target object. In contrast to existing FFF slicing methods which print an object layer by layer, our algorithm provides a means to print local features of an object without being constrained to a single layer. The key benefit of our approach is a tremendous reduction in “extrusionless travel,” in which the printer must move between features without performing any extrusion. We show on a benchmark of 409 objects that our method can yield substantial savings in extrusionless travel, 34% on average, that can directly translate to a reduction in total manufacturing time.

Dual-decomposition (DD) methods are quickly becoming important tools for estimating the minimum energy state of a graphical model. DD methods decompose a complex model into a collection of simpler subproblems that can be solved exactly (such as trees), that in combination provide upper and lower bounds on the exact solution. Subproblem choice can play a major role: larger subproblems tend to improve the bound more per iteration, while smaller subproblems enable highly parallel solvers and can benefit from re-using past solutions when there are few changes between iterations. We propose an algorithm that can balance many of these aspects to speed up convergence. Our method uses a cluster tree data structure that has been proposed for adaptive exact inference tasks, and we apply it in this paper to dual-decomposition approximate inference. This approach allows us to process large subproblems to improve the bounds at each iteration, while allowing a high degree of parallelizability and taking advantage of subproblems with sparse updates. For both synthetic inputs and a real-world stereo matching problem, we demonstrate that our algorithm is able to achieve significant improvement in convergence time.

In this paper, we investigate the problem of scheduling flows for fair stream allocation in ad hoc networks utilizing multiple antennas at the transmitter and receiver side known as Multiple Input Multiple Output (MIMO) antenna technology. Our main contributions include: i) the concept of stream allocation to flows based on their traffic demands or class, ii) achieving the proportional fairness of the stream allocation in the minimum possible schedule length. We first formulate demand-based fair stream allocation as an integer linear programming (ILP) problem whose solution is a schedule that is guaranteed to be contention-free. We then solve this ILP in conjunction with binary search to find a minimum-length contention-free schedule that achieves the fairness goals. We also show that an implementation of our algorithm for a number of sample topologies in fact yields minimum length schedules that achieve the fairness goals.

To reap the benefits of advances in wireless technologies as well as provide backward compatibility with current investments, future wireless routers that constitute the backbone of Wireless Mesh Networks (WMNs) will be equipped with multiple radios of different technology standards. The multiplicity of channels, radios and technology standards makes the problem of efficient network utilization in a WMN more challenging. Unlike previous works that focused only on homogeneous WMNs, in this paper, we focus on determining an effective routing, channel assignment and scheduling scheme that maximizes the network capacity, while maintaining node level fairness in a heterogeneous network setting. We first introduce a novel graph model that captures the WMN heterogeneity in terms of the number of radios and radio technologies. Using this model, we provide an optimization formulation that determines the effective routing scheme and traffic values on each edge. To determine an interference-free channel assignment of these traffic values, we introduce a joint channel assignment and scheduling algorithm that preserves node level fairness. We perform an extensive evaluation of our solution in homogeneous and heterogeneous networks and study the impact of the number of orthogonal channels, radios, gateways and the aggregate traffic demand on the performance of our solution. Our results show that the proposed scheme obtains node level fairness while maximizing the network capacity.

Motivated by stochastic systems in which observed evidence and conditional de- pendencies between states of the network change over time, and certain quantities of interest (marginal distributions, likelihood estimates etc.) must be updated, we study the problem of adaptive inference in tree-structured Bayesian networks. We describe an algorithm for adaptive inference that handles a broad range of changes to the network and is able to maintain marginal distributions, MAP estimates, and data likelihoods in all expected logarithmic time. We give an implementation of our algorithm and provide experiments that show that the algorithm can yield up to two orders of magnitude speedups on answering queries and responding to dy- namic changes over the sum-product algorithm.

We introduce a natural variant of the (metric uncapacitated) k-median problem that we call the online median problem. Whereas the k-median problem involves optimizing the simultaneous placement of k facilities, the online median problem imposes the following additional constraints: the facilities are placed one at a time, a facility cannot be moved once it is placed, and the total number of facilities to be placed, k, is not known in advance. The objective of an online median algorithm is to minimize the competitive ratio, that is, the worst-case ratio of the cost of an online placement to that of an optimal offline placement. Our main result is a constant-competitive algorithm for the online median problem running in time that is linear in the input size. In addition, we present a related, though substantially simpler, constant-factor approximation algorithm for the (metric uncapacitated) facility location problem that runs in time linear in the input size. The latter algorithm is similar in spirit to the recent primal-dual-based facility location algorithm of Jain and Vazirani, but our approach is more elementary and yields an improved running time. While our primary focus is on problems which ask us to minimize the weighted average service distance to facilities, we also show that our results can be generalized to hold, to within constant factors, for more general objective functions. For example, we show that all of our approximation results hold, to within constant factors, for the k-means objective function.

We introduce a natural variant of the (metric uncapacitated) k-median problem that we call the online median problem. Whereas the k-median problem involves optimizing the simultaneous placement of k facilities, the on-line median problem imposes the following additional constraints: the facilities are placed one at a time; a facility cannot be moved once it is placed, and the total number of facilities to be placed, k, is not known in advance. The objective of an online median algorithm is to minimize the competitive ratio, that is, the worst-case ratio of the cost of an online placement to that of an optimal offline placement. Our main result is a linear-time constant-competitive algorithm for the online median problem. In addition, we present a related, though substantially simpler linear-time constant-factor approximation algorithm for the (metric uncapacitated) facility location problem. The latter algorithm is similar in spirit to the recent primal-dual-based facility location algorithm of Jain and Vazirani, but our approach is more elementary and yields an improved running time.