This paper proposes a dynamic and near-optimal power sharing mechanism for self-reconfigurable modular robots that successfully extends the operating time of sets of connected modules. The proposed method achieves near-optimal results even when each module only knows the power status of its immediate neighbors (those to which it is directly connected) rather than the power status of every module in the robotic system. The proposed method is validated in physics-based simulation environments and will be implemented on real robotic hardware developed at the Polymorphic Robotics Laboratory at the University of Southern California. It is also compared with current state-of-the-art power sharing mechanisms. Simulated results show that the proposed method allows for longer operation time than with alternative state-of-the-art methods.

Aggregation of self-reconfigurable robotic modules can potentially offer many advantages for robotic locomotion and manipulation. The resulting system could be more reliable and fault-tolerant and provide the necessary flexibility for new tasks and environments. However, self-aggregation of modules is a challenging task, especially when the alignment of the docking parties in a 3D environment involves both position and orientation (6D), since the bases of docking may be non-stationary (e.g., floating in space, underwater, or moving along the ground), and the end-effectors may have accumulated uncertainties due to many dynamically-established connections between modules. This paper presents a new framework for docking in such a context and describes a solution for sensor-guided self-reconfiguration and manipulation with non-fixed bases. The main contributions of the paper include a realistic experiment setting for 6D docking where a modular manipulator is floating or rotating in space with a reaction wheel and searches and docks with a target module using vision. The movement of the docking parties is a combination of floating and manipulation, and the precision of the docking is guided by a sensor located at the tip of the docking interface. The docking itself is planned and executed by a real-time algorithm with a theoretical convergence boundary. This new framework has been tested in a high-fidelity physics-based simulator, as well as by real robotic modules based on SuperBot. Experimental results have shown an average success rate of more than 86.7 percent in a variety of different 6D-docking scenarios.

Operating and maneuvering in difficult terrains has remained a challenging problem in the field of legged robots. One of the major challenges arises from the high dimensionality inherent in planning foot placements coupled with center of mass motion along terrains that are multifaceted and highly diverse. Previous work has resolved these issues to an extent by constraining the center of mass to fixed trajectories or using predetermined foot placements. To deal with these challenges, this paper proposes a new set of strategies: (1) an optimized geometric Hermite curve with minimum curvature and length is used to plan the motion of the center of mass (2) single contact model dynamics for state-space approximations of center of mass behavior are used to resolve feet transitions between steps in planar environments and (3) vertical center of mass phase space trajectories are optimized to produce an overall plan with minimum energy. This framework allows us to synthesize complex maneuvers in rough terrains and to develop optimal contact transition and foot placement plans that consider the robot's configuration and constraints. Experimental results show that for any potential locations of foot contacts, our planner generates smooth and optimal trajectories for center of mass motion as well as a minimum energy plan for transitioning between foot placements.

Three-dimensional, physics-based simulators are important to the field of self-reconfigurable robotics because they allow researchers to approximate the physical interactions and autonomous behaviors of large numbers of modules in a low-cost, safe, and highly-controlled manner. This paper presents a novel, high-performance, general-purpose simulator for autonomous, self-reconfigurable robots called ReMod3D (RM3D) that overcomes the speed and scalability limitations of existing self-reconfigurable simulators while, at the same time, allowing for realistic module structures, complex environments, and high physical simulation fidelity. While most existing self-reconfigurable simulators view modules as actuated physical bodies with programmable controllers, RM3D views them as embodied agents, defined not only by their physical bodies (links, joints, docks, sensors, actuators) but also by their minds (actions, percepts, behaviors, world models) and the noise inherent in the interaction between sensors, actuators, and the environment. RM3D also simulates inter-module dock connection breakage, something novel for self-reconfigurable robot simulators. Additionally, we present experimental evidence showing that this novel architecture makes RM3D well-suited to locomotion, manipulation, reconfiguration, and embodied intelligence research.

A challenging task for a robotic radio network is to establish the connectivity among a set of entities (humans or radio nodes) in an unknown environment with minimum number of robots. The main difficulty is that the locations of the entities and the radio connectivities between the physical locations are not known in advance. We represent the problem by a topological graph of locations with known access links but unknown radio links and develop a novel ANCHOR algorithm for a set of autonomous robots to discover radio links dynamically and self-organize a radio network to connect the given entities with the least number of robots. We show in simulation analysis the algorithm scale near-linearly with maximum number of connected hops away from the terminals. Experiment also shows performance improvement with increasing number of robots.

This paper presents a thorough analysis of the computational complexity of optimal reconfiguration planning problem for chain-type modular robots, i.e. finding the least number of reconfiguration steps to transform from the initial configuration into the goal configuration. It establishes a formal proof that this problem is NP-complete, even if the configurations are acyclic. This result gives a compelling reason that a polynomial algorithm for optimal reconfiguration plan is unlikely to exist. To facilitate future evaluation of reconfiguration algorithms, the paper also provides the lower and the upper bounds for the minimum number of reconfiguration steps for any given reconfiguration problem.

In many robotics applications, knowing the material properties around a robot is often critical for the robot's successful performance. For example, in mobility, knowledge about the ground surface may determine the success of a robot's gait. In manipulation, the physical properties of an object may dictate the results of a grasping strategy. Thus, a reliable surface identification system would be invaluable for these applications. This paper presents an Inertia-Based Surface Identification System (ISIS) based on accelerometer sensor data. Using this system, a robot actively “knocks” on a surface with an accelerometer-equipped device (e.g., hand or leg), collects the accelerometer data in real-time, and then analyzes and extracts three critical physical properties, the hardness, the elasticity, and the stiffness, of the surface. A lookup table and k-nearest neighbors techniques are used to classify the surface material based on a database of previously known materials. This technique is low-cost and efficient in computation. It has been implemented on the modular and self-reconfigurable SuperBot and has achieved high accuracy (95% and 85%) in several identification experiments with real-world material.

A collective of robots can together complete a task that is beyond the capabilities of any of its individual robots. One property of a robotic collective that allows it to complete such a task is the shape of the collective. One method to form that shape is to form it at a size proportional to the number of robots in that collective, i.e. scalably. In our previous work, scalably forming the shape of the collective required that each robot know the total number of robots in the collective. In this work we present a method called S-DASH, which now allows a collective to scalably form a shape without knowing how many robots are in the collective. Furthermore, S-DASH will change the size of the shape to reflect the addition or removal of robots from the collective. This paper also provides demonstrations of S-DASH running on a simulated collective of robots.

Mapping opaque and confined environments such as caves and pipes is a challenging problem for mobile robots because sensor information is severely limited to the immediate proximity of the robot due to the extreme environmental conditions. The robot must also be flexible and agile in unstructured environments while still providing accurate pose estimation. This paper presents a solution to mapping a 2-dimensional tube by using only a snake robot's proprioceptive joint angle sensors. We assume that the tube is sufficiently smooth and that we know the tube width. We propose techniques for (1) pose estimation of a snake robot by using a self-posture motion model, (2) correcting error in pose estimation using only the snake's internal configuration over time, and (3) building environmental features using only self-occupancy and contact detection. Our goal is to use the minimal amount of sensor information possible to build an accurate spatial map of the environment. We have tested the proposed techniques in simulated environments and experimental results show that they are both effective and efficient for mapping tube environments. We plan to extend these techniques to deal with more complex confined environments beyond single-path tubes.

Flexible and reliable connection is critical for self-reconfiguration, self-assembly, or self-healing. However, most existing connection mechanisms suffer from a deficiency that a connection would seize itself if one end malfunctions or is out of service. To mitigate this limitation on self-healing, this paper presents a new SINGO connector that can establish or disengage a connection even if one end of the connection is not operational. We describe the design and the prototype of the connector and demonstrate its performance by both theoretical analysis and physical experimentations.

This paper presents a bio-inspired, distributed control algorithm calledTENTACLESfor a group of radio robots to move, self-configure and maintain communication between some critical entities (such as humans, command centers, or other systems) in an unknown environment. The basic idea is to direct robots' explorative movements to grow ¿tentacles¿ from entities and establish links when tentacles meet. This approach can self-heal failures of robots and improve communication coverage and quality over time. Experiments in simulations and real robots have shown positive results.

A collective of robots can together complete a task that is beyond the capabilities of any of its individual robots. One property of a robotic collective that allows it to complete such a task is the shape of the collective. In this paper, we present a distributed control method, called DASH, to enable a collective of robots to robustly and consistently form and maintain a pre-defined shape. This control method allows the shape that is formed to be at a scale proportional to the number of robots in the collective. If this collective shape is damaged through the un-controlled movement, removal, or addition of some members of the collective, the existing members will recover the desired shape, proportional to the new number of robots in the collective. We also analyze this control method in terms of class of acceptable shapes and discuss the convergence to the desired shape.

This paper presents a dynamic and distributed reconfiguration planning algorithm for chain-type self-reconfigurable robots, by which a robot can autonomously self-reconfigure from one arbitrary acyclic configuration to another in a distributed way. The novel features of this algorithm include: (1) an efficient representation for unlabeled complex configurations; (2) a distributed comparison to detect common/different substructures in two configurations; (3) reconfiguration are limited to those modules that indicate the differences in topology; and (4) reconfiguration actions are performed in parallel and distributed fashion, where every module decides its own actions locally and coordinate asynchronously to rearrange into the goal configuration. The algorithm is applicable to any chain-type self-reconfigurable robots in general.

Carrying heavy payloads is a challenging task for the modular robot, because its composing modules are relatively tiny and less strong compared with conventional robots. To accomplish this task, we attached passive rollers to the modular robot, and designed a wheeled locomotion gait called tricycleBot. The gait is inspired by paddling motion, and is implemented on the modular robot called SuperBot. Features of this gait are systematically studied and verified through extensive experiments. It is shown that tricycleBot can carry payloads at least 530% of its own weight. It can also be steered remotely to move forward/backward, turn left/right. Capability of tricycleBot demonstrates that the versatility of modular robot can be further expanded to solve very specialized and challenging tasks by using heterogeneous devices.

As the ability to produce a large number of small, simple robotic agents improves, it becomes essential to control the behavior of these robots in such a way that the sum of their actions gives rise to the desired overall result. These robots are modeled as homogeneous, distributed robots, with only one simple short range sensor. Our simple robots are tasked to form and hold a desired swarm shape, independent of the total number of agents. If this shape is damaged by the removal of some of the robots, the remaining agents will recover the former shape, but on a smaller scale. These shapes can also have a pattern such as a picture or drawing displayed on them by controlling the individual robots color, symbolically representing the differentiation of agents within the swarm. This pattern will resize to fit the existing swarm. With the ability to synchronize in time, the swarm gains the ability to change the pattern displayed, resulting in a moving image.

Superbot consists of Lego-like but autonomous robotic modules that can reconfigure into different systems for different tasks. Examples of configurable systems include rolling tracks or wheels (for efficient travel), spiders or centipedes (for climbing), snakes (for burrowing in ground), and climbers (for inspection and repair in space). This video shows several configurations and behaviors that are new for modular and reconfigurable robots. Each SuperBot module is a complete robotic system and has a power supply, micro- controllers, sensors, communication, three degrees of freedom, and six connecting faces (front, back, left, right, up and down) to dynamically connect to other modules. This design allows flexible bending, docking, and continuous rotation. A single module can move forward, back, left, right, flip-over, and rotate as a wheel. Modules can communication with each other for totally distributed control and can support arbitrary module reshuffling during their operation. The modules have both internal and external sensors for monitoring self-status and environmental parameters. They can form arbitrary configurations (graphs) and can control these configurations for different functionality such as locomotion, manipulation, and self-repair. This video shows the latest status the SuperBot modules and all these behaviors were made in just one week. The fact that SuperBot can achieve so much in so short a time demonstrates the unique value of modular, multifunctional and self-reconfigurable robots.

In this paper, we present a general mathematical foundation of hormone-inspired control for the self-reconfigurable robotic system. Problem considered here is the lack of a mathematical description to analyze and explain the dynamic behavior of self-reconfigurable robots. In the global level, the idea of virtual disconnection is developed to abstract the low level module control away from the high level synchronization for both cyclic and acyclic robot configuration. In the module layer, the linear space model is developed to describe each module's internal state, input-output hormone transformation, and its action selection. As a combination of hormone and modern control theory, the approach in this paper gives more features, such as predictability and stability analysis etc, to hormone-inspired control, and makes it applicable to self-reconfigurable systems in general. Simulation and experimental results show the capacity of our method

This paper presents a modular and reconfigurable robot for multiple locomotion modes based on reconfigurable modules. Each mode consists of characteristics for the environment type, speed, turning-ability, energy-efficiency, and recover ability from failures. The paper demonstrates this solution by the Superbot robot that combines advantages from MTRAN, CONRO and others. Experimental results, both in real robots and in simulation, have shown the validity of the approach and demonstrated the movements of forward, backward, turn, sidewinder, maneuver, and travel on batteries up to 500 meters on a flat terrain. In physics-based simulation, Superbot can perform as snake, caterpillar, insect, spider, rolling track, H-walker, etc., and move 1.0 meter/second on flat terrain with less than 6 W/module, and climb slopes of no less 40 degrees

Much work on self-reconfigurable robotics has been focused on motion planning and physical reconfiguration of the robot. Using the Superbot self-reconfigurable robot, we focus on the details of realizing locomotion gaits given that a single robot topology can be realized in a large number of different ways. That is, each module in the robot topology has 4 symmetric orientations that are functional and shape equivalent. Once a role is selected for each module, such as through the use of hormone-inspired control, each module's role is supplied with a gait template which then must be transformed to suit the local configurations of each module with respect to the global topology. We provide a theoretical framework for which this can be accomplished

We present a distributed controller for the center of mass of a modular robot. This is useful for locomotion of a modular robot over uneven and unknown terrain. By controlling the center of mass, a robot can prevent itself from falling over. We present a distributed and decentralized algorithm that computes the mass properties of the robot. Additionally, each module also computes the mass properties of the modules that are directly or indirectly connected to each of its connectors. With this information, each module can independently steer the center of mass towards a desired position by adjusting its joint positions. We present simulation results that show the feasibility of the approach

Self-reconfigurable robots are modular robots that can autonomously change their shape and size to meet specific operational demands. Recently, there has been a great interest in using self-reconfigurable robots in applications such as reconnaissance, rescue missions, and space applications. Designing and controlling self-reconfigurable robots is a difficult task. Hence, the research has primarily been focused on developing systems that can function in a controlled environment. This paper presents a novel self-reconfigurable robotic system called SuperBot, which addresses the challenges of building and controlling deployable self-reconfigurable robots. Six prototype modules have been built and preliminary experimental results demonstrate that SuperBot is a flexible and powerful system that can be used in challenging real-world applications

This paper presents the design of an experimental system for assembly applications in space. The prototypical application is the assembly of mechanical trusses. The system used an air-hockey table to simulate a frictionless two-dimensional space. Assembly robots fly on the surface finding, gathering and assembling the relevant parts to perform the construction. The system design involved building the FIMER Robots, the test bed, the sensing system for position and velocity feedback and the control scheme. This paper describes the hardware and software used in the various sub-systems and includes calibrations and measurements and the results of experiments

Docking between independent groups of self-reconfigurable robotic modules enables the merger of two or more independent self-reconfigurable robots. This ability allows independent reconfigurable robots in the same environment to join together to complete a task that would otherwise not be possible with the individual robots prior to merging. The challenges for this task include: (1) coordinate and align two independent self-reconfigurable robots using the docking guidance system available only at the connectors of the docking modules; (2) overcome the inevitable errors in the alignment by a novel and coordinated movements from both docking ends; (3) ensure the secure connection at the end of docking; (4) switch configuration and let modules to discover the changes and new connections so that the two docked robots will move as a single coherent robot. We have developed methods for overcome these challenging problems and accomplished for the first time an actual docking between two independent CONRO robots each with multiple modules.

This paper describes a distributed and decentralized approach for modules in a self-reconfigurable robot to select appropriate behaviors based on four factors: the current global task, the local topological location in the current configuration, the local state/sensor information, and the received messages from their neighbors. This approach does not assume any unique global identifiers for the modules, and is robust for reconfigurations of modules. The approach is enabled by the extended neighbor topology built upon a previous local topology representation and a hormone-inspired communication and control protocols. Experimental results on the CONRO robot have shown some unique features of this approach for the control of self-reconfigurable robots in general.

This paper presents an experimental system for assembly in space. A weightless and frictionless environment is approximated using an air-hockey table where robots and structural components can float on the surface. The robots use fan propulsion to dock with components and assemble them together to make 2D structures. This system is designed to implement three key technologies for space self-assembly: 1) intelligent components with universal connectors, 2) a set of self-reconfigurable robots that fetch and assemble components, and 3) a distributed method for controlling the robotic-assembly process. An overview of the system's design and experimental results is presented.

This paper describes two contributions for chain typed self-reconfigurable robots: a very illustrative self-reconfiguration task changing from "I" shape to "T" shape, and a sensor-based distributed control method for automatic planning and execution of self-reconfiguration. In the "I-to-T" task, a snake robot is to reconfigure itself into a tripod by docking the tail to a target module in the body, releasing a portion of the connected mass as a new leg, and switching to a new gait automatically. We first accomplished this task using predetermined instructions for individual modules without considering sensor inputs. We then developed a sensor-based approach using our hormone-inspired distributed control to allow the robot to dynamically accept the point of connection at run-time, align the tail and the target using sensors, and select appropriate actions based on modules' location in the configuration. Compared to the standard inverse kinematics, this new control approach is sensor-based and can endure the limited computational resources and uncertainties in the connections. It can be applied to self-reconfigurations that are not designed by the programmers but triggered by the environment.

In this paper, we introduce and describe the notion of a robotic enzyme, and how it can use properties that are similar to biological enzymes to autonomously self-replicate. We test the idea of robotic enzymes using a virtual environment that simulates the currently existing modular robots in a physically accurate way. We describe the self-replicating features of robotic enzymes, and how they could be used to autonomously self-replicate for multiple generations, limited only by the amount of modules in the environment.

The topology of a self-reconfigurable robot can change at anytime. This can be as a result of the failure of some modules of the robot, joining new modules to the robot, displacement of some modules from one location to another caused by the self-reconfiguration task or any combination of these cases. Considering that the process of selecting relevant behaviors to accomplish a given task is based on the current topology of the self-reconfigurable robot, modules must be able to detect and respond to any changes to the robot topology. When changes to the topology of the robot are detected, modules can investigate new ways of accomplishing the given task. This paper presents a distributed solution, FEATURE algorithm, to the problem of autonomous discovery and functional response to topology change. The result is experimentally verified and demonstrated on the CONRO self-reconfigurable robots.

This paper describes a new docking system, called Compliant-And-Self-Tightening (CAST), developed as an effective and efficient connector for joining and releasing modules of self-reconfigurable or metamorphic robotic systems. CAST has been successfully implemented in CONRO where its highly compliant and passive features have allowed a considerable ease of execution of a variety of docking algorithms, while using no additional energy for docking and negligible amount of energy for undocking. Development of CAST was motivated by observing the difficulty of implementation of an earlier less compliant docking system designed by the authors for CONRO.

Self-assembly systems in space are arguably within the reach of today's technology based on the research and development of self-reconfigurable robots on earth. This paper presents an approach to self-assembly in space by developing: (1) a novel design for intelligent and reconfigurable components; (2) the free-flying "intelligent fiber/rope" "match-maker" robots with self-reconfigurable and self-adjustable tethering for autonomous docking; and (3) a totally distributed control method for planning, executing, and monitoring the assembly process. These approaches are partially evaluated by a set of experimental and simulation results to simulate the dynamics and control of free-flying objects in zero-gravity environment.

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 when the robot is manually reconfigured from a chain to a quadruped configuration the robot changes gait from a sidewinder snake gait to a quadruped walking gait. We conclude that role based control is a promising central method for controlling locomotion of self-reconfigurable robots.

A self-reconfigurable robot can be viewed as a network of many autonomous modules. Driven by their local information, the modules can initiate tasks that may conflict with each other at the global level. How the modules negotiate and select a coherent task among many competing tasks is thus a critical problem for the control of self-reconfigurable robots. This paper presents a distributed algorithm called DISTINCT to solve this challenging problem and show that it can be successfully applied to the CONRO self-reconfigurable robots. A discussion how to apply DISTINCT to other types of distributed systems such as sensor network, swarm robots, or multi-agent systems is also given.

Task reallocation in a multi-robot organization is a process that distributes a decomposed global task to individual robots. This process must be distributed and dynamic because it relies on critical information that can only be obtained during mission execution. The paper presents a representation for this challenging problem and proposes an algorithm that allows member robots to trade tasks and responsibilities autonomously. Preliminary results show that such an algorithm can indeed improve the efficiency of organizational performance and construct a locally optimal (hill climbing) task allocation during mission execution.

How do multiple robots self-organize into global patterns based on local communications and interactions? This paper describes a theoretical and simulation model called "Digital Hormone Model" (DHM) for such a self-organization task. The model is inspired by two facts: complex biological patterns are results of self-organization of homogenous cells regulated by hormone-like chemical signals, and distributed controls can enable self-reconfigurable robots to performance locomotion and reconfiguration. The DHM is an integration and generalization of reaction-diffusion model and stochastic cellular automata. The movements of robots (or cells) in DHM are computed not by the Turing's differential equations, nor the Metropolis rule, but by stochastic rules that are based on the concentration of hormones in the neighboring space. Experimental results have shown that this model can produce results that match and predict the actual findings in the biological experiments of feather bud formation among uniform skin cells. Furthermore, an extension of this model may be directly applicable to self-organization in multirobot systems using simulated hormone-like signals.

Presents a biologically inspired approach to two basic problems in modular self-reconfigurable robots: adaptive communication in self-reconfigurable and dynamic networks, and distributed collaboration between the physically coupled modules to accomplish global effects such as locomotion and reconfiguration. Inspired by the biological concept of hormone, the paper develops the adaptive communication (AC) protocol that enables modules continuously to discover changes in their local topology, and the adaptive distributed control (ADC) protocol that allows modules to use hormone-like messages in collaborating their actions to accomplish locomotion and self-reconfiguration. These protocols are implemented and evaluated, and experiments in the CONRO self-reconfigurable robot and in a Newtonian simulation environment have shown that the protocols are robust and scaleable when configurations change dynamically and unexpectedly, and they can support online reconfiguration, module-level behavior shifting, and locomotion. The paper also discusses the implication of the hormone-inspired approach for distributed multiple robots and self-reconfigurable systems in general.

Metamorphic robots with shape-changing capabilities provide a powerful and flexible approach to complex tasks in unstructured environments. However, due to their dynamic topology and decentralized configuration, metamorphic robots demand control mechanisms that go beyond those used by conventional robots. This paper builds on our previous results of hormone-based control, and develops a novel distributed control algorithm called CELL that can select, synchronize, and execute gaits and other reconfiguration actions without assuming any global configuration knowledge. This algorithm is flexible enough to deal with changes of configuration, and can resolve conflicts between locally selected actions and manage multiple active hormones for producing coherent global effects.

Self-reconfigurable robots are modular robots that can dynamically and intelligently reconfigure their shape and size to accomplish difficult missions. To build such robots, however, a number of technical challenges must be overcome. One critical problem is the design and implementation of the reconnectable joints (also called connectors), which allows modules to autonomously connect and disconnect from one another. Such a mechanism must be power efficient, reliable, and compact (the mechanism must fit into a tight space). This paper gives an overview of the CONRO self-reconfigurable robots, and focuses on the reconnectable joints of the CONRO modules. The paper identifies a set of desired features and operation constraints for the joints, and describes our current design for the connectors.

Docking is a crucial action for self-reconfigurable robots because it supports almost all practical advantages of such robots. In addition to the classic docking challenges found in other applications, such as reliable dock/latch mechanics, effective guiding systems, and intelligent control protocols, docking in self-reconfigurable robots is also subject to some unique constraints. These constraints include the kinematics constraints imposed on the docking modules by other modules in the configuration, communication limitations between the docking and relevant modules, and the demand for distributed control software because of the dynamics of configuration. To solve these challenging problems, this paper reports a set of solutions developed in the CONRO reconfigurable robot project. The paper presents a three-stage docking process, six different alignment protocols, distributed inverse kinematics, and other techniques such as dynamic lubrication that are essential for successful docking in CONRO-like robots. These solutions enable CONRO robots to perform autonomous and distributed reconfigurations in a laboratory environment, and they also suggest important considerations for docking in self-reconfiguration in general.

Robot soccer competition provides an excellent opportunity for robotics research. In particular, robot players in a soccer game must perform real-time visual recognition, navigate in a dynamic field, track moving objects, collaborate with teammates, and strike the ball in the correct direction. All these tasks demand robots that are autonomous (sensing, thinking, and acting as independent creatures), efficient (functioning under time and resource constraints), cooperative (collaborating with each other to accomplish tasks that are beyond individual's capabilities), and intelligent (reasoning and planing actions and perhaps learning from experience). Furthermore, all these capabilities must be integrated into a single and complete system. To build such integrated robots, we should use different approaches from those employed in separate research disciplines. This paper describes our experience (problems and solutions) in this aspect for building soccer robots. Our robots share the same general architecture and basic hardware, but they have integrated abilities to play different roles and utilize different strategies in their behavior. Our philosophy in building these robots is to use the least possible sophistication to make them as robust as possible. In RoboCup97, our Dreamteam robots performed well (scored 8 of 9 goals of all teams in the league) and won the world championship in the middle-sized robot league.

This paper first provides an overview of data preprocessing, focusing on problems of real world data. These are primarily problems that have to be carefully understood and solved before any data analysis process can start. The paper discusses in detail two main reasons for performing data preprocessing: (i) problems with the data and (ii) preparation for data analysis. The paper continues with details of data preprocessing techniques achieving each of the above mentioned objectives. A total of 14 techniques are discussed. Two examples of data preprocessing applications from two of the most data rich domains are given at the end. The applications are related to semiconductor manufacturing and aerospace domains where large amounts of data are available, and they are fairly reliable. Future directions and some challenges are discussed at the end.

A metapattern (also known as a metaquery) is a new approach for integrated data mining systems. As opposed to a typical "toolbox"-like integration, where components must be picked and chosen by users without much help, metapatterns provide a common representation for inter-component communication as well as a human interface for hypothesis development and search control. One weakness of this approach, however, is that the task of generating fruitful metapatterns is still a heavy burden for human users. In this paper, we describe a metapattern generator and an integrated discovery loop that can automatically generate metapatterns. Experiments in both artificial and real-world databases have shown that this new system goes beyond the existing machine learning technologies, and can discover relational patterns without requiring humans to pre-label the data as positive or negative examples for some given target concepts. With this technology, future data mining systems could discover high-quality, human-comprehensible knowledge in a much more efficient and focused manner, and data mining could be managed easily by both expert and less-expert users.

Knowledge bases open new horizons for machine learning research. One challenge is to design learning programs to expand the knowledge base using the knowledge that is currently available. This article addresses the problem of discovering regularities in large knowledge bases that contain many assertions in different domains. the article begins with a definition of regularities and gives the motivation for such a definition. It then outlines a framework that attempts to integrate induction with knowledge. Although the implementation of the framework currently uses only a statistical method for confirming hypotheses, its application to a real knowledge base has shown some encouraging and interesting results. © 1992 John Wiley & Sons, Inc.