AUTOMATED SYNTHESIS AND OPTIMIZATION OF ROBOT 
		CONFIGURATIONS: AN EVOLUTIONARY APPROACH

				  by

				Chris Leger

                                 Abstract

     Robot configuration design is hampered by the lack of established,
well-known design rules, and designers cannot easily grasp the space of
possible designs and the impact of all design variables on a robot's 
performance. Realistically, a human can only design and evaluate several
candidate configurations, though there may be thousands of competitive
designs that should be investigated. In contrast, an automated approach to
configuration synthesis can create tens of thousands of designs and measure
the performance of each one without relying on previous experience or design
rules. 
     This thesis creates Darwin2K, an extensible, automated system for robot
configuration synthesis. This research focuses on the development of
synthesis capabilities required for many robot design problems: a flexible and
effective synthesis algorithm, useful simulation capabilities, appropriate
representation of robots and their properties, and the ability to accomodate
application-specific synthesis needs. Darwin2K can synthesize and optimize
kinematics, dynamics, structural geometry, actuator selection, and task and
control parameters for a wide range of robots. 
     Darwin2K uses an evolutionary algorithm to synthesize robots, and
utilizes two new multi-objective selection procedures that are applicable to
other evolutionary design domains. The evolutionary algorithm can
effectively optimize multiple performance objectives while satisfying multiple
performance constraints, and can generate a range of solutions 
representing different trade-offs between objectives. Darwin2K uses a novel 
representation for robot configurations called the parameterized module 
configuration graph, enabling efficient and extensible synthesis of mobile 
robots, of single, multiple and bifurcating manipulators, and of robots with 
either modular or monolithic construction. 
     Task-specific simulation is used to provide the synthesis algorithm
with performance measurements for each robot. Darwin2K can automatically 
derive dynamic equations for each robot it simulates, enabling dynamic 
simulation to be used during synthesis for the first time. Darwin2K also 
includes a variety of simulation components, including Jacobian and PID 
controllers, algorithms for estimating link deflection and for detecting 
collisions; modules for robot links, joints (including actuator models), 
tools, and bases (fixed and mobile); and metrics such as task coverage, 
task completion time, end effector error, actuator saturation, and link 
deflection. A significant component of the system is its extensible 
object-oriented software architecture, which allows new simulation 
capabilities and robot modules to be added without impacting the synthesis 
algorithm.  The architecture also encourages re-use of existing toolkit 
components, allowing task-specific simulators to be quickly constructed.  
     Darwin2K's synthesis algorithm, simulation capabilities, and extensible
architecture combine to allow synthesis of robots for a wide range of tasks.
Results are presented for nearly 150 synthesis experiments for six different
applications, including synthesis of a free-flying 22-DOF robot with multiple
manipulators and a walking machine for zero-gravity truss walking. The
synthesis system and results represent a significant advance in the
state-of-the-art in automated synthesis for robotics. 

Thesis Committee:  John Bares, CMU
                   Manuela Veloso, CMU
                   Pradeep Khosla, CMU
                   Chris Paredis, CMU
                   Robert Ambrose, NASA JSC