Robotic systems are routinely used in the logistics industry to enhance operational efficiency, but the design of robot workspaces remains a complex and manual task, which limits the system’s flexibility to changing demands. This paper aims to automate robot workspace design by proposing a computational framework to generate a budget-minimizing layout by selectively placing stationary robots on a floor grid to sort packages from given input and output locations. Finding a good layout that minimizes the hardware budget while ensuring motion feasibility is a challenging combinatorial problem with nonconvex motion constraints. We propose a new optimization-based approach that models layout planning as a subgraph optimization problem subject to network flow constraints. Our core insight is to abstract away motion constraints from the layout optimization by precomputing a kinematic reachability graph and then extract the optimal layout on this ground graph. We validate the motion feasibility of our approach by proposing a simple task assignment and motion planning technique. We benchmark our algorithm on problems with various grid resolutions and number of outputs and show improvements in memory efficiency over a heuristic search algorithm. In addition, we demonstrate that our algorithm can be extended to handle various types of robot manipulators and conveyor belts, box payload constraints, and cost assignments.

Identifying the closest fog node is crucial for mobile clients to benefit from fog computing. In this paper, we analyze the performance of the Meridian and Vivaldi network coordinate systems for this task. To that end, we simulate a dense fog environment with mobile clients. We find that while network coordinate systems really find fog nodes in close network proximity, a purely latency-oriented identification approach ignores the larger problem of balancing load across fog nodes.

A central aspect of robotic motion planning is collision avoidance, where a multitude of different approaches are currently in use. Optimization-based motion planning is one method, that often heavily relies on distance computations between robots and obstacles. These computations can easily become a bottleneck, as they do not scale well with the complexity of the robots or the environment. To improve performance, many different methods suggested to use collision primitives, i.e. simple shapes that approximate the more complex rigid bodies, and that are simpler to compute distances to and from. However, each pair of primitives requires its own specialized code, and certain pairs are known to suffer from numerical issues. In this paper, we propose an easy-to-use, unified treatment of a wide variety of primitives. We formulate distance computation as a minimization problem, which we solve iteratively. We show how to take derivatives of this minimization problem, allowing it to be seamlessly integrated into a trajectory optimization method. We demonstrate that the resulting method can be used to plan smooth and collision-free paths based on a variety of single- and multi-robot scenarios with different obstacles.

Cubical type theory provides a constructive justification of homotopy type theory. A crucial ingredient of cubical type theory is a path lifting operation which is explained computationally by induction on the type involving several non-canonical choices. We present in this article two canonicity results, both proved by a sconing argument: a homotopy canonicity result, every natural number is path equal to a numeral, even if we take away the equations defining the lifting operation on the type structure, and a canonicity result, which uses these equations in a crucial way. Both proofs are done internally in a presheaf model.

Teleoperating robotic arms is a challenging task that requires years of training to master. It is mentally demanding, as the operator must internally compute transformations, or rely on muscle memory, to perform even the simplest tasks. Alternative methods that rely on embodiment –the immersive, first person experience of controlling the robot from its point of view are recently becoming more popular, thanks to the emergence of mixed reality devices. These methods create an intuitive experience by tracking the users motions, and retargetting them to the robot. However, even recent hardware fails at achieving total immersion, due to inherent discrepancies such as latency, imperfect tracking, and the differences between human and robot motor systems. Thus, performing even simple pick-and-place tasks with these systems, while more intuitive, is still cumbersome, and far from the level of human performance.In this paper we propose an immersive system that aims to bridge this gap. The system tracks the user’s motion and retargets them to the robot as usual, but it also detects the user’s intent, that is, the task they wish to perform. Based on this knowledge, the system can autocorrect the motion when it is about to fail, in a seamless manner, such that the task is successfully performed. We evaluate the efficacy of our autocorrection system in a user study. The results show a statistically significant performance improvement in terms of operation accuracy and time.

This issue of Mathematical Structures in Computer Science is Part I of a Special Issue dedicated to the emerging field of Homotopy Type Theory and Univalent Foundations.

This issue of Mathematical Structures in Computer Science is Part II of a Special Issue dedicated to the emerging field of Homotopy Type Theory and Univalent Foundations.Part I of the Special Issue was published as Volume 31, Issue 1 of Mathematical Structures in Computer Science.In the preface to that issue, 1 we give a brief overview of the history of the workshop series "Homotopy Type Theory and Univalent Foundations (HoTT/UF)" from which this Special Issue arose.This issue comprises articles covering a range of topics in Homotopy Type Theory -from the formulation and formalization of mathematics within Univalent Foundations to the study of the meta-theory of type theory using category theory.Modalities allow one to extend type theories by additional type and term constructions in a well-controlled way.Felix Cherubini and Egbert Rijke's Modal descent studies the factorization systems generated by a modality, focusing on the modal reflective factorization system defined in this work.In one of the main results of this work, the authors characterize the right maps of this factorization system via the modal descent theorem.Nilpotency is an important property of spaces (or homotopy types) in classical homotopy theory.Luis Scoccola's Nilpotent types and fracture squares in homotopy type theory develops these notions synthetically in Homotopy Type Theory.Several important results about nilpotency are proved, including different characterizations of nilpotency.Scoccola also shows that cohomology isomorphisms between nilpotent types induce isomorphisms in all homotopy groups.Finally, he also proves a fracture theorem for a localization of truncated nilpotent types.Simon Boulier and Nicolas Tabareau's Model structure on the universe of all types in interval type theory introduces a type theory with an interval type, that is, a form of cubical type theory.Building on the Orton-Pitts axioms for modeling cubical type theory in a topos, they then construct a model structure on the universe of -not necessarily fibrant -types of that type theory, using, crucially, an operation of "fibrant replacement" defined via a quotient-inductive type.Many of the results presented in this contribution are mechanically checked in the computer proof assistant Coq; the source files are available in a public Git repository.In Syntax and Models of Cartesian Cubical Type Theory, Carlo Angiuli, Guillaume Brunerie, Thierry Coquand, Kuen-Bang Hou (Favonia), Robert Harper, and Daniel R. Licata define a cubical type theory based on Cartesian cubical sets.They also develop axioms, in the style of Orton and Pitts, which provide sufficient criteria for constructing a model of the type theory.This construction is computer checked using Agda as an internal language extended with these axioms.The obtained cubical set model requires less structure on the cube category than previous structural cubical set models.To make up for the lack of structure on the cube category, the notion of fibration had to be modified, and the proof that fibrancy is preserved by all type formers, in particular the universe, relies on the key step of adding the diagonal map of the interval as cofibration.During the preparation of this special issue, three pillars of the community have passed away prematurely.

We present an algorithmic approach to designing animatronic figures - expressive robotic characters whose movements are driven by a large number of actuators. The input to our design system provides a high-level specification of the space of motions the character should be able to perform. The output consists of a fully functional mechatronic blueprint. We cast the design task as a search problem in a vast combinatorial space of possible solutions. To find an optimal design in this space, we propose an efficient best-first search algorithm that is guided by an admissible heuristic. The objectives guiding the search process demand that the design remains free of singularities and self-collisions at any point in the high-dimensional space of motions the character is expected to be able to execute. To identify worst-case self-collision scenarios for multi degree-of-freedom closed-loop mechanisms, we additionally develop an elegant technique inspired by the concept of adversarial attacks. We demonstrate the efficacy of our approach by creating designs for several animatronic figures of varying complexity.

We introduce Deep500: the first customizable benchmarking infrastructure that enables fair comparison of the plethora of deep learning frameworks, algorithms, libraries, and techniques. The key idea behind Deep500 is its modular design, where deep learning is factorized into four distinct levels: operators, network processing, training, and distributed training. Our evaluation illustrates that Deep500 is customizable (enables combining and benchmarking different deep learning codes) and fair (uses carefully selected metrics). Moreover, Deep500 is fast (incurs negligible overheads), verifiable (offers infrastructure to analyze correctness), and reproducible. Finally, as the first distributed and reproducible benchmarking system for deep learning, Deep500 provides software infrastructure to utilize the most powerful supercomputers for extreme-scale workloads.

In this note we show that Voevodsky’s univalence axiom holds in the model of type theory based on cubical sets as described in Bezem et al. (in: Matthes and Schubert (eds.) 19th international conference on types for proofs and programs (TYPES 2013), Leibniz international proceedings in informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany, vol 26, pp 107–128, 2014. https://doi.org/10.4230/LIPIcs.TYPES.2013.107 . http://drops.dagstuhl.de/opus/volltexte/2014/4628 ) and Huber (A model of type theory in cubical sets. Licentiate thesis, University of Gothenburg, 2015). We will also discuss Swan’s construction of the identity type in this variation of cubical sets. This proves that we have a model of type theory supporting dependent products, dependent sums, univalent universes, and identity types with the usual judgmental equality, and this model is formulated in a constructive metatheory.

Cubical type theory is an extension of Martin-Löf type theory recently proposed by Cohen, Coquand, Mörtberg, and the author which allows for direct manipulation of n -dimensional cubes and where Voevodsky’s Univalence Axiom is provable. In this paper we prove canonicity for cubical type theory: any natural number in a context build from only name variables is judgmentally equal to a numeral. To achieve this we formulate a typed and deterministic operational semantics and employ a computability argument adapted to a presheaf-like setting.

We present a domain model of dependent type theory and use it to prove basic metatheoretic properties. In particular, we prove that two convertible terms have the same Böhm tree. The method used is reminiscent of the use of “inclusive predicates” in domain theory.

Cubical type theory provides a constructive justification to certain aspects of homotopy type theory such as Voevodsky's univalence axiom. This makes many extensionality principles, like function and propositional extensionality, directly provable in the theory. This paper describes a constructive semantics, expressed in a presheaf topos with suitable structure inspired by cubical sets, of some higher inductive types. It also extends cubical type theory by a syntax for the higher inductive types of spheres, torus, suspensions, truncations, and pushouts. All of these types are justified by the semantics and have judgmental computation rules for all constructors, including the higher dimensional ones, and the universes are closed under these type formers.

We present an interpretation of a version of dependent type theory where a type is interpreted by a Kan semisimplicial set. This interprets only a weak notion of conversion similar to the one used in the first published version of Martin-Löf type theory. Each truncated version of this model can be carried out internally in dependent type theory, and we have formalized the first truncated level, which is enough to represent isomorphisms of algebraic structure as equality.