{'fraction_non_alphanumeric': 0.02599204176249407, 'fraction_numerical': 0.005074289051947578, 'mean_word_length': 5.044571932921447, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Perception-Informed Autonomous Environment Augmentation With Modular Robots

We present hardware, perception, and planning tools that enable a modular robot to autonomously deploy passive structures to reach otherwise-inaccessible regions of the environment to accomplish high-level tasks. An environment characterization algorithm identifies features in the environment that can be augmented to create a path between two disconnected regions of the environment. Specially-designed building blocks enable the robot to create structures that can augment the identified features to expand the reachable space of the robot. A high-level planner reasons about the high-level task, robot locomotion capabilities, and the environment to decide if and where to augment the environment in order to perform the desired task. These autonomous, perception-driven augmentation tools extend the adaptive capabilities of modular robot systems.


I. INTRODUCTION
Employing structures to accomplish tasks is a ubiquitous part of the human experience: to reach an object on a high shelf, we place a ladder near the shelf and climb it, and at a larger scale, we construct bridges across wide rivers to make them passable. The fields of collective construction robotics and modular robotics offer examples of systems that can construct and traverse structures out of robotic or passive elements [1], [2], [3], [4], and assembly planning algorithms that allow arbitrary structures to be built under a variety of conditions [5], [6]. This existing body of work provides excellent contributions regarding the generality and completeness of these methods: some algorithms are provably capable of generating assembly plans for arbitrary volumetric structures in 3D, and hardware systems have demonstrated the capability to construct a wide variety of structures.
Less work is available regarding ways that robots could deploy structures as a means of completing an extrinsic task, the way a person might use a ladder to reach a high object. In this paper, we present hardware, perception, and high-level planning tools that allow structure-building to be deployed by a modular robot to address high-level tasks.
Our work uses the SMORES-EP modular robot [7], and introduces novel passive block and wedge modules that SMORES-EP can use to form ramps and bridges in its environment, expanding the physical capabilities of the robot. We expand on an existing framework for selecting appropriate robot morphologies and behaviors to address high-level tasks J. Daudelin [8], allowing the high-level planner to not only autonomously decide when to reconfigure the robot, but also when to augment the environment by assembling a passive structure.
To inform these decisions, we introduce a novel environment characterization algorithm that identifies candidate features where structures can be deployed to advantage. Together, these tools provide the novel ability to automatically identify when, where, and how the robot can augment its environment with a passive structure to gain advantage in completing a high-level task. We integrate our tools into an existing system for perception-driven autonomy with modular robots [9], and validate them in two hardware experiments. Based on a high-level specification, a modular robot reactively identifies inaccessible regions and autonomously deploys ramps and bridges to complete locomotion and manipulation tasks in realistic office environments.

II. RELATED WORK
Our work complements the well-established field of collective robotic construction, which focuses on autonomous robot systems for building activity. While we use a modular robot to create and place structures in the environment, our primary concern is not assembly planning or construction of the structure itself, but rather its appropriate placement in the environment to facilitate completion of an extrinsic high-level task.
Petersen et al. present Termes [2], a termite-inspired collective construction robot system that creates structures using blocks co-designed with a legged robot. Similarly, our augmentation modules are designed to be easily carried and traversed by SMORES-EP. Where the TERMES project focused on collective construction of a goal structure, we are less concerned with efficient building of the structure itself and more concerned with the application and placement of the structure in the larger environment as a means of facilitating a task unrelated to the structure itself.
Werfel et al. present algorithms for environmentallyadaptive construction that can build around obstacles in the environment [6]. A team of robots senses obstacles and builds around them, modifying the goal structure if needed to leave room for immovable obstacles. An algorithm to build enclosures around preexisting environment features is also presented. As with Termes, the goal is the structure itself; while the robots do respond to the environment, the structure is not built in response to an extrinsic high-level task.
Napp et al. present hardware and algorithms for building amorphous ramps in unstructured environments by deposit-ing foam with a tracked mobile robot [10], [4]. Amorphous ramps are built in response to the environment to allow a small mobile robot to surmount large, irregularly shaped obstacles. Our work is similar in spirit, but places an emphasis on autonomy and high-level locomotion and manipulation tasks rather than construction.
Modular self-reconfigurable robot (MSRR) systems are comprised of simple repeated robot elements (called modules) that connect together to form larger robotic structures. These robots can self-reconfigure, rearranging their constituent modules to form different morphologies, and changing their abilities to match the needs of the task and environment [11]. Our work leverages recent systems that integrate the low-level capabilities of an MSRR system into a design library, accomplish high-level user-specified tasks by synthesizing library elements into a reactive state machine [8], and operate autonomously in unknown environments using perception tools for environment exploration and characterization [9].
Our work extends the SMORES-EP hardware system by introducing passive pieces that are manipulated and traversed by the modules. Terada and Murata [3], present a latticestyle modular system with two parts, structure modules and an assembler robot. Like many lattice-style modular systems, the assembler robot can only move on the structure modules, and not in an unstructured environment. Other lattice-style modular robot systems create structures out of the robots themselves. M-blocks [1] form 3D structures out of robot cubes which rotate over the structure. Paulos et al. present rectangular boat robots that self-assemble into floating structures, like a bridge [12].
Magnenat et al [13] present a system in which a mobile robot manipulates specially designed cubes to build functional structures. The robot explores an unknown environment, performing 2D SLAM and visually recognizing blocks and gaps in the ground. Blocks are pushed into gaps to create bridges to previously inaccessible areas. In a "real but contrived experimental design" [13], a robot is tasked with building a three-block tower, and autonomously uses two blocks to build a bridge to a region with three blocks, retrieving them to complete its task. Where the Magnenat system is limited to manipulating blocks in a specifically designed environment, our work presents hardware, perception, and high-level planning tools that are more general, providing the ability to complete high-level tasks involving locomotion and manipulation in realistic human environments.

A. Environment Characterization
To successfully navigate its environment, a mobile robot must identify traversable areas. One simple method for wheeled robots is to select flat areas large enough for the robot to fit. However, MSRR systems can reconfigure to traverse a larger variety of terrains. The augmentation abilities we introduce extend MSRR navigation even further; the robot can build structures to traverse otherwiseimpossible terrains. For autonomous operation, we need an algorithm to locate and label features in the environment that can be augmented. We present a probabilistic, templatebased environment characterization algorithm that identifies augmentable features from a 2.5D elevation map of the robot's environment.
The characterization algorithm searches for a desired feature F n using a template consisting of a grid of likelihood functions l i (h) for 1 ≤ i ≤ M where M is the number of grid cells in the template, and h is a height value. The size of grid cells in the template is variable and need not correspond to the resolution of the map. In addition, features of different size can be searched for by changing the cell size of the template to change the scale. Figure 1 shows an example of a template used to characterize a "ledge" feature, consisting of Gaussian and logistic likelihood functions. Any closed-form likelihood function may be used for each grid cell, enabling templates to accommodate noisy data and variability in possible geometric shapes of the same feature. To determine if the feature exists at a candidate pose X in the map, a grid of height values is taken from the map corresponding to the template grid centered and oriented at the candidate pose, as illustrated in Figure 1. Then, the probability that each grid cell c i belongs to the feature is evaluated using the cell's likelihood function from the template.
The likelihood of the feature existing at that location is calculated by finding the total probability that all grid cells belong to the feature. Making the approximate simplifying assumption that grid cells are independent, this probability is equivalent to taking the product over the feature likelihoods of all grid cells in the template: The feature is determined to exist if the total probability is higher than a user-defined threshold, or P (X ∈ F n ) > α M , where α represents the minimum average probability of each grid cell forming part of the feature. In our experiments we use α = 0.95. This formulation normalizes the threshold with respect to the number of grid cells in the template.
To characterize an environment, the algorithm takes as inputs an elevation map of the environment and a list of feature templates. Before searching for features, the algorithm preprocesses the elevation map by segmenting it into flat, unobstructed regions that are traversable without augmentation. It then grids the map and exhaustively evaluates each candidate feature pose from the grid, using a grid of orientations for each 2D location. In addition to evaluation with the template, candidate poses are only valid if the ends of the feature connect two traversable regions from the preprocessing step, thereby having potential to extend the robot's reachable space. Once the search is complete, the algorithm returns a list of features found in the map, including their locations, orientations, and the two regions  Characterization of an environment with a "ledge" feature. Red indicates a detected feature, pink indicates the start of the feature, demonstrating orientation. they link in the environment. Figure 2 shows an example of a characterized map. Each long red cell represents a detected "ledge" feature, with a corresponding small pink cell demonstrating the orientation of the feature (and the bottom of the ledge). Note that, in this example, several features are chosen close to each other. Since all connect the same regions, any one is valid and equivalent to be selected for augmentation.
The algorithm scales linearly with the number of grid cells in the 2D environment map, and linearly with the number of features being searched for. Characterization of the environment shown in Figure 2 took approximately 3 seconds to run on a laptop with an Intel Core i7 processor.

B. Hardware: Augmentation Modules
Our system is built around the SMORES-EP modular robot. Each module is the size of an 80mm cube, weighs 473g, and has four actuated joints, including two wheels that can be used for differential drive on flat ground [7], [14]. Electro-permanent (EP) magnets allow any face of one module to connect to any face of another, enabling the robot to self-reconfigure. They are also able to attach to objects made of ferromagnetic materials (e.g. steel). The EP magnets require very little energy to connect and disconnect, and no energy to maintain their attachment force of 90N [7]. Each module has its own battery, microcontroller, and Large obstacles, like tall ledges or wide gaps in the ground, are often problematic for modular robot systems. One might expect that a modular system could scale, addressing a largelength-scale task by using many modules to form a large robot. In reality, modular robots don't scale easily: adding more modules makes the robot bigger, but not stronger. The torque required to lift a long chain of modules grows quadratically with the number of modules, quickly overloading the maximum torque of the first module in the chain. Consequently, large systems become cumbersome, unable to move their own bodies. Simulated work in reconfiguration and motion planning has demonstrated algorithms that handle hundreds of modules, but in practice, fixed actuator strength has typically limited these robots to configurations with fewer than 40 modules.
We address this issue by extending the SMORES-EP hardware system with passive elements called environment augmentation modules. We use the Wedge and Block augmentation modules shown in Figure 4. Like the construction blocks used by Termes [2], wedge and block modules are designed to work synergistically with SMORES-EP, providing features that use the best modes of locomotion (driving), manipulation (magnetic attachment), and sensing (AprilTags) available to SMORES-EP.
Blocks are the same size as a module (80mm cube), and wedges are half the size of a block (an equilateral right triangle with two 80mm sides). Both are made of lightweight laser-cut medium-density fiberboard (blocks are 162g, wedges are 142g) and equipped with a steel attachment point for magnetic grasping. Neodymium magnets on the back faces of wedges, and the front and back faces of blocks, form a strong connection in the horizontal direction. Interlocking features on the top and bottom faces of the blocks, and the bottom faces of the wedges, allow them to be stacked vertically. Wedges provide a 45-degree incline with a high-friction rubber surface, allowing a set of 3 or more modules to drive up them. Side walls on both the wedges and blocks ensure that SMORES-EP modules stay aligned to the structure and cannot fall off while driving over it. The side walls of wedges are tapered to provide a funneling effect as modules drive onto them, making them more tolerant to misalignment. Each wedge and ramp has unique AprilTag fiducials on its faces, allowing easy identification and localization during construction and placement in the environment.
Wedges and blocks allow a SMORES-EP cluster to autonomously construct bridges or ramps that allow it to reach higher heights and cross wider gaps than it could with robot modules alone ( Figure 5). Provided enough time, space, and augmentation modules are available, there is no limit to the height of a ramp that can be built. Bridges have a maximum length of 480mm (longer bridges cannot support a load of three SMORES-EP modules in the center).

C. High-Level Planner
We utilize a high-level planner that allows users to control low-level robot actions by defining tasks at high-level with a formal language [9]. The high-level planner serves two main functions. First it acts as a mission planner, automatically generating a robot controller (finite state automaton) from user-given task specifications. Second, it executes the generated controller, commanding the robot to react to the sensed environment and complete the tasks. The high-level planner integrates with a design library of user-created robot configurations and behaviors. Users do not explicitly specify configurations and behaviors for each task, but rather define goals and constraints for the robot. The high-level planner chooses robot configurations and behaviors from the design library based on the task specifications, and executes them Consider the example controller shown in Figure 6. The robot tasks are to look for a pink drawer, open the drawer, and then climb on top of it. Each state is labeled with a desired robot action, and each transition is labeled with perceived environment information; for example, the "climb drawer" action is specified to be any behavior from the library with properties climb in a ledge environment. In our previous framework [9], the high-level planner could choose to reconfigure the robot whenever needed to satisfy the required properties of the current action and environment.
In this work, the high-level planner can choose not only to change the abilities of the robot (reconfiguration), but also the properties of the environment (environment augmentation). We expand the library of robot designs with feature templates for recognizing augmentable environments (Section III-A). Associated with each template is a controller for manipulating augmentation modules to build the desired structure. Assembly plans are currently created manually, but could be automatically generated [5], [6].
For the example in Figure 6, if no behavior in the library satisfies the "climb drawer" action, the high-level planner will query the environment characterization subsystem (Section III-A) for possible environment augmentations. The high-level planner passes a set of feature templates to the environment characterization subsystem. Once the environment characterization subsystem recognizes the augmentable environment, it provides the high-level planner a list of matched environment features, and two lists of regions R 1 = {r 1 0 , r 1 1 , . . . }, R 2 = {r 2 0 , r 2 1 , . . . } that the features connect. The high-level planner uses the features to find a list of augmentation plans A = {a 0 , a 1 , . . . } from the library. An augmentation plan a i consists of i) a set augmentation modules used for structure construction, ii) the position and orientation of the structure, and iii) the construction controller for the robot. To choose the best augmentation plan from the list A, the high-level planner considers the available augmentation modules in the current environment, current robot configuration, and distance from the structure to the robot goal position. The high-level planner then commands the robot to construct the structure based on the best augmentation plan. After the robot constructs the structure for augmentation a i , the high-level planner considers regions r 1 i and r 2 i to be connected and traversable by the robot.

IV. SYSTEM INTEGRATION
We integrate our environment augmentation tools into the system introduced in [9], as shown in Figure 7. The Fig. 7. System Overview Flowchart high-level planner automatically converts user defined task specifications to controllers from a robot design library. It executes the controller by reacting to the sensed environment, running appropriate behaviors from the design library to control a set of hardware robot modules. Active perception components perform simultaneous localization and mapping (SLAM), and characterize the environment in terms of robot capabilities. Whenever required, the reconfiguration subsystem controls the robot to change configurations.
The system used the Robot Operating System (ROS) 1 for a software framework, networking, and navigation. SLAM was performed using RTAB-MAP [15], and color detection was done using CMVision 2 .
SMORES-EP modules have no sensors that allow them to gather information about their environment. To enable autonomous operation, we use the sensor module shown in Figure 8. The sensor module has a 90mm × 70mm × 70mm body with thin steel plates on its front and back that allow SMORES-EP modules to connect to it. Computation is provided by an UP computing board with an Intel Atom 1.92 GHz processor, 4 GB memory, and a 64 GB hard drive. A USB WiFi adapter provides network connectivity. A front-facing Orbecc Astra Mini RGB-D camera enables the robot to map and explore its environment and recognize objects of interest. A thin stem extends 40cm above the body, supporting a downward-facing webcam. This camera provides a view of a 1m × 0.75m area in front of the sensor module, and is used to track AprilTag [16] fiducials on modules and augmentation modules for reconfiguration and structure building. A 7.4V, 2200mAh LiPo battery provides about one hour of running time.

V. EXPERIMENT RESULTS
Our system can generalize to arbitrary environment augmentations and high-level tasks. We validate our system in two hardware experiments that require the same system to perform tasks requiring very different environment augmentations for successful completion. In both experiments, the robot autonomously perceives and characterizes each environment, and synthesizes reactive controllers to accomplish the task based on the environment. Videos of the full experiments accompany this paper, and are also available online at https://youtu.be/NKj-xulsxco.  Figure 9 shows snapshots throughout the robot's autonomous performance of Experiment I. After recognizing and opening the first drawer, the robot characterizes the environment with the opened drawer and identifies the side of the drawer as a "ledge" feature. The high-level planner recognizes that the ledge is too high for the current configuration to climb, and furthermore that there is no other configuration in the library to which the robot can transform that could climb the ledge, leaving environment augmentation as the only strategy that can complete the task. Observing a ramp structure in the environment, the high-level planner commands the robot to acquire the ramp, place it at the "ledge" feature detected by the characterization algorithm, climb the drawer, and complete the mission.
In a second version of the same experiment, the first drawer is empty. When the robot characterizes the environment containing the drawer, it identifies no "ledge" features, since the drawer no longer matches the requirements of the feature. As a result, it recognizes that environment augmentation is not possible, and the mission cannot be completed. To indicate this, it self-disassembles.

B. Experiment II
The environment for Experiment II consists of two tables separated by a 16 cm gap. The robot begins the experiment on the left table with two wedges and one block. To complete its mission, the robot must cross the gap to reach a pink destination zone on the right table. Figure 10 shows snapshots throughout Experiment II. This time, characterization of the environment identifies that the pink goal zone is in a separate region from the robot, and also identifies several "gap" features separating the two regions. Recognizing that the gap is too wide for any configuration in the design library to cross unassisted, the high-level planner concludes it must build a bridge across the gap to complete its mission. It begins searching for materials, and quickly identifies the three available augmentation modules, which it autonomously assembles into a bridge. It then places the bridge across the gap and crosses to complete its mission.

VI. DISCUSSION
Block and wedge modules demonstrably expand the physical capabilities of SMORES-EP, allowing the system to climb to a high ledge and cross a wide gap to complete tasks that would have been very difficult with the SMORES-EP modules alone. Perception tools accurately characterize augmentable features in the environment. High-level reasoning tools identify when environment augmentation is necessary to complete a high-level task, and reactively sequence locomotion, manipulation, construction, and reconfiguration actions to accomplish the mission. The presented work represents the first time that modular robots have successfully augmented their environment by deploying passive structures to perform high-level tasks.
As with our previous work with autonomous modular robots [9], robustness proved challenging. Out of 8 test runs of Experiment I, the robot successfully completed the entire task once. Table I  of each module, and the higher probability of failure from higher numbers of components in the system. Perception-related errors were another frequent cause of failure. These were due in part to mis-detections by the characterization algorithm, or because the accuracy in finding location and orientation of features was not high enough for the margin of error of the robot when placing structures. Finally, navigation failures occurred throughout development and experiments due to cumulative SLAM errors as the robot navigates the environment. We found that it was important to minimize in-place rotation of the robot, and to avoid areas without many features for visual odometry to use.

A. Future
Future modular robot systems could greatly improve navigation robustness by adding reliable odometry capabilities. This could be difficult for modular robots because of their potentially irregular configurations and gaits.
In the interest of establishing the deployment of structures as an effective means to address high-level tasks, this work does not focus on the speed or scale of construction, demonstrating the use of only small structures (with three elements). Future work might attempt to accelerate construction, build larger structures, and attempt larger-scale tasks with SMORES-EP. In particular, assembly might be significantly accelerated by using multiple builders in parallel, as some other collective robot construction systems have done [2]. To truly scale to large tasks, a large number of block and wedge modules must be available in the environment, or better, autonomously transported into the environment. Developing mechanisms for transporting building material to a task location remains an open challenge for future work.
While our system implementation is tightly coupled to the SMORES-EP hardware, the concepts, system architecture, and theoretical frameworks could be applied widely. In particular, most elements of the framework could be directly applied to the Termes [2] or foam-ramp building robots [4] that have similar construction and locomotion capabilities to SMORES-EP, provided that appropriate sensing and perception capabilities were established.

B. Conclusion
To conclude, this paper presents tools that allow a modular robot to autonomously deploy passive structures as a means to complete high-level tasks involving locomotion, manipulation, and reconfiguration. This work expands the physical capabilities of the SMORES-EP modular robot, and extends our existing frameworks for addressing high-level tasks with modular robots by allowing both the robot morphology and the environment to be altered if doing so allows the task to be completed. We validate our system in two hardware experiments that demonstrate how the hardware, perception tools, and high-level planner work together to complete highlevel tasks through environment augmentation.