Kasper Støy


Unmaintained since 2007 - find newer stuff here.

HomeResearchPublicationsCoursesPrivate

Ph.D. Thesis

Title Emergent Control of Self-Reconfigurable Robots
Authors Kasper Støy
Published AdapTronics Group, The Maersk Mc-Kinney Moller Institute for Production Technology, University of Southern Denmark, 2003
Download
Pdf

Journal Papers (4)

Title Using cellular automata and gradients to control self-reconfiguration
Authors Kasper Stoy
Abstract Self-reconfigurable robots are built from modules, which are autonomously able to change the way they are connected. Such a robot can,cthrough this self-reconfiguration process, change its shape. The process has proved to be difficult to control, because it involves control of a distributed system of mechanically coupled modules connected in time-varying ways. In this paper we present an approach to the control problem where the desired configuration is grown from an initial seed module. Seeds produce growth by creating a gradient in the system, using localcommunication, which spare modules descend to locate the seed. The growth is guided by a cellular automaton, which is automatically generated on the basis of a three-dimensional CAD model or a mathematical description of the desired configuration. The approach is evaluated in simulation and we find that the self-reconfiguration process always converges and the time to complete a configuration scales approximately linearly with the number of modules. However, an open question is how the simulation results transfer to a physically realized self-reconfigurable robot.
Published Robotics and Autonomous Systems, Volume 54, January 2006, Pages 135-141, Special issue on the best papers presented at IAS-8
Download
Pdf
Title A simple approach to the control of locomotion in self-reconfigurable robots
Authors Kasper Støy, Wei-Min Shen, and Peter Will
Abstract In this paper we present role-based control which is a general bottom-up approach to the control of locomotion in self-reconfigurable robots. We use role-based control to implement a caterpillar, a sidewinder, and a rolling track gait in the CONRO self-reconfigurable robot consisting of eight modules. Based on our experiments and discussion we conclude that control systems based on role-based control are minimal, robust to communication errors, and robust to reconfiguration.
Published Robotics and Autonomous Systems, Volume 44, Issues 3-4 , 30 September 2003, Pages 191-199, Special issue on the best papers presented at IAS-7
Download
Postscript
Pdf
Title Using Role Based Control to Produce Locomotion in Chain-Type Self-Reconfigurable Robots
Authors Kasper Støy, Wei-Min Shen, and Peter Will
Abstract This paper presents a role based approach to the problem of controlling locomotion of chain-type self-reconfigurable robots. In role based control all modules are controlled by identical controllers. Each controller consists of several playable roles and a role selection mechanism. A role represents the motion of a module and how it synchronizes with connected modules. A controller selects which role to play depending on the local configuration of the module and the roles being played by connected modules. We use role based control to implement a sidewinder and a caterpillar gait in the CONRO self-reconfigurable robot. The robot is made from up to nine modules connected in a chain. We show that the locomotion speed of the caterpillar gait is constant even with loss of 75\% of the communication signals. Furthermore, we show that the speed of the caterpillar gait decreases gracefully with a decreased number of modules. We also implement a quadruped gait and show that without changing the controller the robot can be extended with an extra pair of legs and produce a hexapod gait. Based on these experiments we conclude that role based control is robust to signal loss, scales with an increased number of modules, and is a simple approach to the control of locomotion of chain-type self-reconfigurable robots
Published IEEE Transactions on Mechatronics, special issue on self-reconfigurable robots, 7(4), pages 410-417, 2002.
Download
Postscript
Pdf
Title LOST: Localization-Space Trails for Robot Teams
Authors Richard T. Vaughan, Kasper Støy, Gaurav S. Sukhatme and Maja J. Mataric
Abstract We describe Localization-Space Trails (LOST), a method that enables a team of robots to navigate between places of interest in an initially unknown environment using a trail of landmarks. The landmarks are not physical; they are waypoint coordinates generated on-line by each robot and shared with team-mates. Waypoints are specified in each robot s local coordinate system, and contain references to features in the world that are relevant to the team s task and common to all robots. Using these task-level references, robots can share waypoints without maintaining a global coordinate system. The method is tested in a series of real-world multi-robot experiments. The results demonstrate that the method (i) copes with accumulating odometry error; (ii) is robust to the failure of individual robots; (iii) converges to the best route discovered by any robot in the team. In one experiment, a team of four autonomous mobile robots performs a resource transportation task in our uninstrumented office building. Despite significant divergence of their local coordinate systems, the robots are able to share waypoints, forming and following a common trail between two predetermined locations for more than 3 hours, traveling a total of 8.2km (5.1 miles) before running out of power. Designed to scale to large populations, LOST is fully distributed, with low cost in processing, memory and bandwidth. It combines metric data about the position of features in the world with instructions on how to get from one place to another; producing something between a map and a plan.
Published IEEE Transactions on Robotics and Automation, special issue on multi-robot systems, 18(5), pages 796-812, 2002.
Download
Postscript
Pdf

Refereed Conference Papers (18) and workshop papers (2)

Title Hierarchical Robots
Authors K. Stoy, A.Lyder, R.F.M. Garcia, and D. Christensen
Abstract This paper introduces the concept of hierarchical robots, which is a type of modular robots assembled from a hierarchy of modules, and a preliminary realization of this concept: the Odin robot. Odin currently consists of ten modules of two different classes, one class of modules provide structure and the other actuation. We describe the mechanical design of these modules and their electrical design with specific focus on their hybrid communication system whose topology can be changed on-line. We demonstrate the features of this communication system in a simple experiment and also demonstrate how the assembled Odin robot can produce locomotion. While it is too early to make a conclusion regarding the usefulness of hierarchical robots in general, we think that our work indicates that we may be able to simplify the manufactured modules at the bottom of the hierarchy while increasing the functionality of the assembled hierarchical robot.
Published In Proceedings of the IROS Workshop on Self-Reconfigurable Modular Robots, San Diego CA, 2007 (to appear).
Download
Pdf

Title Hybrid Approach: A Self-Reconfigurable Communication Network for Modular Robots
Authors R.F.M. Garcia, K. Stoy, D.J. Christensen and A. Lyder
Abstract We present a novel hybrid communication system for modular robots, based on inter-module buses that can connect on-demand to form arbitrary network topologies. In addition to describing the implementation of this hybrid communication system, we analyse transfer rates and reliability, validating the results using a Spice 1 simulation and a proof-ofconcept experiment performed on a hardware prototype. Thus, we find the system is fast, since it has a potential to provide a maximum transfer rate of 9.9Mbps divided by the maximum bus length measured in meters, with buses as large as 256 modules. The system is also found to be small in size, power saving and reliable. These features, in combination with its flexibility, make hybrid communication suitable for modular robots.
Published In Proceedings of the International Conference on Robots and Communication, Athens, Greece, 2007. (to appear).
Download
Pdf

Title Towards Artificial ATRON Animals: Scalable Anatomy for Self-Reconfigurable Robots
Authors D.J. Christensen, D. Brandt, and K. Stoy
Published In Proceedings of the RSS Workshop on Self-Reconfigurable Modular Robots, Philadelphia PA, August 2006.
Download
Pdf

Title The Deformatron Robot: a Biologically Inspired Homogeneous Modular Robot
Authors K. Stoy
Abstract The Deformatron robot is a homogeneous, modular robot. The Deformatron modules can play one of three roles in the physical structure of the robot: bone, tendon, and muscle. These roles are inspired by their biological counterparts. This combination of roles gives us a modular robot which potentially may have enough structural strength and actuation power to manipulate its environment and work in three dimension even in the presence of gravity. In this paper we present our preliminary LEGO-based prototype of the Deformatron robot. We measure and analyse the properties of the system in terms of structural strength and actuation power. Finally, we conclude that the Deformatron concept may provide an avenue of research which may make modular robots stronger and better suited for real world task environments.
Published In proceedings of IEEE International Conference on Robotics and Automations, (ICRA), Orlando, USA, pages 2527-2531, May 16-18, 2006
Download
Pdf

Title Selecting a Meta-Module to Shape-Change the ATRON Self-Reconfigurable Robot
Authors D.J. Christensen and K. Støy
Abstract The ATRON self-reconfigurable robot consists of simple one degree of freedom ATRON modules. The motion capabilities of an individual module are therefore quite limited. To compensate for this, meta-modules composed of more than one module are used to shape-change the system. Meta-modules emerge from the environment created by other modules, move on the surface of other modules and stop at a new position. The flow of meta-modules, from one place to another on the structure of modules, realizes the desired self-reconfiguration. In this paper we compare six different meta-module types composed of ATRON modules. Variations of meta-module morphology and meta-actions are investigated for its ability to shapechange the robot. We conclude that two of the investigated meta-module types are able to shape-change the robot to an acceptable extent.
Published In proceedings of IEEE International Conference on Robotics and Automations, (ICRA), Orlando, USA, pages 2532-2538, May 16-18, 2006
Download
Pdf

Title How to Construct Dense Objects with Self-Reconfigurable Robots
Authors K. Stoy
Abstract Self-reconfigurable robots can change their shape by rearranging the modules from which they are built. This self-reconfiguration process has proven difficult to control, because it involves control of a distributed system of autonomous, but mechanically coupled modules connected in time-varying ways. In this work we address this control problem and specifically look at how to construct dense configurations. The basic idea behind our solution is that holes inside the desired configuration and modules outside attract each other. The effect is that holes propagate to the surface of the desired configuration and modules outside move in to fill them. This basic solution is augmented with a scaffold and gradient-based algorithm which ensures that the robot does not get stuck in local minima or get disconnected during self-reconfiguration. The approach is evaluated in simulation and we find that the self-reconfiguration process always converges and the time to complete a configuration scales approximately linearly with the number of modules. This is, to the best of our knowledge, the first time this result has been obtained for dense configuration.
Published In proceedings of European Robotics Symposium, (EUROS), Palermo, Italy, pages 27-37, May 12-15, 2006
Download
Pdf

Title Self-Repair Through Scale Independent Self-Reconfiguration
Authors K. Stoy and R. Nagpal
Abstract Self-reconfigurable robots are built from modules which are autonomously able to change the way they are connected, thus changing the overall shape of the robot. This self-reconfiguration process is difficult to control, because it involves the distributed coordination of large numbers of identical modules connected in time-varying ways. We present an approach where a desired shape is grown based on a scalable representation of the desired configuration which is automatically generated from a 3D CAD model. The size of the configuration is adjusted continually to match the number of modules in the system. This has the advantage that if modules are removed or added, the system automatically adjusts its scale and thus self-repair is obtained as a side effect. This capability is achieved by distributed, local rules for module movement that are independent of the goal configuration. We compare the scale independent approach to one where the desired configuration is grown directly at a fixed scale. We find that the features of the scale independent approach come at the expense of an increased number of moves, messages, and time steps taken to reconfigure.
Published In proceedings of IEEE/RSJ International Conference on Robots and Systems, (IROS), Sendai, Japan, pages 2062-2067, Sep 30-Oct 2, 2004
Download
Pdf

Title Self-Reconfiguration Using Directed Growth
Authors K. Stoy and R. Nagpal
Abstract Self-reconfigurable robots are built from modules which are autonomously able to change the way they are connected, thus changing the overall shape of the robot. This process is difficult to control because it involves the distributed coordination of large numbers of identical modules connected in time-varying ways. We present an approach to self-reconfiguration where the desired configuration is grown from an initial seed module. Seeds produce growth by creating a recruitment gradient, using local communication, which spare modules climb to locate the seed. The growth is guided by a novel representation of the desired configuration, which is automatically generated from a 3D CAD model. This approach has two salient features: (1) the representation is concise, with a size proportional to the global shape rather than the number of modules and (2) there is a clean separation between the goal and the local, goal independent rules used by the modules. We demonstrate three implementations of the local rules for recruitment, and show how one can trade-off the number of moves and messages, against time taken to reconfigure.
Published In proceedings of the 7th International Symposium on Distributed Autonomous Robotic Systems (DARS 2004), pages 1-10, Toulouse, France, June 23-25, 2004
Download
Pdf

Title Controlling Self-Reconfiguration using Cellular Automata and Gradients
Selected to appear in Journal of Robotics and Autonomous Systems, special issue on the best of IAS-8
Authors K. Støy
Abstract Self-reconfigurable robots are built from modules, which are autonomously able to change the way they are connected. Such a robot can, through this self-recon-figuration process, change its shape. The process has proven to be difficult to control, because it involves control of a distributed system of mechanically coupled modules connected in time-varying ways. In this paper we present an approach to the self-reconfiguration problem where the desired configuration is grown from an initial seed module. Seeds produce growth by creating a gradient in the system, using local communication, which spare modules climb to locate the seed. The growth is guided by a cellular automaton, which is automatically generated based on a three-dimensional CAD model or a mathematical description of the desired configuration. The approach is evaluated in simulation and we find that the self-reconfiguration process always converges and the time to complete a configuration scales approximately linearly with the number of modules. However, an open question is how the simulation results transfer to a physically realized self-reconfigurable robot.
Published In proceedings of the 8th international conference on intelligent autonomous systems (IAS-8), pages 693-702, Amsterdam, The Netherlands, March 10-13, 2004
Download
Pdf

Title Implementing Configuration Dependent Gaits in a Self-Reconfigurable Robot
Authors K. Støy, W.-M. Shen, and P. Will
Abstract In this paper we examine locomotion in the context of self-reconfigurable robots. Self-reconfigurable robots are robots built from many connected modules. A self-reconfigurable robot can change its shape and configuration by changing the way these modules are connected. The focus of this paper is to understand how several locomotion gaits can be represented in such a robot and how the robot can select one of these gaits depending on its configuration. We implement a control system based on role based control in a physical self-reconfigurable robot built from seven modules. In several experiments we successfully demonstrate that the robot can change from a sidewinder snake gait to a quadruped walking gait when the robot is manually reconfigured from a chain to a quadruped configuration. We conclude that role based control is a promising control method for controlling locomotion of self-reconfigurable robots.
Published In proceedings of the 2003 IEEE international conference on robotics and automation (ICRA'03), pages 3828-3833, Tai-Pei, Taiwan, september 16-18, 2003.
Download
Pdf

Title On the Use of Sensors in Self-Reconfigurable Robots
Awarded best philosophical paper of the conference
Authors K. Støy, W.-M. Shen, and P. Will
Abstract In this paper we investigate the use of sensors in self-reconfigurable robots. We review several physically realized self-reconfigurable robots and conclude that little attention has been paid to the use of sensors. This is unfortunate since sensors can provide essential feedback that can be used to guide self-reconfiguration and control. In the systems that do use sensor feedback, the feedback is used locally on each module. However we identify a need in some situations to use sensor feedback globally. We therefore propose an approach where raw sensor values are abstracted and propagated to all modules. The sensor values are abstracted differently depending on the position of the producing sensor on the robot. We combine this approach with role based control, a control method for self-reconfigurable robots that we have developed earlier. We demonstrate that by combing these two approaches it is possible to make a self-reconfigurable robot consisting of six modules walk and avoid obstacles. However the reaction time of the robot is slow and therefore we discus possible ways of reducing the reaction time.
Published In proceedings of the 7th international conference on simulation of adaptive behavior (SAB'02), pages 48-57, Edinburgh, UK, August 4-9, 2002.
Download
Postscript
Pdf

Title How to Make a Self-Reconfigurable Robot Run
Authors K. Støy, W.-M. Shen, and P. Will
Abstract In this paper we present a multiagent based control algorithm for self-reconfigurable robots. These robots are robots made from a possibly large number of independent modules. In the proposed control algorithm all modules run identical programs, but may play different roles. The modules decide what role to play based on their local configuration and information propagated down to them through the configuration tree. A role consists of a cyclic motion, the period of this motion, and a set of delays. The delays specify the phase delay of the cyclic motions of the child modules compared to the parent. These delays are used to coordinate the motions of the individual module to obtain a coordinated global behavior. We use this general algorithm to implement locomotion in a legged self-reconfigurable robot. We demonstrate that this algorithm successfully produces quadruped and hexapod gaits in a real self-reconfigurable robot made from up to nine independent autonomous modules. We show that the control algorithm scales and argue that the algorithm is minimal, robust to module failures, to loss of communication signals, and to interchange of modules.
Published In proceedings of the 1st international joint conference on autonomous agents and multiagent systems (AAMAS'02), pages 813 - 820, Bologna, Italy, July 15-19, 2002
Download
Postscript
Pdf

Title Exploiting Task Regularities to Transform Between Reference Frames in Robot Teams
Authors Richard T. Vaughan, Kasper Støy, Gaurav S. Sukhatme and Maja J. Mataric
Abstract We describe a team of robots that uses a trail of landmarks to navigate between places of interest. The landmarks are not physical; they are waypoint coordinates generated online by each robot and shared with team-mates over the network. Waypoints are specified with reference to features in the world that are relevant to the team's task and common to all robots. Using such task-level features as landmarks avoids the need to sense and name physical landmarks. Using these common landmarks, each robot can transform waypoint coordinates into its local reference frame, avoiding the cost of maintaining a fixed global coordinate system. The algorithm is tested in an experiment in which a team of 4 autonomous mobile robots run in our office building for more than 3 hours, traveling a total of 8.2km (5.1 miles). Despite signicant divergence of their local coordinate systems, they are able to share waypoints, forming and following a common trail between two fixed locations.
Published In proceedings of the IEEE international conference on Robotics and Automation (ICRA'02), pages 2599-2605, Washington DC, USA, May 11-15, 2002.
Download
Postscript
Pdf

Title Global Locomotion from Local Interaction in Self-Reconfigurable Robots
Selected to appear in Journal of Robotics and Autonomous Systems, special issue on the best of IAS-7
Authors K. Støy, W.-M. Shen, and P. Will
Abstract We present a general distributed control algorithm for achieving locomotion of a self-reconfigurable robot. In this algorithm each module continuously performs a cyclic sequence of actions with a period T. When a specified fraction of this period d has elapsed a signal is sent to all child modules. Upon receiving this signal the child module resets its action sequence making it delayed d compared to its parent. The algorithm is minimal and robust to loss of synchronization signals and change in the number of modules. We show in three different experiments that the algorithm can be used to implement a caterpillar, a sidewinder, and a rolling wheel gait in a real self-reconfigurable robot consisting of eight modules.
Published In proceedings of the 7th international conference on intelligent autonomous systems (IAS-7), pages 309-316, Marina del Rey, California, USA, March 25-27, 2002
Download
Postscript
PDF

Title Most Valuable Player: A Robot Device Server for Distributed Control
Authors B.P. Gerkey, R.T. Vaughan, K. Støy, A. Howard, G.S. Sukhatme, and M.J. Mataric
Abstract Successful distributed sensing and control require data to flow effectively between sensors, processors and actuators on single robots, in groups and across the Internet. We propose a mechanism for achieving this flow which we have found to be powerful and easy to use; we call it Player. Player combines an eÆcient message protocol with a simple device model. It is implemented as a multi-threaded TCP socket server that provides transparent network access to a collection of sensors and actuators, often comprising a robot. The socket abstraction enables platform and language independent control of these devices, allowing the system designer to use the best tool for the task at hand. Player is freely available from http://robotics.usc.edu/player.
Published In proceedings of the International Conference on Intelligent Robotic Systems, pages 1226-1231, Maui, Hawaii, USA, 2001
Also appears in Proceedings of the Second International Workshop on Infrastructure for Agents, MAS, and Scalable MAS at Autonomous Agents 2001, Montreal, Canada, May 29, 2001.
Download
Postscript
Pdf
Links
Player home

Title Using Situated Communication in Distributed Autonomous Mobile Robots
Author Kasper Støy
Abstract When using communication in multi-robot systems it's often not desirable to choose an abstract form of communication that separates the messages from the physical environment in which they have meaning. If the messages are separated from the environment localization information has to be encoded into the messages in order for the receiver to be able to situate the content of the messages. Here we point out that if we instead use a situated form of communication that exploits the physical properties of the signal transferring the message localization information is not needed. We demonstrate this idea by showing how an extremely simple control system that uses short range communication can keep four LEGO Mindstorms robots together in a group. It s also discussed how this idea can be extended to make it possible to simplify path planning in multi-robot systems.
Published In proceedings of the 7th Scandinavian Conference on Artificial Intelligence (SCAI-7), pages 44-52, Odense, Denmark, Feb 19-21, 2001
Download
Postscript
Pdf

Title Blazing a Trail: Insect-inspired Resource Transportation by a Robot Team
Author R.T. Vaughan, K. Støy, G.S. Sukhatme and M.J. Mataric
Abstract We demonstrate a team of real robots that cooperate to robustly transport resource between two locations in an unknown environment. The robots use a trail laying and following algorithm inspired by the trail following of ants and the waggle dance of honey bees. Rather than directly marking their environment, the robots announce landmarks in their odometric localization space. The system tolerates significant odometric drift before it breaks down.
Published In proceedings of the 5th international symposium on distributed autonomous robot systems (DARS), pages 111-120, Knoxville, Tennessee, USA, October 4-6, 2000
Download
Postscript
Pdf

Title Whistling in the Dark: Cooperative Trail Following in Uncertain Localization Space
Author R.T. Vaughan, K. Støy, G.S. Sukhatme and M.J. Mataric
Abstract We demonstrate that a simulated group of robots can cooperate to robustly transport resource between two areas in an unknown environment using an algorithm inspired by the trail following of ants and the waggle dance of honey bees. Rather than directly marking the environment, the robots announce their successful paths through a common localization space. It is found that the algorithm is robust to significant localization error, suggesting that the method will be viable for teams of real robots.
Published In proceedings of the 4th international conference on autonomous agents, pages 187-194, Barcelona, Spain, June 3-7, 2000
Download
Postscript
Pdf

Title Go ahead, make my day: robot conflict resolution by aggressive competition
Author R.T. Vaughan, K. Støy, G.S. Sukhatme and M.J. Mataric
Abstract We examine a simulated but realistic multi-robot transport task that suffers from spatial interference. Previously described techniques to reduce interference are not appropriate for this and related tasks. We demonstrate the utility of an aggressive competition to reduce interference and increase efficiency in our system. A controller is described which breaks deadlocks in favour of the most 'aggressive' robot. Sumulation trials are performed to evaluate a variaty of aggression functions. Our results and subsequent discussion sugest that neither a linear domonance hierarchy nor a simple sensor bias method offer any advantage over a random outcome. Finally we discuss some strategies that might favour the 'correct' outcome of competions to increase the effieciency of the system. We are currently implementing these controllers on a real robot team.
Published In proceedings of the 6th international conference on the simulation of adaptive behavior, pages 491-500, Paris, France, September 11-16, 2000
Download
Postscript
Pdf

Title Adaptive LEGO Robots. A Robot=Human View on Robotics
Author H.H. Lund, C. Bjerre, J.H. Nielsen, M. Nielsen, K. Støy
Abstract In many applications, robots were viewed as a machine. This has resulted in interaction and actuation which is characteristic for machines. When constructing adaptive LEGO robots, we take another view, namely that the robot should resemble a human (or a biological creature) rather than a machine. This has implication on the interaction, the actuation and the control of the robot. Here, I will describe how the robot-as-human approach is in-vestigated in a number of LEGO Mindstorms robot applications. These include making facial expressions, which allows a LEGO robot to express internal "moods", and thereby we might achieve a better human-robot interaction. Another application is the Adaptive LEGO Pet Robot. The Adaptive LEGO Pet Robot's control is based on a modular behaviour system, where a number of the modules are evolved neural networks. Further, the Adaptive LEGO Pet Robot has a number of internal drives such as restlessness and hunger, which allow the robot to react on the internal drives. The human-robot interaction is facilitated by allowing the human to train the LEGO pet robot (rather than to program the robot) to make associations between spoken words (via speech recognition) and evolved behaviours. The Adaptive LEGO Pet Robot is an example of scaling up evolutionary robotics to complex behaviours by combining evolutionary robotics with behaviour-based robotics.
Published In proceedings of IEEE Systems, Man, and Cybernetics, 1999
Download
Postscript
Pdf

Tech Reports and Workshop Proceedings

Title Player Robot Server
Authors B. Gerkey, K. Støy, and R.T. Vaughan
Published In institute for robotics and intelligent systems technical report IRIS-00-391, University of Southern California, 2000
Download
Postscript
Pdf
Links
Player home

Master's Thesis

Title Adaptive Control Systems for Autonomous Robots
Author K. Støy
Published 1999
Download
Postscript
Pdf