---
title: "Greedy Stone Tower Creations with a Robotic Arm"
authors:
  - "Martin Wermelinger"
  - "Fadri Furrer"
  - "Hironori Yoshida"
  - "Fabio Gramazio"
  - "Matthias Kohler"
  - "Roland Siegwart"
  - "Marco Hutter"
doi: "10.24963/ijcai.2018/760"
url: "https://ijcai.org/proceedings/2018/760"
pdf: "https://ijcai.org/proceedings/2018/0760.pdf"
venue: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence"
year: 2018
pages: "5394-5398"
track: "Best Sister Conferences"
keywords:
  - "Robotics: Robotics and Vision"
  - "Robotics: Manipulation"
  - "Planning and Scheduling: Planning Algorithms"
---

# Greedy Stone Tower Creations with a Robotic Arm

Martin Wermelinger, Fadri Furrer, Hironori Yoshida, Fabio Gramazio, Matthias Kohler, Roland Siegwart, Marco Hutter

*Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*, pages 5394-5398. DOI: [10.24963/ijcai.2018/760](https://doi.org/10.24963/ijcai.2018/760)

## Abstract

Predominately, robotic construction is applied as prefabrication in structured indoor environments with standard building materials. Our work, on the other hand, focuses on utilizing irregular materials found on-site, such as rubble and rocks, for autonomous construction. We present a pipeline to detect arbitrarily placed objects in a scene and form a structure out of the detected objects. The next best stacking pose is selected using a searching method employing gradient descent with random initial orientations, exploiting a physics engine. This approach is validated in an experimental setup using a robotic manipulator by constructing balancing vertical stacks without mortars and adhesives. We show the results of eleven consecutive trials to form such towers autonomously using four arbitrarily in front of the robot placed rocks.

## Full text

## 1 Introduction and RelatedWork

Over the last decade, robotics has been introduced to architectural construction not only for safer and more efficient construction, but also for exploring diverse forms [Kohler et al., 2014]. However, there are still intensive manual labor works involved for on-site assembly of these components [Knaack et al., 2012].

Digital fabrication has explored applications of autonomous robots in unstructured on-site operation scenarios [D¨orfler et al., 2016; Sandy et al., 2016], but are restricted to build with regular materials. Building structures with irregularly shaped objects requires structural analysis, e.g., through numerical analysis [Livesley, 1978; Livesley, 1992]. There exist tools for obvious contact surfaces as shown by [Block et al., 2006] and [Whiting et al., 2009]. However with irregularly shaped elements, we need to start from contact detection and then acquire contact surfaces.

∗The authors contributed equally to this work. M.W. for the manipulation tasks, F.F. was responsible for the object detection, H.Y. for the pose searching algorithm.

This can be done in a physics engine, such as Open Dynamics Engine (ODE), for evaluating structural stability [Battaglia et al., 2013]. In our work we also use the simulation environment but with irregular, concave shapes.

Our work focuses on handling objects of arbitrary shape, such as found irregularly shaped stones, without using additional adhesives to build dry-stack compositions. As a case study, discrete rigid elements, such as stones or concrete rubble, are targeted as a building material. The goal is to construct a balancing vertical tower with found objects, while maintaining the structure in static equilibrium using a robotic manipulator. The use of such objects reveals the following challenges. Firstly, individual object instances need to be identified. Secondly, grasping and stacking poses are not obvious, requiring a novel algorithm to pick a 'good' next pose among infinitely many. Thirdly, the stacking task may be performed in unstable situations, requiring recurring structural evaluation and target re-planning after each object placement. To achieve this, we developed an iterative work-flow including precise object detection, motion control, and planning the next target pose (see Fig. 1). As part of this autonomous stacking work-flow, we describe an algorithm suggesting stable poses for stacking, validated by an implementation in a real-world experiment.

This paper makes the following contributions regarding handling irregularly shaped objects:

- a pose searching algorithm considering structural stability using a physics engine
- an object detection pipeline
- an autonomous system for constructing balancing vertical towers using a manipulator

An extended and comprehensive overview of this work is given by [Furrer et al., 2017].

## 2 Object Detection

Before starting with the stacking algorithm, we need to find the objects in the scene. Additionally, during the course of the object stacking, we want to be able to track the locations of the objects. In the scope of this work, we are only considering pre-scanned models of the objects to be detected in the scene. We present an object detection pipeline that consists of the following steps. We start by extracting 3D keypoints from raw point clouds of an RGB-D sensor. These keypoints are then described using keypoint descriptors and matched to keypoints from a pre-scanned object in a descriptor matching step. Using these matches and a clustering step, we find an initial alignment of the scene and the pre-scanned object, which is then refined by applying an Iterative Closest Point (ICP) algorithm. As a final step of the object detection pipeline, we verify that we have enough inlier points by applying the identified pose transform of the object to the scene.

Figure 1: In an offline step we scan a set of objects (top). These objects, or a subset of it, can be distributed arbitrarily on the workspace and get detected by our object detection pipeline (middle-left). From the detected objects the presented pose searching algorithm proposes the next stable stack (middle-right). A motion planner (bottom-right) is used to generate the trajectories to replicate the proposed stack with the robot arm (bottom-left). After placing the object, its pose is measured and used as base for the subsequent pose searching step.

![Image](https://ijcai.org/proceedings/2018/fulltext/760/image_000000_de46ef1874a803b89e3848454a509151430f7d4178cc885256121850f83d27a7.png)

## 2.1 Keypoint Extraction and Description

From an RGB-D sensor we get a scene point cloud PC, in camera frame C. To get keypoints, we used two methods, a simple voxel based subsampling, as well as the Point Cloud Library (PCL) implementation of Intrinsic Shape Signatures (ISS) [Zhong, 2009], which can not only describe the keypoints, but also be used as a keypoint detector. Beside the ISS descriptor, we use Rotational Projection Statistics (RoPS) descriptors [Guo et al., 2013], which were giving us better results in the matching step, at a slightly higher computational cost.

## 2.2 Descriptor Matching and Clustering

We compare a keypoint kC,scene of a scene point cloud with a keypoint of a point cloud of a pre-scanned object kO,object in object frame O. To find a pair of corresponding keypoints kC,scene and kO,object, we set up a kd-tree in descriptor space to find the nearest neighbors. Then we use an approach, presented in [Chen and Bhanu, 2004], to verify that the matched keypoints are geometrical consistent. We select the b best transforms TCO,j,matching, j ∈ {1, . . . , b} that give the most geometrical consistent matches. The transforms TCO,j,matching project the object point cloud PO,object into the camera frame C. Using an ICP step we refine these transforms TCO,j,matching, to get better alignments of the two complete filtered point clouds PC,scene and PO,object. The final transform TCO is obtained after checking the inlier ratio of the transformed point clouds.

## 2.3 Object in Robot ArmFrame

To transform the point cloud of the localized object PO,object into the robot arm frame R, we apply the previously detected best transform TCO, a fixed pre-calibrated transform TT C from the camera frame C to the robot arm tooltip frame T , and the transform given by the robot state TRT between the tooltip frame T and the robot arm frame R:

<!-- formula-not-decoded -->

## 3 Pose Searching

Our goal is to construct a vertical tower consisting of irregularly shaped objects from a subset S of available objects oi ∈ S ⊆ O, where O denotes the complete set of given objects. Within the set S, we want to find the best object and its target pose. The search space is twofold: discrete object space and continuous pose space. To find a stable pose on a vertical stack, our pose searching method places each object oi on the top object of the existing stack in a dynamic simulation using a physics engine. For evaluating each object's 'goodness' with a certain pose pi, we introduce a cost function that maximizes the support polygon Si's area Ai of the newly placed object oi and minimizes other considerable parameters, such as kinetic energy. Throughout this process, several initial poses are tested with fixed initial positions but randomized orientations. We are sampling our initial orientations randomly, to keep the problem viable in large problem sets, where a holistic pose sampling would become intractable. The returned cost value is interchangeable among available objects in S, thus we find the best object o∗ with the best pose p∗ .

## 3.1 Valid Contact Pose Search

To find a valid contact pose, we set the object to an initial pose in simulation that is close to the existing stack, but not yet touching it. The initial pose pinit,i of a new object oi ∈ O consists of its initial position rinit,i and its initial orientation qinit,i. The initial position is set with an offset from the centroid Cj of the last placed object's support polygon Sj along the normal direction nj of Sj (see Fig. 2). To obtain the initial orientation, the detected object orientation is rotated around a randomized axis with the random angle θ ∈ [-θinit, θinit].

Figure 2: (1) The initial position rinit,i of object oi is set along the normal direction nj of Sj of the previously placed object oj . (2) We apply an attraction force F to object oi to get contact points between the two objects.

![Image](https://ijcai.org/proceedings/2018/fulltext/760/image_000001_27aee44d25fbb3a5ca0838c93f2570168ebb0f2df2b2ff19734d055338c449ef.png)

Figure 3: (3): Projection P ′ i of the Center of Mass (CoM) position Pi onto the support polygon Sj. (4): Contact pose pcontact,i resulting from the valid pose search algorithm.

![Image](https://ijcai.org/proceedings/2018/fulltext/760/image_000002_b6d3e1c916de96a52d7a7ab31394746c7a7227fa80a60de758369cd969eb21c5.png)

For evaluating physical stability of object oi, it is a valid approach to analyze whether P ′ i , the projection of the CoM position Pi onto the support polygon Si, is inside the support polygon or not (see Fig. 3). In order to find a valid support polygon Si for an irregularly shaped object oi, we consider the contact points of the object to other objects. The assumed contact situations are simple; either on a flat surface for the first stack, or contact points between two rigid body objects with parallel contact normals.

To assure that pinit,i results in a valid contact pose pcontact,i, we apply an attraction force F along the thrust line direction vector vi to the object oi (see Fig. 2). During this process, we continuously check whether the projection P ′ i of the CoM position lies within the support polygon (see Fig. 3). As soon as the number of contacts Ncontact(pi) between oi and the existing stack is at least three (see Fig. 3), the resulting pose pcontact,i is evaluated by oi's kinetic energy Ekin(pcontact,i) with a threshold value Ekin,stable. By evaluating the kinetic energy, we limit the viable set of poses to the ones that cause minimal motion of the existing stack.

## 3.2 Contact Pose Refinement

We assign a cost to each valid contact pose pcontact,i to compare its 'goodness' in terms of a robust object pose, which allows further stacking. Therefore, we maximize the area of the support polygon Si as well as minimize the kinetic energy Ekin, and surface normal deviation from the thrust line ni for reducing sheer forces. To robustly find the support polygon Si from the sparse contacts between oi and the existing stack, contacts over several simulation update steps are collected and simplified [Alliez et al., 2016], [Karavelas, 2016].

Given the area Ai of the support polygon Si, the kinetic energy Ekin(pcontact,i), the dot product ‖ni · vi‖, where vi is the thrust line direction vector, the length ‖rPjPi ‖ between Pi and the CoM of the previously stacked object Pj, we define the cost function as

<!-- formula-not-decoded -->

where wj are manually selected weights of the individual cost function components.

After assigning the cost to the valid contact pose pcontact,i, gradient descent is performed for searching the local optimum pose p∗local,i until the cost converges. To compute the gradient, the contact pose pcontact,i is perturbed with a small pose step δp.

After finding a local optimum pose p∗local,i , a new randomized rotation is assigned to the initial pose pinit,i and the process is repeated until x local solutions are found. The pose with minimum cost is selected as a solution p∗i for object oi. We iterate the entire process over all objects of the available subset S, returning the best object o∗ with the best pose p∗ .

## 4 Experimental Setup

To show the applicability and repeatability of the presented pose searching and object detection methods, we implemented the algorithms, using a robot arm to perform autonomous dry-stacking as in Figure 1. The goal is to create a vertical tower out of randomly placed irregularly shaped objects whose mechanical and geometric properties are known.

## 4.1 Experimental Setup

We use a set of six natural lime stones as objects because they have challenging properties for the stacking task, they are of irregular shape and have low friction coefficients. The object's geometric shape were previously scanned and the point cloud and mesh model were scaled to a reasonable resolution of 500 mesh faces. The weight, CoM position, and moment of inertia of each stone were measured and added to the geometric model description. The friction coefficient was estimated with a low value of µstone = 0.1 and uniformly applied to all stones. For manipulating the objects, we use a robotic arm equipped with a three-finger gripper as depicted in Figure 4. The object detection is performed with an RGB-D depth camera mounted on the robot arm. A force-torque sensor mounted at the attaching point of the gripper is used to detect impact during the placement of the object.

Figure 4: An overview of the used hardware setup: a ROBOTIQ 3-finger gripper, a FT150 force torque sensor, and an Intel®RealSense™ SR300 RGB-D camera are attached to a UR10 arm.

![Image](https://ijcai.org/proceedings/2018/fulltext/760/image_000003_09b4e776f03b800dfc1540aa9d18dbd258c5e2e0d31531968eb692fd3af89c88.png)

Figure 5: The cost of the selected target pose of an individual stone for all eleven runs at each level of the stack. A higher cost indicates a less preferable target pose. '+' denotes a successful stacking, failed attempts are represented with a 'o'. Each color corresponds to an individual run.

![Image](https://ijcai.org/proceedings/2018/fulltext/760/image_000004_3acda68cfd1b4bb5284a37fc0003423770d7e4e246215dde41ba641a49aa34c3.png)

The work-flow of autonomously creating a vertical stack of arbitrarily placed stones is shown in Figure 1. This task is performed by continuously executing a loop consisting of object detection, pose searching and object manipulation. The stacking task is terminated once the pose searching no longer finds a feasible solution from the available objects or the stacking was not successful.

## 4.2 Results

The robotic system performed the vertical stacking task in eleven consecutive runs with an alternating set of four stones 1 . In two of these runs, the system succeeded to construct a stack out of all four available stones. In six cases the system was able to vertically stack three stones, but failed to place the fourth stone, and in three cases the system did not succeed to stack the third stone. The average cost where the robot failed to place the object was 2.5 times higher than the average cost of the last pose the system was able to successfully stack. This shows that these poses were already identified as less favourable compared to the ones that were successfully stacked. If the cost at a previous step is high, the probability increases that the following stone placement will fail. See for example the high cost of the second stone in run 6 and 7 (see Figure 5).

1 Watch the accompanying video: https://www.youtube.com/ watch?v=bXz52KMGUng

On average, a trial to construct a vertical stack lasted 271.0 s, where the main fraction of this time (61%) is spent for the manipulation task that includes path planning, arm and gripper motion.

## 5 Conclusion

In this paper, we introduced an autonomous robotic system that constructs a balancing vertical tower out of irregularly shaped stones without using extra materials. Its work-flow consists of a continuous loop with object detection, target pose search, physical manipulation, and evaluation. We presented an object detection pipeline suited to localize irregularly shaped objects in a scene and a target pose searching algorithm, based on a physics engine, to generate stable stacks. The proposed algorithms were implemented and tested on a robotic system (a fixed platform in a controlled environment with a flat terrain, and pre-scanned objects). The system showed to be able to perform stacking tasks autonomously and thus validating the proposed pose searching algorithm.

Aiming at more practical situations, we want to focus on construction with unseen objects. This involves the segmentation of unknown objects in a scene and their handling with incomplete information. Solving this can either be achieved by creating object models in the construction process or by applying techniques where we do not require a specific representation of the object, as shown in [Breyer et al., 2018] for grasping objects. We plan to extend this work to place objects including force-torque sensor readings. Furthermore, we want to create more complex target shapes, such as arches or walls.

## Acknowledgements

This work was supported in part by the Swiss National Science Foundation (SNF), the National Centre of Competence in Research Digital Fabrication.

## References

1. [Alliez et al., 2016] Pierre Alliez, Clément Jamin, Quentin Mérigot, Jocelyn Meyron, Laurent Saboret, Nader Salman, and Shihao Wu. Point set processing. In CGAL User and Reference Manual. CGAL Editorial Board, 4.8.1 edition, 2016.
2. [Battaglia et al., 2013] Peter W. Battaglia, Jessica B. Ham- rick, and Joshua B. Tenenbaum. Simulation as an engine of physical scene understanding. Proceedings of the Na- tional Academy of Sciences, 110(45):18327-18332, 2013.
3. [Block et al., 2006] Philippe Block, Thierry Ciblac, and John Ochsendorf. Real-time limit analysis of vaulted ma- sonry buildings. Computers & structures, 84(29):1841- 1852, 2006.
4. [Breyer et al., 2018] Michel Breyer, Fadri Furrer, Tonci Novkovic, Roland Siegwart, and Juan Nieto. Flexible Robotic Grasping with Sim-to-Real Transfer based Rein- forcement Learning. ArXiv e-prints, March 2018.
5. [Chen and Bhanu, 2004] Hui Chen and Bir Bhanu. 3D free- form object recognition in range images using local sur- face patches. Pattern Recognition, 2004. ICPR 2004. Pro- ceedings of the 17th International Conference on, 3:136- 139 Vol.3, 2004.
6. [Dörfler et al., 2016] Kathrin Dörfler, Timothy Sandy, Markus Giftthaler, Fabio Gramazio, Matthias Kohler, and Jonas Buchli. Mobile Robotic Brickwork, pages 204-217. Springer International Publishing, Cham, 2016.
7. [Furrer et al., 2017] Fadri Furrer, Martin Wermelinger, Hi- ronori Yoshida, Fabio Gramazio, Matthias Kohler, Roland Siegwart, and Marco Hutter. Autonomous Robotic Stone Stacking with Online next Best Object Target Pose Plan- ning. In Robotics and Automation (ICRA), 2017 IEEE In- ternational Conference on, pages 2350-2356. IEEE, 2017.
8. [Guo et al., 2013] Yulan Guo, Ferdous Sohel, Mohammed Bennamoun, Min Lu, and Jianwei Wan. Rotational pro- jection statistics for 3D local surface description and ob- ject recognition. International Journal of Computer Vi- sion, 105(1):63-86, 2013.
9. [Karavelas, 2016] Menelaos Karavelas. 2D segment delau- nay graphs. In CGAL User and Reference Manual. CGAL Editorial Board, 4.8.1 edition, 2016.
10. [Knaack et al., 2012] Ulrich Knaack, Sharon Chung-Klatte, and Reinhard Hasselbach. Prefabricated Systems : Prin- ciples of Construction. Birkhäuser, Basel, 2012.
11. [Kohler et al., 2014] Matthias Kohler, Fabio Gramazio, and Jan Willmann. The Robotic Touch: How Robots Change Architecture. Park Books, 2014.
12. [Livesley, 1978] Robert Kenneth Livesley. Limit analysis of structures formed from rigid blocks. International Jour- nal for Numerical Methods in Engineering, 12(12):1853- 1871, 1978.
13. [Livesley, 1992] Robert Kenneth Livesley. A computational model for the limit analysis of three-dimensional masonry structures. Meccanica, 27(3):161-172, 1992.
14. [Sandy et al., 2016] Timothy Sandy, Markus Giftthaler, Kathrin Dörfler, Matthias Kohler, and Jonas Buchli. Au- tonomous repositioning and localization of an in situ fabri- cator. In Robotics and Automation (ICRA), 2016 IEEE In- ternational Conference on, pages 2852-2858. IEEE, 2016.
15. [Whiting et al., 2009] Emily Whiting, John Ochsendorf, and Frédo Durand. Procedural modeling of structurally-sound masonry buildings. In ACM SIGGRAPH Asia 2009 Pa- pers, SIGGRAPH Asia '09, pages 112:1-112:9, New York, NY, USA, 2009. ACM.
16. [Zhong, 2009] Yu Zhong. Intrinsic shape signatures: A shape descriptor for 3d object recognition. In 2009 IEEE 12th International Conference on Computer Vision Work- shops, ICCV Workshops, pages 689-696, Sept 2009.