ABSTRACT Title of Thesis: DESIGN, ANALYSIS, AND FABRICATION OF A SNAKE-INSPIRED ROBOT WITH A RECTILINEAR GAIT Degree Candidate: Brent William Spranklin Degree and Year: Master of Science, 2006 Thesis Directed By: Associate Professor Satyandra K. Gupta Department of Mechanical Engineering Snake-inspired robots display promise in areas such as search, rescue and reconnaissance due to their ability to locomote through tight spaces. However, several specific issues regarding the design and analysis must be addressed in order to better design them. This thesis develops kinematic and dynamic models for a class of snake-inspired gait known as a rectilinear gait, where mechanism topology changes over the course of the gait. A model using an Eulerian framework and Coulomb friction yields torque expressions for the joints of the robot. B-spline curves are then used to generate a parametric optimization formulation for joint trajectory generation. Exact gradient computation of the torque functions is presented. A parametric model is used to describe the performance effects of changing system parameters such as mass, length, and motor speed. Finally, a snake-inspired robot is designed and fabricated in order to demonstrate both the vertical rectilinear gait and a modular, molded design aimed at reducing the cost of fabrication. DESIGN, ANALYSIS, AND FABRICATION OF A SNAKE-INSPIRED ROBOT WITH A RECTILINEAR GAIT By Brent William Spranklin Thesis submitted to the Faculty of the Graduate School of the University of Maryland, College Park in partial fulfillment of the requirements for the degree of Master of Science 2006 Advisory Committee: Associate Professor Satyandra K. Gupta, Chair/Advisor Associate Professor Hugh A. Bruck Dr. Greg Schultz ? Copyright by Brent William Spranklin 2006 ii Acknowledgments First, I would like to thank my advisor, Dr. S.K. Gupta, for his continued guidance and support during both my undergraduate and graduate education. He taught me a lot, and was always there to motivate me, and for that I will always be grateful. I would also like to thank Dr. Bruck for his assistance and guidance throughout my education, and Dr. Schultz for taking the time to serve on my committee. I would like to thank all of my lab-mates and people who collaborated on this project. I had a terrific time collaborating with Lawrence ?J.R.? Gyger and James Hopkins on this work, and would like to wish them luck as they complete their academic careers. I would also like to thank my undergraduate assistants Navid Charooseh, Chris Jinks, and Ben Bernstein for the many hours they contributed. In addition, I would like to thank the rest of the people I had the pleasure to work with; especially those who helped me proofread this thesis. Finally, I would like to thank my family and friends. I would like to thank my parents for instilling the value of education in me, and my brothers for always being there for me. I would also like to thank Lauren for always sticking by me, and sometimes accompanying me on those late evenings and weekends in the lab. iii Table of Contents Acknowledgments......................................................................................................... ii Table of Contents.........................................................................................................iii Table of Figures ............................................................................................................ v Chapter 1 - Introduction................................................................................................ 1 1.1 Background......................................................................................................... 1 1.1.1 Snakes .......................................................................................................... 1 1.1.2 Advantages and Disadvantages of Snake-Inspired Locomotion ................. 2 1.1.3 What Can Snakes Offer to Engineers?......................................................... 5 1.1.4 Possible Applications of Snake-Inspired Robots......................................... 6 1.2 Motivation......................................................................................................... 10 1.2.1 Kinematic and Dynamic Model................................................................. 10 1.2.2 Gait Design ................................................................................................ 12 1.2.3 Improved Mechanical Design.................................................................... 12 1.3 Thesis Goal and Scope...................................................................................... 14 1.4 Organization...................................................................................................... 15 Chapter 2 - Related Work ........................................................................................... 17 2.1 Overview........................................................................................................... 17 2.2 Snake Locomotion ............................................................................................ 17 2.3 Snake-Inspired Robot Designs for Search and Rescue..................................... 25 2.4 Snake-Inspired Robot Mechanics: Kinematics and Dynamics......................... 44 2.5 Rectilinear Gait Generation .............................................................................. 52 2.6 Robot Trajectory Optimization......................................................................... 54 2.7 Summary........................................................................................................... 57 Chapter 3 - Gait Development and Analysis .............................................................. 59 3.1 Introduction....................................................................................................... 59 3.2 Background....................................................................................................... 60 3.2.1 Basic Robotics ........................................................................................... 60 3.2.2 Joint Trajectories........................................................................................ 63 3.2.3 Exact vs. Redundant Actuation.................................................................. 64 3.2.4 B-Spline Functions..................................................................................... 65 3.3 Gait Overview and Rationale............................................................................ 67 3.3.1 Drawbacks of a Serpentine Gait ................................................................ 68 3.3.2 Advantages of a Rectilinear Gait ............................................................... 70 3.3.3 Gait Sequence ............................................................................................ 71 3.4 Kinematics and Dynamics Model..................................................................... 74 3.4.1 Gait Kinematics ......................................................................................... 75 3.4.2 Dynamics ................................................................................................... 83 3.4.3 Mechanism 2 (M2) ..................................................................................... 89 3.4.4 Mechanism 3 (M3) ..................................................................................... 92 3.4.5 Steps 4 and 5 .............................................................................................. 93 3.4.6 Mapping Solutions..................................................................................... 94 3.5 Trajectory Generation ....................................................................................... 96 3.5.1 B-Spline Trajectory Formulation............................................................... 97 iv 3.5.2 Trajectory Optimization............................................................................. 97 3.5.3. A Heuristic-Based Trajectory Generation Approach.............................. 105 3.6 Results............................................................................................................. 111 3.7 Validation........................................................................................................ 123 3.8 Summary......................................................................................................... 125 Chapter 4 - Parametric Study.................................................................................... 127 4.1. Introduction.................................................................................................... 127 4.2. Mission Requirements ................................................................................... 127 4.3. Discussion of Varied Parameters ................................................................... 129 4.4 Discussion of Results...................................................................................... 132 4.5 Summary......................................................................................................... 143 Chapter 5 - Snake-Inspired Robot Realization ......................................................... 145 5.1 Introduction..................................................................................................... 145 5.2 Design Goals and Objectives.......................................................................... 145 5.3 Structural Design ............................................................................................ 148 5.3.1 Molded Structure ..................................................................................... 149 5.3.2 Multi-Material Molding........................................................................... 151 5.4 Component Selection...................................................................................... 157 5.4.1 Actuators.................................................................................................. 157 5.4.2 Power ....................................................................................................... 159 5.4.3 Control System......................................................................................... 162 5.5 Overall Module Mechanical Design and Manufacturing................................ 167 5.6 Locomotion Results ........................................................................................ 177 5.7 Next Generation Snake: Embedded Components........................................... 179 5.8 Summary......................................................................................................... 183 Chapter 6 - Conclusions............................................................................................ 184 6.1 Contributions................................................................................................... 184 6.2 Anticipated Benefits........................................................................................ 185 6.3 Future Work.................................................................................................... 186 6.3.1 Model Improvement and Validation........................................................ 186 6.3.2 Improved Prototype Design ..................................................................... 187 6.3.3. Generation of Optimal Gaits................................................................... 189 Appendix A: Equations............................................................................................. 190 Appendix B. Design Information.............................................................................. 197 References................................................................................................................. 203 v Table of Figures Figure 1.1 Python regius, a common snake. ................................................................. 2 Figure 1.2. Rescuers search for survivors at a disaster scene [1]. ................................ 7 Figure 1.3. Example of an industrial pipe structure [2]. ............................................... 9 Figure 1.4. Chart of a possible overall system model................................................. 11 Figure 2.1. Serpentine Locomotion [9]....................................................................... 19 Figure 2.2. Snake exhibiting serpentine locomotion through a series of vertical pegs. The snake alters its curve proportionally to peg spacing [3]. ............................. 19 Figure 2.3. Steps 1-7 show the progression of snake as it exhibits concertina locomotion. Portions colored black are stationary while portions colored white are sliding [3]. ..................................................................................................... 20 Figure 2.4. Sidewinding Locomotion. The shaded portions are at rest with respect to the ground [3] ..................................................................................................... 21 Figure 2.5. Points on the ventral surface of the snake are used to demonstrate rectilinear motion. Heavier points denote static contact while the lighter points denote sliding contact [4].................................................................................... 23 Figure 2.6. Rectilinear Motion. In step one, region A is at maximum contraction, region B is contracting, region C is at maximum elongation, and region D is elongating. The progression of the wave is seen through the motion steps of the gait [4]................................................................................................................. 24 Figure 2.7. Active Cord Mechanism by Hirose [9]. ................................................... 27 Figure 2.8. ACM traveling through a track using sensors [9]. ................................... 29 Figure 2.9. Hirose's ACM-R3 [10]. ............................................................................ 30 Figure 2.10. One link of Dowlings snake-inspired robot [13].................................... 33 Figure 2.11. Dowlings snake-inspired robot [13]. ...................................................... 34 Figure 2.12. Actuated universal joint design by Wolf et al [18]................................. 36 Figure 2.13. Gavin Miller's S5 snake-inspired robot [19]. ......................................... 37 Figure 2.14. Omnitread robot climbing up a step [21]. .............................................. 41 Figure 2.15. Nomenclature for Hirose?s equations [9]. .............................................. 46 Figure 2.16. Model of muscle structure in snake joint [9].......................................... 47 Figure 2.17. Parameters in Chirikjian and Burdick?s approach [24]. ......................... 49 Figure 2.18. Burdick and Ostrowski model [25]. ....................................................... 50 Figure 2.19. Merino and Tosunglu's Gait [34]............................................................ 53 Figure 2.20. Initial path, 2-link manipulator [37] ....................................................... 56 Figure 2.21. Optimal solution, 2-link manipulator (working against gravity) [37].... 56 Figure 3.1. Representation of gait analysis and development procedure. .................. 60 Figure 3.2. .Basic robot link representation................................................................ 61 Figure 3.3. Closed-loop (left) and open-loop (right) configurations of a snake-inspired robot. ................................................................................................................... 62 Figure 3.4. Gait presented by Merino and Tosunoglu [34]......................................... 72 Figure 3.5. Modified traveling wave gait, steps and mechanisms are identified........ 74 Figure 3.6. The first gait step...................................................................................... 76 Figure 3.7. Representation of the first mechanism as a open-loop, planar, kinematic chain.................................................................................................................... 77 vi Figure 3.8. Representation of the first mechanism as a closed-loop, planar, kinematic chain.................................................................................................................... 79 Figure 3.9. Free body diagrams for the links in M1.................................................... 87 Figure 3.10. Gait step 2, which is modeled with mechanism 2 (M2).......................... 90 Figure 3.11. Model of M2. .......................................................................................... 91 Figure 3.12. Gait step 3, which can be modeled with mechanism 3 (M3).................. 93 Figure 3.13. Architecture of fitness evaluation function ? COMPUTE_DYN(C). .. 109 Figure 3.14. Organization of search algorithm. ........................................................ 110 Figure 3.15. Effort vs. iterations for step 1 search.................................................... 112 Figure 3.16. Resultant trajectory function for joint 1. .............................................. 114 Figure 3.17. Resultant trajectory function for joint 2. .............................................. 114 Figure 3.18. Snapshots of gait step 1, shown at 0.1s intervals. ................................ 115 Figure 3.19. Torque versus time for joint 1. ............................................................. 116 Figure 3.20. Torque vs. time for step 2..................................................................... 117 Figure 3.21. Effort vs. iterations for step 2............................................................... 118 Figure 3.22. Resultant trajectory for joint 1.............................................................. 119 Figure 3.23. Resultant trajectory for joint 2.............................................................. 119 Figure 3.24. Resultant trajectory for joint 3.............................................................. 120 Figure 3.25. Snapshots of gait step 2, shown at 0.1s intervals. ................................ 121 Figure 3.26. Torque vs. time for joint 1.................................................................... 122 Figure 3.27. Torque vs. time for joint 2.................................................................... 122 Figure 3.28. Torque vs. time for joint 3.................................................................... 123 Figure 3.29. Snapshots of gait.................................................................................. 125 Figure 4.1. Mapping between design parameters and performance. ........................ 129 Figure 4.2. Varied parameters. The gait angles occur at the transition points, or ?steps.?.............................................................................................................. 132 Figure 4.3. Trajectories generated for step 2 at different step times......................... 134 Figure 4.4. Torque 2 would be greater than Torque 1. ............................................. 134 Figure 4.5. Sample two-link manipulator [44].......................................................... 136 Figure 4.6. Effort versus step time. Feasible design space for sample exercise shown. ........................................................................................................................... 138 Figure 4.7. Effort versus velocity, changing step times. Feasible design space for sample exercise shown...................................................................................... 138 Figure 4.8. Gait angle versus effort, gait step time = 1s. .......................................... 139 Figure 4.9. Effort versus velocity, achieved by changing the gait angle. Gait step time is 1s. .................................................................................................................. 140 Figure 4.10. Effort vs. angle when gait step time is 0.1s.......................................... 140 Figure 4.11. Effort vs. velocity (achieved by changing gait angle) when gait step time is 0.1s. ............................................................................................................... 141 Figure 4.12. Effort versus length. ............................................................................. 142 Figure 4.13. Effort versus velocity, varying length. ................................................. 142 Figure 4.14. Effort versus mass. ............................................................................... 143 Figure 5.1. Example of a fully-modular snake-inspired robot.................................. 147 Figure 5.2. Overmolding [52]. .................................................................................. 152 Figure 5.3. Multi-Shot molding [52]......................................................................... 153 Figure 5.4. Multi-material molded gimbal mechanism [51]..................................... 155 vii Figure 5.5. Original rotor assembly [51]. ................................................................. 155 Figure 5.6. Redesigned rotor structure: Only 8 parts [51]. ....................................... 156 Figure 5.7. Servomotor. ............................................................................................ 158 Figure 5.8. Battery technology trends (adopted from [54])...................................... 160 Figure 5.9. Lithium polymer battery......................................................................... 161 Figure 5.10. Modular circuit architecture. ................................................................ 165 Figure 5.11. Circuit layout. Components IC1 and IC2 are the voltage regulator and the PIC, respectively. C1, C2, and C3 are .1, .33, and .1 ?F capacitors, respectively. ...................................................................................................... 166 Figure 5.12. Circuit board layout, key components are labeled. .............................. 167 Figure 5.13. Completed design module. ................................................................... 169 Figure 5.14. Side views of modules.......................................................................... 170 Figure 5.15. Stage 1 of molding for part 1................................................................ 172 Figure 5.16. Stage 1 molding part 2.......................................................................... 173 Figure 5.17. Stage 2 molding.................................................................................... 174 Figure 5.18. Second Stage exploded view................................................................ 174 Figure 5.19. Robot module. ...................................................................................... 175 Figure 5.20. Fully assembled modular snake-inspired robot.................................... 176 Figure 5.21. End module........................................................................................... 177 Figure 5.22. Snapshots of locomotion. ..................................................................... 179 Figure 5.23. Solid Model of embedded module. ...................................................... 182 Figure 5.24. Embedded module................................................................................ 182 Figure 5.25. A pager motor that has been partially embedded in polyurethane. ...... 182 1 Chapter 1 - Introduction 1.1 Background 1.1.1 Snakes Snakes are diverse creatures that occupy a wide range of habitats. They also have a wide range of locomotive capabilities, ranging from crawling and burrowing to climbing and even swimming. While snakes all have a similar structure, they do exist in a variety of sizes and aspect ratios. For example, snakes such as the Boidae family (Boas and Pythons) tend to have thicker, heavier bodies (Figure 1.1), while snakes in families such as the Leptotyphlopidea family (Thread snakes and Worm snakes) tend to have thinner body types. Snakes also range in length from more than 20 feet for reticulated pythons and anacondas, to substantially less than 1 foot long for many of the smaller varieties. The design of a snake is a simple structure that is repeated many times. Snakes bodies are elongated forms that consist of a long backbone made of many vertebrae. In fact, there are only three different kinds of bones in the entire snake skeleton: the skull, the vertebrae, and the ribs. Snake backbones consist of 100-400 vertebrae, and the design of each vertebra allows small motions in both the lateral and vertical directions. They do not allow any twisting, however, and thus act as compliant universal joints. Each vertebra itself only allows a very small amount of angular motion, but the motions of many vertebrae allow snakes to drastically curve their bodies. Each vertebra allows rotation of 10-20 degrees in the horizontal plane, and between 2-3 degrees in the vertical plane. 2 While some of the subtleties and details of snake locomotion are not fully understood, the basic forms of forward locomotion can be grouped into several different classes of gaits. The gait that a particular snake may use depends on the type of snake, the terrain that it is traveling over, and the speed at which the snake desires to travel. While a gait known as the serpentine gait is most commonly thought of as snake locomotion, this thesis focuses on rectilinear snake locomotion because of the potential benefits of rectilinear locomotion that are discussed in Section 3.3. Figure 1.1 Python regius, a common snake. 1.1.2 Advantages and Disadvantages of Snake-Inspired Locomotion Snake locomotion provides several advantages over traditional forms of locomotion in both animals and machines. Due to their elongated form and lack of legs, snakes have compact cross-sections and thus can move through very thin holes and gaps. Likewise, snake-inspired devices have much thinner cross sections than other robots with equivalent sizes and capabilities. In addition to the thinner cross section, snakes 3 also have the ability to climb up and over obstacles that are much taller than their body height. This is done by lifting the front half of their long bodies. Similarly, a snake-inspired robot can lift its body up and over obstacles much larger than most legged or wheeled devices. These properties are very desirable when moving through complex and cluttered environments. Aditionally, snakes are also stable. Because their bodies are constantly in contact with the ground at many different points, it is difficult to knock them over, especially since they have a low center of mass and do not lift their bodies off the ground much during locomotion. Snakes have redundant designs that rely on the same kind of joint (and structure) that is repeated many times. This means that if one joint fails, the snake can continue to locomote. The simplicity of the design also means that the snake does not have any fragile appendages that can easily break. The form of locomotion that snakes use also relies on a large amount of contact between the ground and the posterior. This large surface area gives the snake good traction characteristics in variable environments. Whereas one wheel or leg in a traditional kind of robot may slip, the large contact surface of a snake-inspired robot would make this occurrence less likely. Snakes are very versatile and can act as both locomotors and manipulators, as they can use their bodies to wrap around objects to grasp them. This can be seen in the climbing action across tree branches, or when a constrictor is clenching its prey. Since one structure can do both things, the need for different mechanisms to achieve different tasks is eliminated. 4 Finally, despite frictional opposition to their locomotion, snakes actually have been shown to consume a comparable amount of energy to other biological forms with similar sizes, weights, and speeds. This can be explained by the fact that snakes do not perform a lot of lifting of their body in their motion, and they also do not consume a lot of energy by moving different appendages like legged animals (this is elaborated on in Chapter 2). With all of these advantages, why are snakes unique in their form of locomotion among animals? Why do the majority of different animals use different forms of locomotion, and why are all mobile robots not based on snakes? The answer is that there are also many disadvantages to snake locomotion as well. A major disadvantage to snake locomotion is that it is often slower than other forms of locomotion. The fastest snake has a maximum forward speed of 3 m/s (Black Mamba) and many snakes travel much slower. Other wheeled devices and organisms with legs that are similar-sized have the ability to travel much faster. For example, the Prairie Racerunner, a species of lizard, has been clocked at speeds up to 8 m/s. Another deficiency of snake structure and snake locomotion of interest to the robot designer is that a snake does have many convenient locations to carry a payload like many other wheeled and legged locomotion platforms. Mobile robots often carry a suite of sensors and actuators, as well as power components. Typically, for a wheeled or legged robot the majority of the body provides a place to carry payload, and the legs or wheels require a comparatively small amount of the volume. With 5 snake-like robots, however, the entire form is used in the locomotion process, and thus must conform to the shape of the snake. A final notable drawback of snake locomotion is related to control of the many degrees of freedom. As was previously mentioned, natural snakes can contain as many as 400 vertebrae, each of these constituting two degrees-of-freedom. Many robotic implementations of snake locomotion have had as many as 20 actuated joints. The control (as well as engineering analysis) of a system such as this is not trivial. Current control architectures have difficulty dealing with systems with many degrees- of-freedom. 1.1.3 What Can Snakes Offer to Engineers? Snake-like robots can offer engineers a novel means of locomotion and a versatile platform design for unmanned robotic systems. The functional requirements for a snake are similar to the functional requirements of many tasks that we wish to achieve with robotics. Snakes must be able to move in environments with many obstacles and be able to place their bodies into tight spaces. Some snakes also must be able to burrow, climb, and even swim. Similarly, unmanned robots must be able to travel in both tight and cluttered environments where humans cannot go for reasons of either safety or size. Users also often want unmanned robots that are stealthy, for example in the case of espionage and reconnaissance. Finally, robots need to be robust enough to complete their task. 6 1.1.4 Possible Applications of Snake-Inspired Robots Urban Search and Rescue (USAR) With the world?s population increasing, and more people living in urban environments, both man-made and natural catastrophes are becoming more and more common. This has been illustrated in recent events such as the terrorist attacks on the World Trade Center in 2001, and hurricane Katrina in the United States. Other examples of catastrophes would be the tsunami in southeast Asia that killed almost 200,000 people in December of 2004, and the 2005 earthquake in the Kashmir region of Pakistan. During disasters in urban areas, it is common for buildings to collapse and for debris to be present, complicating the search and rescue process. Such environments make survivors difficult to find amongst the debris, because they may be buried. Additionally, debris and partially-collapsed buildings can also make the search environment dangerous for both human rescuers and even trained dogs because of the potential for collapse. Even more dangerous would be the case where toxic chemicals or radiation are present in the cleanup site, which could be the result of an event such as a terrorist attack. In an event where lives are at risk, time is always critical. Rescue workers need up-to-the-minute information about the hazards they face and where the survivors may lie. Other critical information includes the structural integrity of the disaster area, what hazardous materials are present, and the presence of fires or flammable gasses in the rubble. 7 Yim et al. [1] outline a typical search and rescue operation. A typical search and rescue team consists of approximately 10 people. The team consists of a structural engineer, canine handlers, and ?various specialists in handling special equipment to find and extract a victim?. The engineer oversees and judges the structural integrity of the building where the rescue is taking place, while the canine handlers use their dogs to search with their keen senses. Equipment that is commonly used in USAR efforts consists of video cameras mounted on poles that are inserted into crevices to look for survivors (Figure 1.2). Listening devices are also used to hear calls for help, and thermal imaging is used to search for body warmth. Figure 1.2. Rescuers search for survivors at a disaster scene [1]. Snake-inspired robots would be a valuable aid to such rescue crews in many situations. Robots could be mounted with sensor equipment and allowed to search the rubble in order to relay up-to-the-minute information back to rescuers. Cameras, 8 microphones, and a variety of sensors could be mounted on snake-inspired robots, and the robots could travel deep into the rubble, obtaining information that might otherwise be difficult for rescuers to obtain. Snake-inspired robots could be used to find survivors in voids deep in the rubble, or to survey the structural integrity of the damaged building. Snake-inspired robots could travel in areas where it would be impossible, impractical or dangerous to send humans or even dogs. This would be the case because of both their unique attributes, and simply because they are expendable. If a piece of rubble falls on a segment of a snake-inspired robot, damaging it, the robot could still function due to its hyper-redundant characteristics. Because of their characteristics, they could search the rubble faster and more effective than human rescuers. Furthermore, if many robots are used, the effort can be accelerated even further. This would especially be the case if autonomous robots could be developed that operate in swarms. Inspection Another important and beneficial use of snake-inspired robots is inspection tasks. In many circumstances, it is necessary to inspect environments that are either too small for humans to inspect, or are too dangerous to send a human into. Examples of such tasks would vary from the inspection of the ballast in a Navy ship or submarine to the inspection of portions of a reactor in a nuclear power plant. Other examples could range from the unstructured environment of a space station to the tight environment of a pipe network. 9 The same attributes that would make snake-inspired robots desirable in USAR tasks would also make them desirable in tasks of inspection. Robots could again carry sensor equipment to record and relay information about the use environment. The benefits of a small cross section and stability would come into play when navigating the unstructured and tight environments that may be required in such inspection tasks. Figure 1.3. Example of an industrial pipe structure [2]. Routing of Cables In addition to inspecting environments such as pipes, serpentine robots could also be used to route cables through complex pipe structures (Figure 1.3). Cables could be attached to the robot, and the robot could then travel the desired path of the routing, placing the end of the cable at the final destination of the routing. 10 1.2 Motivation The motivation for this work can be organized into three areas of improvement for snake-inspired robots: a) modeling, b) gait design, and c) mechanical design. 1.2.1 Kinematic and Dynamic Model In order to design a snake-inspired robot that utilizes a vertical rectilinear gait, it would be advantageous to have a kinematics and dynamics model for a multi-linked snake-inspired robot that is moving in such a fashion. By being able to compute the torque as a function of time during the entire course of motion for the gait, relevant information about the snake-inspired robot design (metrics such as effort) can be extracted. In order to develop functional snake-inspired robots, they must be designed to meet certain functional requirements and performance characteristics. These may be characteristics such as maximum forward velocity, range, operation time, payload, and many more. If a design is to be developed to meet such parameters, then a model should be devised to determine how certain design parameters, such as module mass, length, and the gait parameters, affect the performance of the robot. A dynamic model must be developed (with a kinematic model preceding it) that will allow the designer to ascertain the necessary parameters to compute the performance. Such a model could then facilitate optimization, feasibility studies, and scaling of snake- inspired robot designs. For example, if one were designing a robot for a particular mission that required the robot to travel a certain distance in a certain amount of time, 11 the use of the dynamics calculations would allow one to determine the amount of effort required by the robot, and thus the power supply could be selected accordingly. A kinematics and dynamics model would be a central component of a possible overall system model for the design of a snake-inspired robot like the one shown in Figure 1.4. Figure 1.4. Chart of a possible overall system model. Most of the work in snake-inspired robot kinematics and dynamics has been conducted on snake-inspired robots that move with a serpentine gait (lateral undulation) using wheels or other features on the ventral surface to provide the needed anisotropic friction to achieve forward locomotion. Other robots have been developed and demonstrated that use a rectilinear gait without wheels and have been shown to move through varying terrain. However, a detailed analysis of their Module Parameters Number of modules Module length Module diameter Atructure mass Battery mass Maximum twist angle Servomotor Max speed Max acceleration Torque curve Mass Gait Parameters Time step Gait angle Kinematics Model Dynamic Model Geometric Model Constraints Cost Manufacturing Optimization Routine Performance Characteristics Forward velocity Maximum torque Torque-to-weight ratio Range Mission time Payload Radius of curvature Total weight 12 locomotion kinematics and dynamics have not been thoroughly developed. This is due to the fact that the dynamically changing ground contact causes the system to morph during the gait. 1.2.2 Gait Design While rectilinear gaits have been implemented, it is desirable to have a framework to generate gaits with desirable performance characteristics, or even optimal performance characteristics. A motivation for this work is to develop a highly- controllable means for gait design with an optimization model. Thus, gaits can be easily synthesized that provide desirable characteristics such as requiring less effort. Earlier gait designs have mostly been based on linear joint trajectories, or joint trajectories that are based on sinusoids. A better joint trajectory representation needs to be developed such that the gaits can be highly tuneable. A parametric gait design is needed such that trajectories can be easily controlled. By using joint trajectories that are highly tunable, the gait design can then be integrated with the dynamics model to design gaits that are optimal. 1.2.3 Improved Mechanical Design A considerable barrier in the development of snake-inspired robots is that they are currently expensive to produce, as they require manual assembly of many small parts because of the many sections and joints. This is especially important since one of the probable uses for snake-inspired robots, dangerous search and rescue applications, would place the robots in locations where it is likely that they would be destroyed. 13 Further, it would be desirable to have many snake-inspired robots in such a situation so that many can be deployed at the same time, increasing the amount of ground that is covered by the search. A snake-inspired robot design that is comprised of identical modules could lead to reduced costs if the modules could be mass produced and easily assembled. This means that they could be rapidly assembled for deployment. They could also be assembled to custom requirements such as length. Such modules should be designed and manufactured in a means that reduces both parts and assembly operations, yet still has a rugged enough design to withstand hazardous environments. Most prior work in the field of snake-inspired robots has paid scant attention to part counts and assembly operations, resulting in robots that contain many parts that are manually assembled. Large amounts of assembly operations can lead to high manufacturing costs. If snake-inspired robots could be developed and manufactured in a low-cost means, they could be considered to be expendable and possibly disposable. This means that search and rescue workers could send many of them into a location to retrieve data, and not have to be concerned with whether or not they are recovered. This would allow search and rescue workers to obtain more data in less time, and allow more focus to be spent on rescuing survivors and securing dangerous areas, instead of retrieving their search and rescue robots. The final motivation for this work is to develop and demonstrate the operation of a fully-modular snake-inspired robot that has been constructed using a concurrent assembly and fabrication process, multi-stage multi-material molding, aimed at low- cost fabrication. The use of multi-stage multi-material molding would significantly 14 reduce the part count and assembly operations required to produce each module. The use of mechanically-embedded components could further improve on the design goals by encasing components to protect them from the environment, and eliminating a host of fasteners that are typically required to hold such components in place. 1.3 Thesis Goal and Scope The goals and scope of this thesis can be organized into the several topics laid out in Sections 1.2.1-1.2.3. First, a formulation for the kinematics and dynamics of a 6-link snake-inspired robot locomoting with a particular class of rectilinear gait on flat terrain is presented. A means of analysis is presented that is conducted by breaking up the motion into separate mechanisms, and a set of equations using an Eulerian framework with a Coulomb friction model is presented to calculate joint torques and effort values. Second, a means of optimizing a gait is presented using the dynamic model that was developed and a B-spline curve representation of the joint trajectories. A simple discrete-sampling based approach is used to present how an optimization procedure would work, and a continuous strategy based on gradients is discussed. Third, a parametric study is conducted to demonstrate how several relevant design parameters affect gait design and performance. Finally, a fully-modular snake- inspired robot is developed that meets the following goals: 1. The robot will demonstrate that the class of locomotion gait that has been studied in this thesis will provide forward locomotion. 15 2. The robot will demonstrate the desired overall design architecture of a robot system that can be built out of identical modules. 3. The design will lay the foundation for a modular robot constructed with components that are embedded during the molding process, reducing parts, assembly operations, and also resulting in a more ruggedized module. 1.4 Organization The organization of this thesis can be divided into three major technical sections, in addition to the related work section: Chapter 2 is a literature survey of subjects relevant to this thesis. The major topics of discussion are snake-inspired robot design, snake-inspired robot kinematics and dynamics, rectilinear gait design for snake-inspired robots, and effort-based optimization for robot joint trajectories. Chapter 3 contains complete description of the gait synthesis and analysis problem. The general form of the gait must be selected, and the model developed. Once the rigid-body model with morphing topology is defined, then the kinematic and dynamic relations and constraints are developed to produce the complete system of Newton-Euler equations for each step of the gait problem. Utilizing this set of equations, which predicts the torque in each joint, the effort of the gait can be computed. This effort calculation is then used to develop a framework for optimizing the gait as a function of the joint trajectory parameters, by searching for minimum- 16 effort solutions. The results from a discrete sampling-based solution are presented, with the framework for a continuous solution using direct gradient computation. In Chapter 4 of this thesis, a parametric study of the bulk design parameters of the robot is discussed. Physical parameters of the robot and the gait are varied and the effects that they have on the gait performance is evaluated and discussed. This section is important for studying how snake-inspired robots can be modified and optimized for specific mission parameters. The final technical chapter, Chapter 5, describes the physical realization of a snake-inspired robot. The complete design and manufacturing process for the robot is presented. Emphasis is placed on the modular architecture of the design, as well as the novel, low-cost means of manufacturing utilizing multi-material molding. Furthermore, a design that may further reduce assembly costs by using physically embedded components is discussed. 17 Chapter 2 - Related Work 2.1 Overview The development and analysis of a snake-inspired robot is a multidisciplinary task. Thus, the body of literature and the previous work that has been done that pertains to snake-inspired robot design, development, analysis, and gait generation can be grouped into several different topics. First, biological snake locomotion is described. Authentic snake locomotion serves as the inspiration for this snake-inspired robot concept, and thus biological snake locomotion must be understood in order to mimic snakes using robotic devices. Second, the design of current snake-inspired robots and their differences, advantages, and disadvantages are discussed. In order to analyze the kinematics and dynamics of a snake-inspired robot, which must be done in order to develop and characterize gaits, the body of work that exists in the area of kinematic and dynamic analysis of snake-inspired robots is investigated. The third section addresses different models. The robot described in this thesis progresses using a rectilinear gait, and this approach to motion builds on prior work. This work is discussed in the fourth section. Finally, because this thesis seeks to provide a framework for optimizing the gait, prior work and different approaches to robot joint trajectory optimization are discussed. 2.2 Snake Locomotion There are four common and distinct gaits that snakes typically use in terrestrial locomotion. These are known as: a) serpentine (lateral undulation), b) concertina, c) 18 sidewinding, and d) rectilinear progression [3]. Most snakes are capable of executing all or several of these different forms of locomotion, and typically switch as the conditions require. In certain circumstances, a snake may even use a hybrid combination of more than one gait. Serpentine Locomotion Serpentine locomotion, also known as lateral undulation, is the most common form of locomotion used by snakes (Figure 2.1). All snakes are capable of serpentine locomotion, and they frequently use serpentine locomotion when moving through terrain such as grass, stones, and sand. The snakes body moves laterally in a sinusoidal curve that propagates down the snake. In this form of locomotion, every part of the snakes body follows the same path as the snake moves along. The forward propulsion occurs due to forces pushing laterally (normal) against the snakes body. These forces are mostly achieved by the snake pushing its body against obstacles located along its path (Figure 2.2). Obstacles can be large, such as a stick or rock, or small, such as small pebbles and sand. Studies have shown that snakes will alter the curvature of their serpentine waves dependant on the terrain that they are moving over and the location of obstacles in that terrain [3]. 19 Figure 2.1. Serpentine Locomotion [9]. Figure 2.2. Snake exhibiting serpentine locomotion through a series of vertical pegs. The snake alters its curve proportionally to peg spacing [3]. 20 Concertina Locomotion A second form of locomotion in snakes is known as concertina locomotion. Concertina locomotion is used less frequently than serpentine locomotion, but it is often used in situations where the snake is moving through a thin tunnel or channel. It is also used, although less frequently, on terrain that is rough but uniform. Concertina locomotion is shown in Figure 2.3, and consists of the body configuring itself into short curves. The curvature is then increased, propelling part of the snake forward. The snake then recompresses to repeat the motion. The forward propulsion exists because a portion of the snake remains static with the ground while the other portion is compressing or uncompressing forward. These static contact points are achieved by either the snake exerting pressure on neighboring obstacles or by the ventral scales preventing backward slipping against the ground. Figure 2.3. Steps 1-7 show the progression of snake as it exhibits concertina locomotion. Portions colored black are stationary while portions colored white are sliding [3]. 21 Sidewinding (Crotaline) Locomotion A third, and very distinct form of snake locomotion is known as sidewinding. Sidewinding is a form of locomotion that is typical of a certain group of rattlesnakes that live in sandy deserts. Sidewinding is similar to serpentine locomotion in that the sidewinder propagates waves of curvature along the body. However, in sidewinding locomotion, the resultant movement of the snake is sideways with respect to the axis of the body. Figure 2.4 shows tracks that are produced by the sidewinding locomotion that point in the direction of the travel. The snake lifts and rolls its body between the tracks to achieve advancement, as the sections that lie within the tracks are in static contact with the surface. The weight is appropriately transferred to these points to ensure proper friction with the ground. Sidewinding can be considered a specialized gait that is only used on slippery surfaces such as sand. Figure 2.4. Sidewinding Locomotion. The shaded portions are at rest with respect to the ground [3] . 22 Rectilinear Locomotion The final common form of snake locomotion is known as rectilinear locomotion. Rectilinear locomotion is a form of locomotion that is common to large snakes with well-developed muscles such as boas and pythons [4]. This form of movement is distinct from the other forms of locomotion in that the snake progresses with its body fully aligned with the direction of movement. Movement is achieved by waves of muscular contraction and expansion passing along the body of the snake. This form of locomotion is best understood by imagining two points located on the ventral (bottom) surface of the snake. With the waves of muscular contraction and expansion, the distance between the two points is oscillating. When the distance between the two points is at a minimum, that segment is at rest. When the distance between the points is either increasing or decreasing, the moving point is moving forward. This is achieved by the frictional characteristics between the snake and the surface, and can be thought of as a ?ratcheting? action. The points on the ventral surface move forward in discrete steps. However, the top of the body moves continuously because of the changing geometry of the muscular segments. Figure 2.5 shows marked points on the ventral surface as the snake progresses forward. Figure 2.6 illustrates the muscular contraction and expansion that occurs during rectilinear motion. 23 Figure 2.5. Points on the ventral surface of the snake are used to demonstrate rectilinear motion. Heavier points denote static contact while the lighter points denote sliding contact [4]. 24 Figure 2.6. Rectilinear Motion. In step one, region A is at maximum contraction, region B is contracting, region C is at maximum elongation, and region D is elongating. The progression of the wave is seen through the motion steps of the gait [4]. Energy Consumption From a biomimetic perspective, it is easy to see why snake-like locomotion would be of interest to the robot designer. Snake-inspired robots have many advantages over other forms of legged and wheeled locomotion, such as redundancy and a small cross section. However, it is widely believed that snake locomotion is costly from an energy perspective because of its reliance on slipping and the fact that it uses significant lateral motion to achieve a much smaller amount of forward motion. Studies conducted on a black racer (Coluber constrictor) using the standard oxygen consumption test have indicated that this is a misconception [5]. These studies have shown that the net cost of transport for a snake locomoting via lateral undulation is similar to the net cost of transport for similar-sized lizards and mammals. However, 25 concertina locomotion was shown to be significantly more costly. The tradeoff lies within the fact that concertina locomotion is often used in tight environments such as tunnels. Likely explanations for the similar cost of transport between limbless and limbed locomotion are that while snakes lose energy to friction, limbed creatures expend energy lifting their center of mass and accelerating limbs. Discussion and Relevance The understanding of snake locomotion in nature gives us several candidate means of locomotion to use for a snake-inspired robot. By observing snakes in nature, we can determine the mechanism they use to achieve propulsion, and how they modify these mechanisms as the terrain changes. In this thesis, a gait directly inspired by rectilinear locomotion in snakes is selected for study because it depends on static friction and allows robots to fit through narrow passageways. 2.3 Snake-Inspired Robot Designs for Search and Rescue This section seeks to shed light on the field of snake-inspired robots designed for information-gathering applications, such as urban search and rescue and inspection. A considerable amount of work has been done in the field of snake-inspired robotics. However, many of the designs are somewhat similar and many of the goals of the robot realization are different (for example, to provide a platform for a new actuation technology). Therefore, this section is not a complete review of snake-inspired or serpentine robots. Rather, the discussion is limited to designs that can be considered ?pioneering? works, designs that have been specifically designed for meeting the 26 requirements of a search and rescue mission, and designs that can be considered somewhat ?novel?. It should be noted, however, that as of this point, snake-inspired robots have not been fully developed and used in real search and rescue environments. The case for snake-inspired robots has been made by several different researchers. Hirose envisioned a search and rescue paradigm which he calls ?snakes and strings? [6]. Similarly, Gavin Miller presented a similar case for such robots [7]. He envisioned a detailed search and rescue scenario whereby a snake-inspired robot could be equipped with an array of sensors such as infrared, pyroelectric, cameras, and microphones. The robot was teleoperated by a search and rescue worker and used to find a survivor. As discussed in Chapter 1, snake-like robots can traverse into areas that humans and dogs can not, obtaining information that is vital to the search and rescue effort, such as site structural integrity and survivor locations. Yim et al. discussed the same mission as a need to develop self-reconfigurable robots [1]. They developed a robot called the PolyBot that could locomote using a snake-like gait and discussed how it could be used in search and rescue applications. While the literature search focuses only on snake-like robots, it is important to note that many researchers developing this other class of robots have also shown their robots to be able to locomote with snake-like gaits [8]. 27 Active Cord Mechanism Shigeo Hirose is considered one of the pioneers in snake-like robots, and his original robot called the Active Cord Mechanism (ACM) was the first functional snake-like locomotor (Figure 2.7) [9]. The purpose of Hirose?s first ACM was to understand the mechanism of locomotion in real snakes. Following many studies on real snakes to ascertain the mechanisms of locomotion, Hirose developed the ACM to validate the work. Figure 2.7. Active Cord Mechanism by Hirose [9]. The first ACM consisted of 20 links, and had movement in only two dimensions. This means that it glided along the floor using a serpentine gait. At the core of Hirose?s theories about snake locomotion was the fact that snakes produce an anisotropy in friction coefficients between the lateral and tangential frictions on their ventral surface. This is what causes the propulsion in the serpentine gait. In order to realize this in a robot, Hirose placed small wheels on casters on the bottom of each link, facing in the tangential direction of the length of the robot. This resulted in a 28 very low friction coefficient in the tangential direction, and a high coefficient in the normal direction that the snake uses to propel itself. The links were connected using joints that allow rotation to each other, and locomotion was accomplished by rotating the wheel-base mechanism back and forth. This meant that locomotion was only accomplished through shape changing, like a real snake. The entire robot weighed 28 kg, and was 2 meters long. Each joint was actuated using a servosystem that consisted of a motor and a potentiometer. Control was achieved via a system whereby a command was sent to the first motor, executed, and then sent to the next motor to be executed. After demonstrating locomotion on a flat surface with no obstacles, Hirose demonstrated how snakes alter their path when obstacles are present by conforming to their environment, and how they use obstacles to propel themselves. This was achieved by adding binary tactile sensors on the lateral sides of each link. In these experiments, Hirose demonstrated how the robot could fully conform to a shape. Work also was done to demonstrate how a snake could propel itself through an abstractly-winding track using only pressure from the walls (Figure 2.8). In this experiment, casters that could roll in 360 degrees were placed on the bottom of the links so that there was not anisotropy of friction coefficients. 29 Figure 2.8. ACM traveling through a track using sensors [9]. The original ACM, although not practical for applications other than locomotion on a smooth floor, was a significant contribution to the field of snake- inspired robots. It provided a proof of concept for Hirose?s models of snake locomotion, and provided much information on the control of large, hyper-redundant robots. It also generated interest in the field, and was the first step in a line of ACMs by Hirose. Hirose later applied his results with the first ACM to a much improved snake called the ACM-R3 (Figure 2.9) [10]. The ACM-R3 was designed to be more functional in an actual search and rescue application. Unlike the first ACM, which ran off of an electrical tether cord, the ACM-R3 contained batteries for power, and the servomotors were radio controlled. Each unit contained its own battery and 30 controller, making the design fully modular. The modular architecture means that there were 6 wires running between modules, as opposed to many more. Figure 2.9. Hirose's ACM-R3 [10]. The largest differences in the ACM-R3 were that it was capable of 3D motion, unlike the first ACM, and it had large wheels on all sides of the body. These large passive wheels have diameters of 110mm, and add functionality to the system because they can roll against contacted obstacles. The design of the links is such that everything is contained in a shell that has orthogonal axes of rotation on each end. A key requirement in the development of this design was that the snake be able to lift its body weight up. Hirose accomplished this by using servomotors that provided 19 Nm of torque, and the design could lift 8 units up into the air. The overall specs for the ACM-R3 are as follows: 31 Dimensions: 110 X 110 X 1755 mm Mass: 12.1 kg Maximum Twist Angle: 62 degrees (each direction) Like the first ACM, the ACM-R3 executed a serpentine locomotion gait using the passive wheels. However, in addition to the serpentine locomotion, it could lift its body up to move over obstacles. Hirose also experimented with other gaits on this mechanism, including a lateral rolling gait. This design provided a marked improvement over the first ACM because it was self-contained, meaning that it had on-board power and can be radio-controlled. The design also showed an improvement in ruggedness, with all of the components mounted inside a shell. Also, an extra degree-of-freedom was added such that the robot could lift up to maneuver over obstacles. The design, however, still required a flat surface on which the wheels could roll to allow locomotion. The design of the ACM-R3 has since been improved in the generation of the ACM-R5. The ACM-R5 has the added capability that it can move on both land and in water, due to a rugged, waterproof packaging. The ACM-R5 also has wheels on six different sides as opposed to four. Finally, it can operate for 30 minutes without recharging, and has an integrated camera mounted on the ?head? unit. To date, no work has been published on the ACM-R5, but the robot was presented at The 2005 World Exposition in Aichi, Japan [11], and detailed information about the ACM-R5 is also avaliable [12]. 32 Robot Developed by Kevin Dowling Another early implementation of a snake-inspired robot was developed by Dowling at Carnegie Mellon University [13]. Dowling developed a snake-inspired robot while studying gait generation using machine learning. Dowling took a comprehensive look at a wide range of possible technologies that could be used in snake-inspired robots, and designed a snake-inspired robot that could move in three dimensions around a servomotor actuator. Unlike the work of Hirose, Dowling?s robot did not require passive wheels in order to move. Dowling looked at the geometric design of a snake-inspired robot as it related to mission parameters. He determined the dimensions of curved and right-angle pathways that a snake could fit into as a function of link geometry and twist angle. Dowling found that the angle of motion is not as important as the link length. The link length should be as short as possible. The mechanical design of this robot consisted of an aluminum sheet with servos mounted to it. The servos were mounted orthogonally, so that each end of the link contained an actuated revolute joint. The rotating sections were mounted directly to the servo horn, and adjacent links were attached to each other such that orthogonal servos connect to each other. A sample link can be shown in Figure 2.10. The robot contained 10 links for 20 degrees-of-freedom, and had an overall length of 102 cm. The mass of the robot was 1.32 kg, and each link had a diameter of 6.5 cm. The robot was controlled using centralized control and powered using a tether. The servos were controlled using a DCC bus and wires that runs the length of the 33 robot. The control circuitry was located in the ?head? of the snake. NiCad batteries were proposed as a power source, but external power was used in the actual implementation. Additionally, a CCD camera was mounted on the head unit. The entire robot is shown in Figure 2.11. An interesting feature of this robot was that use of ?skin? was investigated to provide desirable friction characteristics. Dowling proposed covering the entire robot in a fabric or material that would provide good friction characteristics in order to propel the snake forward. Several candidate materials were discussed and evaluated. Figure 2.10. One link of Dowlings snake-inspired robot [13]. 34 Figure 2.11. Dowlings snake-inspired robot [13]. Other Early Works Other interesting early snake-like robots include those developed by Chirikjian and Burdick at Caltech [14], Shan [15], and the ?Kaa? robot designed for climbing by IS robotics [2]. An important aspect of snake-inspired robot design is the design of actuated joints. Ikeda and Takanashi of NEC developed an innovative joint for serpentine robots and manipulators [16]. The joint was based on an actuated universal joint and was to be used in a snake-inspired robot called the ?Quake Snake?. NASA?s Jet Propulsion laboratory used a modified version of NEC?s joint in the design of their 12 degree-of-freedom hyper-redundant manipulator that could be used for spacecraft applications, functioning in a crowded workspace [17]. The joint used by JPL consisted of a u-joint within a gear-head and bearing assembly. The difference between the JPL joint and the NEC joint was that the NEC joint was on the outside of the assembly. 35 An innovative search and rescue solution that utilized a hyper-redundant robot with an actuated universal joint was developed by Wolf et al (Figure 2.12) [18]. This robot consisted of a hyper-redundant manipulator robot mounted on a mobile base. Seven actuated, serially-chained, 2-DOF joints constituted one component of the robot which had a camera mounted on the end. This allowed for the end to be inserted into hard-to-reach locations to gather data in a search and rescue effort. The structure was mounted on a mobile base that utilized a standard four-wheel vehicle configuration. The design of the hyper-redundant chain consisted of actuated universal joints with orthogonal axes of rotation. Actuation of the universal joints was accomplished by linear ball screw actuators that push and pull against the joint. The joints also contained an innovative ?snubber? mechanism to prevent damage when a load is placed on the structure, or the stops of the movement have been reached. The joints allow for 55 degrees of motion in each direction. Like other designs, Wolf et al. realized that it was impractical to run wires through the structure to each of the 14 actuators. Therefore, the control was accomplished using an I2C control bus that runs along the length of the structure from the mobile base. Each link component contained its own H-bridge, decoder, and PIC microcontroller. PWM signals were used to control the motion of each link. 36 Figure 2.12. Actuated universal joint design by Wolf et al [18]. Robots Developed by Gavin Miller Another body of work that is of interest in the area of snake-inspired robots is that of Dr. Gavin Miller [19]. Dr. Miller?s snake-inspired robot effort is entirely self-funded, yet he has been able to produce a family of sophisticated and life-like snake-inspired robots that are complete with power, control, and sensors. Miller?s robots were inspired by the work of Hirose, and used passive wheels on the bottom to assist in movement using a lateral serpentine gait. Realism and aesthetics were a major portion of the design goals. Miller?s serpentine robots culminated in his most sophisticated design, called the S5 (Figure 2.13). The S5 was inspired by real snakes and built on an earlier design, the S3. The basic design used universal joints on the top of the robot and two servos on opposite sides of each link that were used to produce lateral and vertical motion. The complete design consists of a head unit plus 32 actuated links that were actuated using 64 servos. Control was achieved using one Basic Stamp II microprocessor (20 MHz), one Scenix Microprocessor, and 8 servo control units. Power was supplied using 42 batteries, and the snake was controlled using a radio controller. 37 Figure 2.13. Gavin Miller's S5 snake-inspired robot [19]. In addition to the S5 and its predecessors, Dr. Miller also made several attempts to create a snake-inspired robot that only used one motor, and is currently working on a new design of a snake-inspired robot without wheels that locomotes using a rectilinear gait. In order to develop a snake-like robot with only one motor, he developed a system of gears and rockers that would propagate undulations down the robot. The design, however, failed. The rectilinear design is based on a python and is currently under development. It reportedly has a sensor suite that contains sonar, a compass, and pyroelectric heat sensors. 38 AmphiBot A recent snake-inspired robot developed with the use-environment in mind is called the AmphiBot [20]. AmphiBot was created as an amphibious robot capable of anguilliform swimming and snake-like undulation. It was produced as a bio-inspired robot to investigate how the central nervous system implements locomotion in animals using a central pattern generator. The AmphiBot was designed to be modular so that individual elements could be quickly replaced and also added and subtracted. Each element contained its own motor, battery, and microcontroller. The robot was remotely controlled and moves in a lateral serpentine gait, assisted by passive wheels. In the water, the lateral sides of the robot generate the forward forces. The design was developed to be rugged and waterproof. Each individual module was constructed to be waterproof, as opposed to just having a waterproof coating around the entire snake. The structural components were molded using polyurethane. The LiPo batteries were molded directly into the casing and the battery charging circuit was built into the design. The battery with a 600mAh capacity was used, which allowed for 2 hours of continuous use. Each link consisted of four components: a body, two covers, and a connection piece. O-rings were placed in between the covers and the body to form a seal. Five wires that are molded directly into the connection piece were used to supply the control bus and the power bus (when charging) to the entire snake. Each link has a length of 7 cm and a cross section of 5.5 cm by 3.3 cm. 39 OmniTread Up to this point the discussion has been limited to robots that locomote purely by snake-inspired means, whether that be serpentine, concertina, sidewinding, or rectilinear. There is a different class of robots that are designed for search and rescue applications that are inspired by snakes, but use active means of progression as opposed to body undulations. These robots were designed to be shaped like snakes and have many degrees of freedom. What separates them from the snake-inspired robots that were previously described is that they use active wheels or tank treads to generate forward motion. An example of one such robot was the OmniTread robot developed at the University of Michigan [21]. The first OmniTread robot was called the OT-8 (Figure 2.14). This robot consisted of five links that were connected by four, two-degree-of- freedom joints. The propulsion of the robot was achieved by an innovative means: Using tank treads on the four sides of every link. The tank tread design maximizes the ?propulsion ratio?, the ratio of surface area that is active in propulsion to the surface area that is not. In order to maximize this ratio, tank treads cover as much of the sides as possible and the gap size between the links are minimized. The idea behind the maximization of this ratio is that any environmental feature that contacts the robot at a location not covered by treads will impede the motion. Treads on each side also make the design indifferent to falling over. The second innovative feature of the OmniTread was that it is designed with pneumatic bellows that acted as the actuators between the links. These allowed for dual functions. The bellows allowed compliance between the links, allowing the 40 robot to passively conform to the terrain to maximize traction. The pneumatic bellows meant that stiffness could be adjusted ?on the fly?. An example of when this would be needed is when the robot is climbing over a gap. Thus, the bellows were used to both actuate the joints and adjust the compliance. A total of 16 bellows were used, giving the robot 16 position parameters and 16 stiffness parameters. Two valves were used to control each bellows. A universal joint was located in the center of the space between links (between the bellows) in order to maintain structural rigidity. One motor provided the power to all of the tracks in the robot using a central drive shaft spine running the entire length of the robot, using universal joints. In the next iteration of the OmniTread (OT-4) [22], each link contained small clutches that can engage and disengage each tread as is needed. The dimensions of the OmniTread OT-8 links were 20X18.5X18.5cm and the entire robot was 127 cm long. The complete robot weighed 13.6 kg. Performance testing has been completed on the OmniTread design. The robot has been shown to be able to climb up a curb more than 36% of its length, and 240% of its height. Additionally the robot can lift up two of its head or tail segments. The OT-8 operated off of a power and pneumatic tether, but the newer OT-4 has built in CO2 cartridges and batteries for up to one hour of continuous operation. The OT-4 can also fit through a hole with a diameter of only 4 inches. In order to have such a compact design, the OT-4 was designed with complex links that are rapid prototyped using a stereolithographic resin process. The links are reinforced with aluminum. 41 Figure 2.14. Omnitread robot climbing up a step [21]. Overall, the OmniTread robots would appear to be much more functional than other snake-inspired robots that have been produced to date, but the improved functionality comes with a cost. The mechanisms in the OmniTread, including all of the drive belts and drive shafts make it much more complicated to manufacture than the other robots. The OT-4 is so complicated that its components must be produced using an SLA technique. GMD-Snake Another, earlier snake-like robot that used driven wheels was developed by Klaassen and Paap [23]. This robot was called the GMD-Snake2 (Only the second iteration is reviewed in this thesis, as it builds on the first). The GMD-Snake2 consisted of cylindrical links that were connected by universal joints and had wheels on the bottom that are driven by small motors. Additionally, the position of each joint was controlled by three motors that used small ropes to move the joint. The robot was designed to be a rugged design for practical applications. Links were built around an aluminum cylinder with holes on the surface. The device 42 could be operated on a tether, or the last section could be entirely filled with batteries. The diameter of this robot was 18 centimeters and the length was 1.5 meters long. The robot had a mass of 15 kg. Like many of the other robots, each section contained its own processor and communications were achieved via a bus. Discussion and Evaluation There are several common themes in the design of many of these snake-inspired robots. Upon reviewing the designs, it can be seen that distributed control is often used, with processors and chips located in each of the links. This is done for two reasons: simplicity and modularity. In the case of the AmphiBot, the processors are located locally so that the design is modular and links can be easily added. The control system based on the central pattern generator allows for this scheme. On the other hand, in the hyper-redundant robot by Wolf et al. the processors were distributed locally so that a large number of wires do not need to travel the length of the robot. Another common design feature in many of the robots discussed is that they rely on either a universal joint or two revolute joints in an orthogonal configuration. This is taken from the inspiration of snakes. Snake vertebrae allow for lateral and vertical twisting, and snakes locomote by using both means to move their bodies. The robots discussed that only have motion in the lateral direction were designed for the laboratory to demonstrate gaits and control architectures. In the case of Hirose?s robots, the extra degree-of-freedom was later added. 43 In general, it can be seen that the majority of snake-like robots have been developed to demonstrate gaits, control schemes, and validate mathematical theory in the laboratory environment. Many of them rely on small passive wheels to locomote on smooth surfaces. In an actual search and rescue environment, the surface may not be smooth enough for the wheels to roll. In addition, many of the robots have been designed for the physical environment of the laboratory instead of the actual search and rescue environment. More recent robots, such as the AmphiBot and the ACM-R5 have been developed with ruggedness in mind with their waterproof design. The OmniTread can be considered the most functional robot for search and rescue application, however, it illustrates another major drawback in snake-like robot design. The design of the OmniTread contains many parts and is complicated from a mechanical standpoint. Considering that each bellows requires 2 valves to actuate, the entire design has 48 different valves for actuation. Since the actuation of the bellows requires air lines, a manifold is built into the chassis. The shape of the chassis is so complicated that it must be built using the SLA process. The drive train also requires man parts including worm gears and universal joints. The OmniTread is not alone in its large part count. Looking at Figure 2.10, it can be seen that assembling just one link of Dowling?s robot would require the relative placement of 9 parts and more than 16 screws. Large part counts, large number of assembly operations, and specialized manufacturing processes would make these snake- inspired robots costly to produce. 44 2.4 Snake-Inspired Robot Mechanics: Kinematics and Dynamics The first analysis of the mechanics of snake-inspired robot locomotion was done by Shigeo Hirose, along with the development of the ACM [9]. Hirose began by posing a snake mechanism as a series of serial robot links with infinitesimal length. He assumed that the snake moved by undulation in 2 dimensions. By using a summation of the forces and torques acting on the body of the ACM, Hirose developed ?force density functions? along the parametrized length ?s? of the robot, as functions of continuous torque, T(s), and curvature, ?(s). Functions were developed in both the tangential direction (Equation 2.1) and the normal direction (Equation 2.2), and were integrated over the length of the robot to develop the propulsive force and the amount of lateral ?pushing? done by the snake. )()()( sdssdTsft ?= (2.1) 2 2 )( )( ds sTdsfn = (2.2) Using these equations and the expression for power, a power density function was also developed that expresses the power in terms of torque, curvature, and tangential velocity. As for analysis of the kinematics, Hirose assumes that the body of the snake takes on a continuous curve where each segment follows the previous segment. 45 Hirose proposes a curve to describe snake locomotion as well as parameters that govern the specific locomotion. Observing that the curvature of a sine wave is irregular as a function of curve length, Hirose proposed two curves to describe snake locomotion. One is a composite curve based on the clothoid spiral by Umetani, with linear curvature with respect to length. The second curve, which Hirose named the serpentoid curve (Equation 2.3), has a curvature that varies sinusoidally with length. Hirose proposed that snakes moved with a serpentine curve because it has the ?greatest amount of smoothness of contraction and relaxation of the motor muscles? [9]. ? ? ? ??? ? ?????? ???= ???????+= ? ? ? = ?? ? = l sm m Jlsy l smJ m lsJsx m mm m m m pi?pi pi?pi? 2 12sin 12 )()1(4)( sin)(2 )1(4)()( 1 121 2 1 0 (2.3) The parameter ? is called the winding angle (Figure 2.15) and defines the angle in which the snakes body intersects with the line that indicates the direction of progress. Jm indicates the mth order Bessel function. These two curves are compared with measured data from actual snake locomotion, along with a composite arc curve and a sinusoid, and are shown to closely agree with the measured data, with the serpentoid curve being the closest match. 46 Figure 2.15. Nomenclature for Hirose?s equations [9]. Upon developing functions to describe the shape of snake locomotion, Hirose proposed a function to describe the muscular force acting on each joint (Figure 2.16). Functions are proposed with the nature of the body shape and structure in mind, and are dependent an independent parameter that was experimentally obtained from real snakes. With the functions for muscle force and gait shape developed, expressions for propulsive (tangential) force and normal force were developed. The experimentally-measured forces were shown to agree with the proposed model. 47 Figure 2.16. Model of muscle structure in snake joint [9]. The major contributions of Hirose?s work can be summarized as the following. Hirose used a biologically inspired approach to describe and quantify the geometric and dynamic aspects of real snake locomotion. In his work, he developed a parameterized model of such locomotion, and both experimentally verified his conclusions on real snakes and a synthesized robot system. His work assumed that the geometry of the snake took on a continuous curve, but since he formulated his equations in terms of curvature and torque distribution, his calculations can be modified for a snake with discrete links. Chirikjian and Burdick analyzed the kinematics of snake locomotion from a geometric standpoint [24]. They modeled the snake-inspired robot as a continuous backbone curve and analyzed the kinematics of gaits that used both ?stationary? and ?traveling? waves. Traveling waves would be those similar to rectilinear snake 48 locomotion, while stationary waves would be those more similar to inchworm locomotion. They used a two step process to compute the kinematics of snake locomotion where they first assume that the snake can be modeled by a continuous spline or ?backbone curve?, and then use this backbone curve to specify actual joint displacements. The model does not consider the dynamics of the system, and assumes that there is sufficient friction to enact the gait. In Chirikjian and Burdick?s work, the snake is assumed to take the shape of a spline, and a path of the motion is specified as well. The spline can be either extensible or inextensible. The spline is modeled by the following equation with ?s? as the normalized arc length and ?t? as the time: ?= s dtutltsx 0 ),(),(),( ??? (2.4) The component ?l? denotes the length of the curve tangent, and ?u? denotes the unit tangent vector of the curve, which is parameterized using Euler angles. In this formulation, the curve becomes a function of ?shape functions? that specify the orientation and position of the backbone reference frame as a function of time and parameterized arc length. A path that the robot takes is defined as a curve in R3, and the task becomes developing backbone curves that traverse the path curve, as shown in Figure 2.17. A ?stride length? is specified, which defines how far the robot traveled during one cycle of the gait. The task is then to determine a curve with the specified stride length that matches the path curve at either end of the stride, but does not intersect the path 49 curve. Gaits can be developed using this framework and techniques such as variational calculus. Figure 2.17. Parameters in Chirikjian and Burdick?s approach [24]. Another approach to gait kinematics was developed by Burdick and Ostrowski [25]. This work models the snake-inspired robot as a discrete set of links with passive wheels on the bottom. The model is based on Hirose?s first active cord mechanism (Figure 2.18). The variables of locomotion are divided into two sets: shape and position. The shape space is defined with a manifold with the order being the number of movable joints in the robot. The position variables are defined in the special Euclidean group SE(2), because the robot is constrained to motion on a plane. The total configuration of the robot can be defined with these two sets of spaces. 50 Figure 2.18. Burdick and Ostrowski model [25]. A framework is then developed using Lie algebra to determine how changes in the shape space affect changes in the configuration constraints through the nonholonomic constraint that the wheels place on the locomotion. The framework begins by defining a three segment snake, and the constraint is formulated as: ( ) 0cos,sin = ?? ? ? ? ?? ? ? ? ?? ? ? i i ii y x?? (2.5) This equation means that locomotion of each segment must occur in the direction of the wheels. The relationship between segments is established using a connection, and the relationship between angles and the position-changing of the snake can be established. Three links are used to start, because this constitutes the ?principal kinematic case?, the case where there are an equal number of constraints and equations. Adding a link adds two additional degrees of freedom, but only one constraint equation. When links are added, they are simply made to follow the first set of links. 51 Saito, et al. investigated the locomotion of a snake-like robot from a dynamic perspective [26]. They considered the case where a snake moves in a lateral serpentine gait due to anisotropic friction, but without wheels. Friction models were developed based on both viscous and Coulomb friction. The model found the frictional forces and torques acting on each link as a function of the shape and shape changing parameters. These equations were then assembled into a Newton-based formulation of the equations of motion. The behavior (velocity, acceleration) of the center of mass for the entire robot, as well as each link, can be computed from this set of equations. This framework resulted in a system of equations where the joint torque, joint angles, and inertial behavior of the entire robot are related. A similar framework was also developed by Ma et al [27]. Another dynamic framework for snake-inspired robot locomotion was developed by Cortes et al. [28]. In this work, a dynamic framework for the locomotion of a robotic eel was developed. The work used a Lie group formulation similar to [25], and the dynamics were addressed using a Lagrangian reduction process. Friction was modeled using a fluid friction model. Discussion and Evaluation While different kinematic and dynamic models for snake locomotion have been developed, none of them consider the dynamics of a snake using a vertical rectilinear gait. Work has been done by several different researchers to model the snake as both a continuous form, and a discrete set of links. Also, snakes with and without wheels have been investigated. Most of the models, however, deal with serpentine motion in 52 the lateral plane, with only [24] dealing with waves that travel in the vertical plane. This work only considered kinematics, and approximated the snake as a continuous curve. Gaits have been generated in the vertical plane, as will be seen in the next section, but minimal dynamic analysis exists for such gaits. The dynamic analysis does not exist because the changing points of ground contact apply reaction force loads intermittently, resulting in a complicated model. 2.5 Rectilinear Gait Generation In this section, the design and generation of gaits in snake-inspired robots that resemble rectilinear locomotion of biological snakes is discussed. As described in section 2.2, rectilinear locomotion is achieved in biological snakes by slight lifting and compression of segments, in order to creep forward. In snake-inspired robots, this gait is achieved by propagating vertical waves from the tail to the front of the robot to achieve advancement. Much literature exists relevant to the generation of a variety of forms of gaits, from serpentine to even non-biologically-inspired gaits. In this section, discussion is limited to only gaits that are considered ?rectilinear? and similar to the gait that is developed and analyzed in this thesis. Gaits of a rectilinear nature, where the robot lifts up its body, have been proposed in many different works, including [13], [24], and [29]. They are desirable because they have minimal slip, and are less dependent on the specific friction characteristics of the surface on which they locomote, as opposed to other gaits which may require passive wheels. Another gait somewhat similar to rectilinear locomotion, meaning that advancement is achieved by lifting in the vertical plane, is 53 executed by a caterpillar robot developed by [30] and [31], as well as Nilsson?s slip- free gait [32]. Robots utilizing rectilinear locomotion gaits have also extensively been developed at Carnegie Mellon?s Biorobotics Lab [33]. Merino and Tosunglu [34] presented a rectilinear gait for a theoretical modular robot that performed like a snake-inspired robot. They posed the gait as a series of configurations that the robot would take (Figure 2.19). The end result of this is the propagation of a half-wave from the rear to the front of the robot. It can be seen that the amount that the gait advances during each cycle is a function of the link length, and the angle at which the two outside links of the half-wave are inclined from the ground. From this, and assuming a linear servo speed, it can be seen that the velocity of the robot increases linearly with the angle. The robot was then modeled with the software package Working Model to confirm that the gait would achieve a forward motion. Figure 2.19. Merino and Tosunglu's Gait [34]. 54 Chen et al. [35] presented the idea of a ?traveling wave? gait similar to the work of [34] where the configuration of the vertical wave travels through a series of ?phases? as it moves forward. They proposed moving the angles according to a serptentoid curve to propagate waves from the rear to the front. Traveling wave locomotion is also addressed in [36]. Discussion and Evaluation Rectilinear gaits have been shown to be successful in snake-inspired robots, and this thesis builds on the work presented in this section. This thesis builds on the idea presented by [34] that by using a sequence of configurations a wave can be propagated through the snake to achieve forward locomotion. The work of Chen et al. [35] similarly noticed that the snake?s motion could be broken into ?phases? where different parts contact the ground. Both the modeling of these gaits and the drawbacks of the gaits that have been presented thus far are addressed in this thesis. The drawbacks of current gaits are that they have used either linear interpolations or sinusoids to specify their joint trajectories. In this work, a more controllable means of generating joint trajectories is used, resulting in trajectories that are more efficient. 2.6 Robot Trajectory Optimization Developing gaits for snake-like robots includes the generation of joint trajectories in order to specify the time history of how a joint changes its position. These trajectories can be optimized using a mathematical framework. A considerable 55 amount of literature exists in the area of optimal trajectory generation in manipulator robotics, and similar techniques and principles can be applied to the snake gait problem. This section provides a brief review robot trajectory optimization. In general, robot trajectory optimization can be classified into two approaches. The first approach uses an optimal control framework, and solves a two-point boundary value problem [37]. The second approach assumes that the joint trajectory follows a path that can be described using a set of parameters (often control points) and then seeks to vary the parameters until a local optimum is found. This approach has the advantage of being simpler; especially considering that robot manipulator equations are complex and highly non-linear. It also has advantages in constraint handling, because an initial path can be specified that satisfies constraints, and then an optimal path can be found by searching [38]. In this work, the performance of the joint trajectory is defined using a measure called ?effort?. Early attempts to formulate optimal control paths for manipulator robots typically focused on the minimization of time [39]. However, a problem with approaches such as these is that they do not consider the wear and tear on the robot joints, or the amount of energy consumed. A better function to minimize would consider both the time that the robot takes to complete the trajectory and the amount of torque and energy required to complete the motion. More recent approaches to trajectory planning have considered these issues [40]. An example of a study where a parameter-based effort minimization scheme is used is the work of Martin and Bobrow [41]. This work uses B-spline curves to define the trajectory of the path (for a description of B-spline curves, consult [42] or 56 Chapter 3 of this thesis). The effort is defined as the integral of torque squared over time, incorporating the amount of torque required by the robot and the time that the motion takes to complete the motion. Martin and Bobrow present an iterative procedure to obtain analytic gradients of the effort function with respect to the control points, and use these gradients to search for locally optimal solutions. Quasi-Newton algorithms can be used to find optimal solutions. The authors stress the fact that the problems are often numerically ill-conditioned and thus finite different gradients lead to poor convergence, hence the need for analytical gradients. A simple example of an optimal trajectory found for a two-link planar chain is shown in Figure 2.20 and Figure 2.21. This motion is occurring in a gravitational field. Figure 2.20. Initial path, 2-link manipulator [37] Figure 2.21. Optimal solution, 2-link manipulator (working against gravity) [37]. The minimum effort optimization presented in [41] is only for open-loop serial manipulators; however, the work is expanded on to cover closed-loop manipulators in [43]. In order to compute minimum-effort joint trajectories for closed-loop mechanisms, a procedure is developed that reduces the closed-loop 57 system to an equivalent open-loop system and then maps the solution back to the closed-loop system. Exactly and redundantly actuated chains are considered. Discussion and Evaluation Effort-based optimization using B-spline curves has been presented by several researchers, and has been shown to be a good means of generating robot joint trajectories. In this work, effort-based optimization is used to evaluate and optimize the performance of a locomotion gait for a snake-like robot. The methods presented in this section are drawn on to develop a model for optimization of the rectilinear locomotion gait. 2.7 Summary The prior work that is relevant to this thesis covers several different areas from biology to mechanical design, and such was divided into five different areas of discussion. Each is important to this thesis in separate ways. First, snake locomotion was discussed, as it is the inspiration for this work. Several snake-inspired robots that have been previously developed were discussed, and from an evaluation of them desirable and negative attributes of these robots were discussed. From an evaluation of prior designs, the lessons learned can be incorporated into the design developed in this thesis. The work in this thesis seeks to build on and improve the modularity of previous designs, as well as develop a design with lower manufacturing costs. The third and fourth portions of the related work discussed the state of the art in characterization of snake-inspired robot locomotion and gaits. Earlier 58 implementation of rectilinear gaits was reviewed, and a gait was identified that is further modified and enhanced in this work. A detailed kinematic and dynamic formulation will be developed in this thesis. Finally, robot trajectory optimization approaches were discussed because this work applies a similar approach to design a gait for snake-inspired robots. This will result in a highly-parameterizable formulation for optimized gaits. 59 Chapter 3 - Gait Development and Analysis 3.1 Introduction In order to generate and analyze motion and performance for the snake-inspired robot, both a framework for analysis and a gait are required. The definition of a gait as it relates to a snake-inspired robot is a set of joint trajectories that are repeated to generate a forward motion in the robot. In order to generate a gait, the relevant parameters must first be defined, an approach that results in forward motion developed, and then the equations that can be used to describe the performance of the gait developed. Because of the heuristic-based and optimization-based approaches to gait design that are used in this thesis, performance information (fitness) must be generated in order to develop the gait in a feedback-like nature. A means of parameterizing trajectories so that that they may be optimized is also presented. In this thesis, a framework for optimizing joint trajectories is presented, and a separate, simpler, heuristic-based approach to obtain joint trajectories with improved performance is demonstrated. A representation of the gait design process is shown in Figure 3.1. The relevant parameters of the gait and the physical design are identified as the gait angle, step time, length, and mass. Control points are used to determine the exact path of the trajectory, and all of this information is used in the dynamic model to obtain a torque signature. This torque signature can then be used to generate the effort. 60 Figure 3.1. Representation of gait analysis and development procedure. 3.2 Background Prior to developing the specifics of the snake-inspired robot gait, several elements of background material must be discussed. In order to describe and analyze the motion of a snake-inspired robot, basic robot representation must be discussed, and a basic description of robot link trajectories is presented. Furthermore, since B-spline curves are utilized to describe and specify the trajectories of joint motion, a description of B- spline curves is presented. 3.2.1 Basic Robotics A basic description of robot kinematics and dynamics can be found in [44]. The trunk of the robot can be thought of as a robotic manipulator with a certain number of joints and links. Each link contains its own Euclidean coordinate system or frame, and the orientation between links can be described using a rotation matrix between the coordinate systems. Figure 3.2 shows link frames {A} and {B} relative to each Gait Parameters: Gait Angle Step Time Physical Parameters: Link Length Link Mass Joint Trajectory Torque Profile Effort Control Points 61 other. Since 2-D planar motion is only considered in the case of the rectilinear gait, the orientation of frame B can be represented with respect to frame A using the rotation matrix denoted as follows, with the X and Y directions labeled, and both coordinate systems are standard right-handed coordinate systems: ? ? ? ? ? ? ? ? ? ? ? = 100 0cossin 0sincos ?? ?? RAB (3.1) Figure 3.2. .Basic robot link representation. A complete transformation, however, consists of both a rotation and a translation. In order to perform both simultaneously the homogenous transform is introduced. The homogeneous transform takes the form of: (3.2) With BAP being the vector from the origin of {A} to the origin of {B}. {A} {B} ?B YA XA YB XB 62 Using the transformation and rotation matrices, the position of any robot link can be described with respect to any other robot link if the angles of the joints in between them are known. The kinematics and dynamics of the snake-inspired robot are developed using these transformations and several assumptions. Any robot comprised of multiple linkages can be described as a kinematic chain. A kinematic chain is defined as any assembly of links that are connected by joints [45]. Kinematic chains can be divided into two major classes: Open-loop chains and closed-loop chains. Open-loop chains are kinematic chains whereby each link is connected to each other link by only one path. Closed-loop chains, on the other hand, are chains whereby links can be connected to each other by multiple paths. A snake-inspired robot with a vertical undulation is a unique case where the mechanism can take on the properties of either a closed-loop or an open-loop chain, depending on the topology of the mechanism, as shown in Figure 3.3. The multiple points of ground contact act as either a prismatic link (in the case of dynamic friction), or simply a rigid link (in the case of no slipping) in the closed loop case. Thus, both closed- and open-loop robot analyses must be addressed. Figure 3.3. Closed-loop (left) and open-loop (right) configurations of a snake-inspired robot. Acts as a friction- opposed prismatic joint when slipping occurs 2-link serial chain 63 As others have mentioned in numerous works [25] [26], the configuration of the snake-inspired robot can be divided into two distinct sets of variables: shape and position (orientation). In the distinct case where the snake is only moving in a vertical 2-D plane, the orientation of the snake is determined by its shape, as there is typically one stable orientation for each shape (the assumption is that it remains in a stable orientation). Therefore, the motion of the snake-inspired robot can be described as a function of joint angles, provided that the friction is sufficient for locomotion. 3.2.2 Joint Trajectories In order to specify how to physically execute the gait, joint trajectories must be developed that specify how the joints are moved between positions with respect to time. Because a snake-inspired robot does not contain wheels, it must rely on a net change in body shape to achieve a forward motion. In order to achieve this change in shape, the complete time histories of angular acceleration, velocity, and position of each joint will be specified to achieve the appropriate configurations for forward motion. These complete time histories are called the ?joint trajectories?. Joint trajectories specify the motion parameters in what is known as the ?joint space?. The mapping between Cartesian space and the joint space is discussed in [44]. Since the mechanisms considered in this work are closed mechanisms, there are more joints than free variables, thus, the trajectories can be freely specified for a number of joints, while the trajectories for the other joints must be calculated from the geometric constraints using inverse kinematics. There are bounding constraints, 64 however, on the free joints, so that the mechanism may remain in a feasible configuration. This will be elaborated on later. 3.2.3 Exact vs. Redundant Actuation Since snake-inspired robots often take on closed-loop configurations, it must be acknowledged that there are multiple solutions for the actuation of closed-loop mechanisms. In the case of a closed kinematic chain, the mechanism will have less degrees-of-freedom than joints. In this situation, one can use an exact or a redundant actuation strategy. In an exact actuation strategy, a select number of the joints are allowed to be passive. The number of active joints is selected such that there are the same number of active joints are there are degrees-of-freedom. In this case, there is a unique solution to the problem of inverse dynamics. In a redundant actuation strategy, the number of actuated joints is greater than the degrees-of-freedom, thus there is not a unique solution to the inverse dynamic problem. Typically an optimization or other framework would be used to determine the inverse dynamics in this case. In this framework, an exact actuation strategy is used. The rationale is that the gait design already requires several feedback loops for the heuristic-based search, and requiring another one to solve the redundant actuation problem would further complicate the gait design problem. 65 3.2.4 B-Spline Functions For the generation of the free joint trajectories, it is assumed that the time history of the joint parameters follows that described by a B-spline curve. B-splines are a class of curve that originated in geometric modeling, and are popular in the geometric modeling community due to their versatility and their unique properties [42]. B-splines are composite curves composed of Bezier curves that are pieced together (For those not familiar with Bezier curves, consult [42]). B-spline curves are defined by a vector known as a knot vector and a series of control points. Changing the locations of the control points and the knot vectors changes the geometry of the curve. It is important to note, that unlike Bezier curves, the degree of a B-spline curve is not determined directly by the number of control points. This is a key advantage of B-spline curves, as complex curves can be modeled without the use of large polynomials. B-spline curves also have the advantage that the control points locally control the curve, but do not have large global effects on the curve. Thus, changing one control point does not have an effect on segments of the curve that are far away from it, which can occur with Bezier curves. Finally, B-spline curves have what is known as the convex hull property, meaning that the curve is fully contained within the convex hull of the control points. This is important in trajectory generation, as the control points defined in the trajectory generation will bound the values of the trajectory (i.e., ],0[)( fuupup ??? ). The basic structure of a B-spline curve is represented as a compilation of a set of basis functions as follows: 66 ? = = n i kii uNpup 0 , )()( (3.3) ip denotes the control points, and N denotes the basis functions. The basis functions are recursively defined as: 1)(1, =uNi if 1+?? ii tut (3.4) 0= otherwise 1 1,1 1 1, , )()()()()( ++ ?++ ?+ ? ? ?+ ? ?= iki kiki iki kii ki tt uNut tt uNtuuN (3.5) The parameter k controls the degree of the curve, which is (k-1). The parameter n designates the number of control points. The degree and number of control points are related to the knot vector by the following relationship, with T being the number of ?knots? (or length of the knot vector): Tkn =++ 1 (3.6) B-spline curves do not necessarily interpolate the beginning end control points, but can be allowed to if non-uniform knots are used. In this case, repeated knots are desirable because the joint angles at the beginning and the end of the time step should be directly specified. In selecting the B-spline parameters for trajectories, a cubic B-spline with 5 control points was chosen. In addition, the mechanisms should begin and end at rest, 67 thus the derivative of each curve endpoint should be zero. As mentioned before, the curve should interpolate the end points as well. For the interior knots, an even spacing is used. The parameterization of the curve was chosen to be from 0 to 1, meaning that each time step should take 1 second to complete. The formulation is as follows, note that there are 5 distinct control points, and the two exterior control points are repeated to achieve the desired boundary condition. T = [0 0 0 0 0.25 0.5 0.75 1 1 1 1] (3.7) P =[?i ?i C1 C2 C3 ?f ?f] (3.8) The parameters ?i and ?f are the beginning and end angles of the interval, which are always 0, ?, or -?. The interior control points, designated as ?C? are the free variables. An important note on B-spline curves that is relevant to the problem of bio- inspired design is that recent studies in neuroscience have shown that trajectories of movements in humans closely resemble B-spline curves. A recent study has shown that when asked to move their hands in a circular motion, the actual achieve motion is best described using ?bell-shaped? B-spline basis functions [41]. 3.3 Gait Overview and Rationale At this point, a description of the class of gait that will be used to achieve locomotion in the snake-inspired robot is presented. The framework will then be developed to 68 parametrically optimize this gait to improve performance. The class of gait is inspired by rectilinear locomotion in real snakes. This gait was selected because of its advantages over other classes of gaits, such as concertina and serpentine locomotion. The general strategy for achieving this gait is then broken down into a series of configurations that the robot must transition through in order to move its body mass forward. In rectilinear motion in real snakes, sections of the snake expand and contract in order to propel the snake forward. This motion is achieved by muscles pulling and pushing the ribs closer and further apart. In order to achieve a similar effect in an artificial snake, which is more rigid and has less degrees-of-freedom, vertical motion is used. When the snake bends in the upward direction, the lateral component of the segment distance shrinks. The shorter segment is then propagated from the rear of the snake, moving the snake forward. Biological snakes use slight lifting and careful body positioning to shift weight and allow segments to slide. In this approach, the segments off the ground are simply lifted to allow forward motion. Work by [30], however, has shown that it is possible to shift weight (and thus frictional force) around a robot to allow sliding of desired segments, and this is something that could be considered for snake-inspired robot locomotion in the future. 3.3.1 Drawbacks of a Serpentine Gait The majority of work to date on serpentine gaits in snake-inspired robots has been in the area of mathematical exercises and demonstration purposes. Since serpentine locomotion relies heavily on anisotropic friction, most of the realization of serpentine 69 locomotion has been achieved with passive wheels on the ventral surface of each robot link. These wheels allow for slipping in the tangential direction, but prohibit slipping in the normal direction. Other implementations, such as the work by Saito et al. [26], have used a similar idea, using large ridges on the ventral surfaces of the bottom of the robot to achieve anisotropic friction on a surface such as carpet. Both concepts are feasible in the laboratory, but are heavily dependent on specific surface characteristics. In the field, there is a good possibility that a snake- inspired robot will encounter terrain that is too coarse for small wheels to have an effect. In addition, because serpentine gaits are reliant on dynamic frictional characteristics of the surface, it is difficult to predict or ensure satisfactory performance of the robot on surfaces that are not fully described a priori. Finally, further work needs to be done with the design of the ventral surface of snake-inspired robots to achieve frictional characteristics similar to biological snakes. Furthermore, as mentioned by [3], serpentine locomotion requires careful control. Snakes actively control the trajectory of their curves to push against obstacles in their path. This requires sophisticated feedback control that is difficult to achieve in an artificial snake. In addition to using obstacles to push off, snakes using serpentine locomotion are constantly adjusting their weight and muscular force against the ground to control their frictional characteristics. Finally, a primary application of snake-inspired robots is to be able to fit through tight spaces. As has already been discussed in the section about snake- inspired robot locomotion, biological snakes typically switch to concertina or rectilinear locomotion when they need to fit through tight spaces. This is because 70 serpentine locomotion typically requires a larger cross section (when looking forward) than other forms of locomotion. Biological snakes often make a conscious switch from rectilinear to (typically) concertina locomotion when presented with the challenge of fitting through a tight space. This would be another issue that would require sophisticated programming and control in artificial snake-inspired robots. 3.3.2 Advantages of a Rectilinear Gait Gaits inspired by rectilinear locomotion have been successful in the laboratory, and have been demonstrated to traverse more difficult terrain and through tighter spaces (i.e. pipes) [33]. The primary benefits to a rectilinear gait are that it is easy to control and implement, and because it relies primarily on static friction, as long as the surface provides a reasonable degree of static friction with the ventral surface of the robot, the gait should be possible to implement. Since the rectilinear gait relies on a regular pattern of muscular contraction, it should be easier to control and implement than a serpentine gait. Vertical waves of bending passed along the axis of the snake-inspired robot are all that would be required to achieve forward movement. This, of course, is only true provided that there is sufficient traction between the ventral surface and the ground. This, however, should not be much of a complication if the bottom surface of the robot is comprised of a high-friction material such as rubber. Conversely, with a gait such as a serpentine gait, this type of material would prohibit forward motion, because the rectilinear gait relies on dynamic friction to move itself forward. In a rectilinear gait, the snake exerts more pressure on the static points, slightly lifting the moving points 71 and allowing them to move forward. This would be a feasible strategy with most frictional surfaces in snake-inspired robots, provided that there is enough lifting of the moving points. Typically, the approach used by robot designers (and our approach) is to completely lift the portion of the snake that is moving forward. Using this strategy, forward motion can be achieved with a high coefficient of friction between the snake and the ground. This means that snake locomotion will be feasible on a wide range of surfaces. Another possible advantage of the rectilinear gait is, because there is minimal slipping of the surface on the ground, there is not a lot of energy lost due to friction. On first glance, this would appear to be a major advantage over serpentine locomotion, however, the energy gains are largely offset due to the fact that the body of the snake does a significant amount of work to lift the trunk above the ground to avoid the friction. This is a tradeoff that has been slightly investigated in biology, but still must be investigated in snake-inspired robots. 3.3.3 Gait Sequence The rectilinear gait studied here relies on lifting in the vertical direction to advance segments of the snake forward, using friction. Gaits that use this similar vertical motion have been implemented and shown to be successful by several groups [33]. The gait that has been chosen for this study is based on the gait presented by Merino and Tosunoglu [34]. The authors presented a sequence of joint configurations that should result in a forward motion if the robot is driven through them. This sequence is shown in Figure 3.4. 72 Figure 3.4. Gait presented by Merino and Tosunoglu [34]. This gait illustrates that if a vertical wave is passed through the robot, the result will be an advancement that is proportional to the gait angle ? (labeled in Figure 3.4). This advancement is computed as: )cos(22 ??= lx (3.9) ? Advancement 73 The average velocity of the robot can then be determined by dividing the advancement by the cycle time. A gait inspired by this sequence has been chosen to propel the 6-link robot described in this thesis. Additionally, it can be seen that steps 1-3 in Figure 3.4 can be merged into one step to simplify the motion and prevent any unnecessary joint motions. For a full description of Merino and Tosunoglu?s work, consult Section 2.5. This rectilinear (or traveling wave) gait is difficult to analyze kinematically and dynamically because the topology of the mechanism changes during the course of the motion. This means that the ground contact is constantly changing, altering the points at which external reaction forces are applied. Figure 3.5 shows the different topologies of the mechanism during the course of the gait cycle. Mechanism 1, or M1, is the first part of the gait sequence and it is considered an open-loop mechanism, considering that the moving joints are free to move from the first position to the last position without a reaction force, provided that the joints remain in the feasible joint space (above the horizontal). Mechanisms M2 and M3, however, have reaction forces that are applied on different ends of the moving joints. Thus, they needed to be treated differently as far as the kinematics and dynamics are concerned. 74 Figure 3.5. Modified traveling wave gait, steps and mechanisms are identified. Locomotion from this gait will be achieved by driving the appropriate joints through desired trajectories. The trajectories will be specified using the B-spline curves that are presented in Section 3.2.4. The parameters (control points) of the B- spline curves can be selected heuristically and then tested to verify that the gait is feasibly. However, a search-based approach is preferred, where a search is conducted to find control points that optimize the performance of the locomotion gait. 3.4 Kinematics and Dynamics Model This section presents a formulation of both the kinematics and dynamics of the model. This is necessary because a dynamics model must be created in order to M1 M2 M3 M2 M1 Steps 1 2 3 4 5 Motion Direction 75 determine the amount of torque required to actuate the robot. More importantly, the dynamics model can be used to evaluate metrics that determine the performance of the robot. The value in the kinematics model is that it is both necessary to develop the dynamics model, and also can be used to verify the feasibility of the gait. In Section 3.3.3, the gait was divided into mechanisms with different topologies. In this section, the kinematics and dynamics model is constructed for each mechanism. The example of M1 is used to show how the kinematics and dynamics models are developed, and then it is shown how this approach can be expanded and applied to M2. Finally, it is shown how the solutions to the steps and mechanisms can be mapped back to the overall mechanism to achieve one set of global solutions. 3.4.1 Gait Kinematics Consider the first mechanism in the locomotion gait, M1, shown in Figure 3.6. The links of the snake-inspired robot must move from the flat shape shown in the first figure to the lifted shape shown in the second part of the figure. This motion can be described by three parameters in the joint space: the angular positions of joints 1, 2, and 3. It can also be seen that the feasible joint space is constrained to a region that amounts to a half-space due to the presence of the ground. Since the constraint amounts to an inequality constraint, it may or may not be active depending on the joint space configuration of the mechanism. This complicates matters, because the dynamics are different for the case where the 76 constraint is active and the case where the constraint is not active. This issue is solved by posing the move as two different problems and then comparing the results. Figure 3.6. The first gait step. The first way to model the sub-problem is to treat it as a free three-link system with three degrees of freedom. This system is shown in Figure 3.7. In this case, both the kinematic and dynamic parameters can be computed using the recursive Newton- Euler method that is presented in Craig [44] (Equations 3.10-3.18). In order to ensure that the configuration remains in the feasible joint space, the y-positions of each of the joints and the ?tip? of the third link are calculated. If the position of either of the joints is equal to or less than zero, a penalty function is assessed in the fitness function (Section 3.5.3). 1 2 3 1 2 3 77 Figure 3.7. Representation of the first mechanism as a open-loop, planar, kinematic chain. The iterative Newton-Euler scheme propagates the kinematics from the base of the manipulator to the tip, and then propagates the dynamics from the tip back to the base. The outward iterations compute the inertia of each link, and then it is assumed that the forces that achieve this inertia originate at the base. In order to account for gravity, a vertical acceleration is assigned to the base reference frame. In the notation used, the preceding superscript denotes the reference frame in which the value is computed with respect to, and the following subscript denotes the entity that the property relates to. In other words, 1?1 denotes the angular velocity of link 1 with respect to reference frame 1. The dots indicate the derivatives of the values with respect to time, R denotes a rotation matrix, iPi+1 denotes the vector from the origin of coordinate system ?i? to the coordinate system ?i+1?, and finally, ? denotes torque. Joint 1 Joint 2 Joint 3 Link 1 Link 2 Link 3 78 Newton Euler Kinematics and Dynamics Formulation [44]: Outward Iterations i: 0 ? 5 1 11 1 1 ? + ++? + + += i ii i i i i Z??? (3.10) 1 11 1 111 1 ?? + ++?? + ++??+? + +?+= iiiiiiiii i i i ZZ ????? (3.11) ( ) ?? ? ? ??? ? +??+?= ? ++ ?+ + ?+ i i i i i i i i i ii i i ii i vPPRv 1111 1 ??? (3.12) ( ) 11111111111 111 + ?++ + + + +++? +?+ +??+?= +++ i i C i i i i i C ii i C i vPPv iii ??? (3.13) 1 1 11 1 + ?+ ++ + = iC i ii i vmF (3.14) 1 1 11 11 1 11 1 11 + + ++ ++? + ++ + ++ ?+= i i i C i ii i i C i i IIN ii ??? (3.15) Inward Iterations i: 6 ? 1 i i i ii ii i FfRf += + + + 1 1 1 (3.16) 1 1 111 1 1 + + +++ + ?+?++= + i ii ii i i i C i i i i i i i fRPFPnNn i (3.17) 79 i iT i i i Zn ?=? (3.18) Ci denotes the centroid of the ith link. The second means of modeling the sub-problem is to assume that the ?tip? of the third link remains in constant contact with the ground during the motion. In this instance, the problem can be modeled as a kinematic chain with four rotating joints and a slider mechanism that is shown in Figure 3.8. In this case, the geometric relations involve an equality constraint, as the y-position of the ?tip? of link 3 always remains at y=0. Figure 3.8. Representation of the first mechanism as a closed-loop, planar, kinematic chain. Joint 1 Joint 2 Joint 3 Link 1 Link 2 Link 3 80 In this case, the kinematic configuration of the mechanism is governed by a constraint relationship. The mechanism is converted from one with three-degrees of freedom to one with two degrees of freedom. In this system, the angles of joints 1 and 2 are treated as free variables, and the position of joint 3 is calculated using the following constraint relation: 0)sin()sin(sin 321211 =+++++ ?????? (3.19) The parameter ? can be introduced to simplify the notation: ? = = i j ji 1 ?? (3.20) The equation then reduces to: 0sinsinsin 321 =++ ??? (3.21) The angle of link 3 can then be calculated by the solving the equation to yield: )sinsin(sin 2113 ??? ??= ? (3.22) with: 2133 ???? ??= (3.23) 81 The only constraints on the angles of joints 1 and 2 are that they must satisfy the aforementioned criteria of not resulting in any Cartesian positions below y=0, and that: ( ) 1sinsin 21 ?+ ?? (3.24) These constraints define the feasible design space of the problem. Like the previous constraint criteria, a penalty is assessed in the fitness formulation if this constraint is not met. Both the angular velocity and acceleration of the third link can be computed using the same constraint relationship. The constraint equation can be implicitly differentiated once to yield the angular velocity, and twice to yield the angular acceleration as follows: 0coscoscos 332211 =++ ??? ?????? (3.25) and 0sincossincossincos 3 2 3332 2 2221 2 111 =?+?+? ????????? ???????????? (3.26) Solving for the angular velocity of link 3 yields: 82 ?????? +?= ??? 2211 3 3 coscoscos 1 ???? ?? (3.27) with: 2133 ???? ??= ???? (3.28) Solving for the angular acceleration of link 3 yields: ??? ? ??? ? ??+??= ????????? 3 2 32 2 2221 2 111 3 3 sinsincossincoscos 1 ?????????? ?? (3.29) with: 2133 ???????? ??= ???? (3.30) It should be noted that this forumulation of the jacobian can result in singularities at ?3=pi/2. However, the joint trajectories that are used in this work do not approach this singularity. The complete kinematic description of each links parameters can then be developed by the outward iteration scheme presented as equations 3.10-3.15. It is important to note that the link velocity must also be calculated, it is given by: )( 1111 ++++ ?+= iiiiiii iii PvRv ? (3.31) 83 The accelerations must then be mapped back to the nonmoving base coordinate system by pre-multiplying by the appropriate transformation matrices, for example: 3 3 2 3 1 2 0 13 0 ?? = vRRRv (3.32) This is done in order to develop the equations for the inverse dynamics of the system. 3.4.2 Dynamics The dynamic problem of the gait design involves computing which torque values are needed to achieve the desired joint motion. The dynamics have already been developed for the case of the open-loop configuration, as they only involve simple inward-outward propagation. This formulation depends on the manipulator moving in free space, and the reader can consult [44] for a full derivation of the algorithm. For the case of the second representation, the dynamics must be treated differently than that of a serial manipulator due to the fact that reaction forces arise at the ?tip? of the final link. The Newton-Euler equations are still used to develop the dynamics, but the simple iterative method cannot be applied. In order to apply the Newton-Euler equations to the closed-loop case, the forces and the moments are simply summed about each link. Since there is a frictional force that acts on the ?tip? of the third link, a Coulomb friction model represents this force. This means that the force can be calculated using the equation: 84 )( 30 tipRfr vsignFF ??= (3.33) The term 0v3tip denotes the velocity of the ?tip? of the third link, and FR is the vertical reaction force between the ground and the link. The ?sign? denotes the signum function, meaning that the frictional force is always acting in a direction opposite to the velocity of the link. It is of note that an Eulerian framework is used to develop the dynamics for this problem because of the friction term. When forces are directly computed, frictional forces can be accounted for. Figure 3.9 shows the free body diagrams for mechanism M1 in the closed loop configuration. The mechanism consists of three bodies, both enacting forces on each other, and on the external environment. The entire mechanism is contained in a plane, so there are only three degrees of freedom for each body: Translation in the x and y directions, and a rotation about the z-axis. The Newton and Euler equations are applied as follows: ? ?= vmF (3.34) and ? ?= ?IM (3.35) This results in three equations for each body. For example, the equations for link 1 are: 85 xxx vmFF 11201 ? =? (3.36) yyy vmFF 11201 ? =? (3.37) 111210111210121 cos2cos2sin2sin2 ? =??++? ??????? IFlFlFlFl yyxx (3.38) With ?I? being the moment of inertia of the link about the centroid, and ?l? being the link length. The equations can be generalized for any link (with the exception of the final link) as: ixxiiixi vmFF ? +? =? )1()1( (3.39) iyyiiiyi vmFF ? +? =? )1()1( (3.40) iiyiiiyiixiiiixiii IF lFlFlFl ? +?+?+ =??++? ??????? cos2cos2sin2sin2 )1(1)1()1()1(1 (3.41) 86 The generalized equations for the final link are (with i=3 in this case): ixfrixi vmFF ? ? =+)1( (3.42) iyRiyi vmFF ? ? =+)1( (3.43) iifriRiixiiiyi IF lFlFlFl ? ?? =?++? ????? sin2cos2sin2cos2 )1()1( (3.44) 87 Figure 3.9. Free body diagrams for the links in M1. F01y F01x F12y F12x ?1 F12y F12x F23y F23x ?2 ?1 ?2 ?2 F23y F23x ?3 FR 1 2 3 F fr centroid 88 In the case of M1 there are exactly 9 unique terms and 9 equations. The entire system of equations can be reduced to one matrix equation, which can then be inverted to solve for each unknown term. The resultant matrices and vectors are: ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? +? ? ?? ? ? ??? ? ? = 00sin)(2cos2cos2sin2 001100000 00)(010000 100cos2sin2cos2sin200 000101000 000010100 11000cos2sin2cos2sin2 000001010 000000101 3 0 333 0 2222 1111 ????? ? ???? ???? tip tip vsignllll vsign llll llll A (3.45) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 2 1 23 23 12 12 01 01 ? ? R y x y x y x a F F F F F F F F (3.46) and ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? 3 3 3 2 2 2 1 1 1 ? ? ? I vm vm I vm vm I vm vm F y x y x y x i (3.47) The applied force vector Fa is solved for by inverting A as follows: ia FAF 1?= (3.48) The values Fa(8) and Fa(9) give ?1 and ?2 respectively. The matrix problem is solved at each discrete time step of the sampling to obtain the needed values. 89 In the case of the first mechanism (M1) both the open-loop and closed-loop solutions are possible. In the heuristic-based framework which is used in this thesis, each model will be tested, and the solution that gives the best results will be used as the actuation strategy. 3.4.3 Mechanism 2 (M2) The second step of the locomotion gait involves another configuration change. The Figure 3.10 shows the second step of the locomotion gait. The topology of this mechanism is different than that of the mechanism in the first step (M1) as it involves four links that must change position instead of three. Further, it can be assumed that it is not possible to have an open-loop solution because of stability reasons. (In addition, testing the first mechanisms open-loop solution showed it to be inferior to the closed-loop solution, so it can be assumed that a solution that would involve lifting four links completely off of the ground would be even less desirable). 90 Figure 3.10. Gait step 2, which is modeled with mechanism 2 (M2). The mechanism M2 is modeled similarly to the closed-loop model of M1 with the difference being that M2 has an extra link. This means that this mechanism has exactly three degrees-of-freedom. As seen in Figure 3.10, the link marked as ?1? is the first non-moving link, and thus can be assumed to be the ground link. Like the analysis of M1, the assumption that the base link does not move can be tested once the total force vector is calculated. The rigid body model of the mechanism is shown in Figure 3.11, and the analysis is conducted in the same means as the closed-loop analysis of M1. 1 2 3 4 5 1 2 3 4 5 91 Figure 3.11. Model of M2. The geometric constraint of this mechanism can be described using the following equation, with the same parameters as the previous sub-problem: 0sinsinsinsin 4321 =+++ ???? (3.49) The kinematics of the mechanism can be developed in the same way that they were for M1 by solving and differentiating the constraint relation. In this case ?1, ?2, and ?3 are allowed to be free variables and ?4 is the constrained variable. Again, in the case of the dynamics, the joints that are kinematically free are the driven joints and the fixed joint is free to rotate. Similarly, the dynamics of M2 can be developed using the exact same method as the dynamics were developed for M1. The complete formulation can be found in Appendix A. The solution for this mechanism involves inverting a 12 X 12 matrix, and the torque values are obtained. Joint 1 Joint 2 Joint 3 Link 1 Link 2 Link 3 Link 4 Joint 4 92 3.4.4 Mechanism 3 (M3) The third step of the locomotion gait involves the configuration change shown in Figure 3.12. The topology of this mechanism is different than that of M2 because the entire final link 6 in Figure 3.12 slides on the ground, as opposed to just the tip of a link. This means that there are actually five links that are assumed to be moving with respect to the base link instead of four. However, it can be seen that the degrees-of- freedom, the locomotion and the constraint equations are exactly the same as for M2. It can be seen that an additional angle parameter arises because of the 5th joint, however, this is related to the other parameters by ?5 = -?4 (3.50) (Appendix A discusses this in more detail). It is also important to note that in this case, it cannot be intuitively concluded that the link that is assumed to be the ground link does not move relative to the ground. The dynamics of M3 are similar to those of M2. However, the difference is that because an entire link is sliding on the ground for M3, the slider mechanism shown in Figure 3.11 is assumed to have mass, and thus inertia. This results in a 14 X 14 matrix that must be inverted at each time step of the discrete sampling. The equations for the model of mechanism M3 are presented in Appendix A. A noteworthy difference between M3 and the other mechanism should be made with concern to the base link. In the case of the other mechanisms, it can be seen how the two or three non-moving links act as an anchor for the rest of the motion. However, with M3, this is not the case. From Figure 3.12 it can be inferred that there are times when the moving links are bounded by one link that is on the 93 ground in both cases. For the formulation, it was assumed that one is moving and one is not. Using the exact actuation strategy presented in this section, simulation was conducted on M3, and the results show that the downward reaction forces on the side of the mechanism with the actuated links were larger than those on the non-actuated side. This would imply that the frictional force is greater on that link, and thus the assumption that the link does not slip would be correct. This simulation was only conducted with an exact actuation strategy, and with the gait found in Section 3.5.3. Future work should include a deeper analysis of this issue. Figure 3.12. Gait step 3, which can be modeled with mechanism 3 (M3). 3.4.5 Steps 4 and 5 Upon looking back at Figure 3.5, it can be seen that symmetry about M3 can be exploited. Thus, steps 4 and 5 use mechanisms M2 and M1, respectively, with reversed coordinate systems and opposite trajectory directions. In this case, the 1 1 2 2 3 3 4 4 5 5 6 6 94 equations do not need to be derived again. The solutions can be obtained using the framework of M1 and M2. 3.4.6 Mapping Solutions Now that the entire gait problem has been broken up into sub-problems and solutions are found, the problem needs to be re-compiled into a global solution. In other words, for each mechanism, the joints and links have been labeled for that step. The joints in the overall robot are labeled as well. The solutions for each sub-problem must be ?mapped? back to the appropriate joints for the entire problem. In order to map the solutions, a simple matrix multiplier scheme is used. The solutions for the step sub- problem can be multiplied by a matrix to map them to the global coordinates of the joints using the matrix ?Sn?, with ?n? being the number of the step. localnglobal S ?? = (3.51) Step 1: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3 2 1 5 4 3 2 1 100 010 001 000 000 ? ? ? ? ? ? ? ? (3.52) 95 Step 2: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 4 3 2 1 5 4 3 2 1 1000 0100 0010 0001 0000 ? ? ? ? ? ? ? ? ? (3.53) Step 3 is simply a 5 X 5 identity matrix. Step 4: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 4 3 2 1 5 4 3 2 1 0000 0001 0010 0100 1000 ? ? ? ? ? ? ? ? ? (3.54) Step 5: ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3 2 1 5 4 3 2 1 000 000 001 010 100 ? ? ? ? ? ? ? ? (3.55) Similarly, the torque solutions can be mapped using the same matrix: localnglobal S ?? = (3.56) After the solutions for the sub-problem are mapped to their global coordinates, the solutions can be pieced together in the order of the steps to obtain the time-histories of the joint angles and joint torques for the entire step of the gait. 96 Note about singularities and the joint space It should be noted that the developed model assumes rigid body kinematics and dynamics only. This means that the model does not allow for the link lengths to vary, or for the links to deform. This is important to note, because in problems of complex manipulator kinematics and dynamics such as this one, there can be a limited feasible workspace and singularities can arise. If the joints are allowed to slightly bend or extend, many of the configurations that are infeasible or singular in the rigid-body model can actually be physically realizable. This is important to note in a case like this, because it means that there may be gaits that are feasible in practice but are not feasible in the rigid body model. 3.5 Trajectory Generation With the kinematic and dynamic model completed, this information can now be used to generate trajectories with desired characteristics. In this section, the kinematics and dynamics model is used to generate a metric called ?effort?. With the effort metric, a method to generate optimal joint trajectories that minimize effort can then be constructed. In this section, the problem is first formulated and a strategy to arrive at an optimal solution is proposed. A simpler heuristic-based framework that was used to generate trajectories is then presented and several of those trajectories are presented. 97 3.5.1 B-Spline Trajectory Formulation As was mentioned in Section 3.2.4, the core of the solution to the trajectory generation problem lies in the representation of the joint trajectories. In this work, the joint trajectories are represented using B-spline curves that are parameterized by a set number of control points. The B-spline representation consists of basis functions that are weighted using control points. The order of the curve and the location of the control points define the curve. By using B-splines to represent the joint trajectories, the joint trajectory can be represented using a collection of parameters. This converts the problem of trajectory optimization from an optimal control problem to a standard parametric optimization problem that can be solved using a search-based approach. 3.5.2 Trajectory Optimization In this work, a search-based optimization strategy is developed. This entails using an initial guess of the parameters that define the trajectories, and modifying them to find a better solution. The aim of this approach is to find a locally-optimal solution. A local search strategy involves determining which direction to change the parameters to achieve a decrease in the objective function, in our case, the effort. This movement must remain within the constraints of the problem. The objective function that is minimized in the development of this gait is known as effort. Effort is a standard metric that is used in robot optimization because it incorporates both the time that the action takes, and the amount of torque required by the joints. It is important to note that it is a better metric to use than mechanical work, because mechanical work only measures the amount of work that is done on 98 the object. Mechanical work does not consider the fact that when a static torque is applied using a motor, the motor consumes energy just to resist the torque, even if it is not moving the load. The effort metric is formulated as: ?= ft dtJ 0 2 2 1)( ?? (3.57) The overall optimization problem for a minimum effort trajectory-generation problem can be formulated as the following [41]: minimize ))(()( ?= ?? fJ (3.58) subject to ?=+ ??? ),()( qqhqqM (3.59) qtqq ?? )( (3.60) 0)0( qq = , 0)0( = ? q (3.61) ff qtq =)( , 0)( = ? ftq (3.62) The variable ?q? is used to denote the vector of joint positions in this case, with the Equations 3.60-3.62 specifying bounds and boundary conditions on this variable. These equations are satisfied in the construction of the B-splines, because the boundary control points are fixed. In this case, ?q? is replaced with ???. Equation 3.59 is a general equation known as the ?state-space? equation; it expresses the torque as a function of shape and dynamic values. In this situation, it is used to 99 designate the sub-problem of computing the joint torques which has already been developed. In order to generate optimal joint trajectories at each step of the locomotion gait, a gradient-based search algorithm, similar to that shown in [41] and [43] is proposed. A gradient-based search is possible, because the joint trajectories are specified as B-spline functions, as described in Section 3.2.4. This means that the trajectory of each joint angle is only a function of a set of control points and time. A similar strategy to that in [41] can be used to search for locally-optimal trajectories from initial guesses. Gradient-based searches begin with an initial guess, and work by iteratively updating the parameter values until a local optima is found, as determined using a convergence criterion. Updating the parameter value vector ?x? is accomplished using the following equation: )( )()()()1( kkkk xsxx ?+=+ (3.63) The value x(k) is the current guess of the optima in the parameter space, and x(k+1) is the updated value. In order to move from the current value to the next value, the step size ??? and the search direction ?s? are required. The search direction is constructed using the gradient of the objective function. The step size is typically obtained by finding a value of ??? that minimizes the objective function. This is accomplished using a ?line search?, meaning that a single variable optimization problem must be solved. A pre-determined step size can also be used. 100 The major task remaining in order to compute the updated parameter values is the generation of the search direction. The majority of the differences between different search methods lie in the means that the search direction is constructed. Quasi-Newton methods are a class of methods that use the gradient to determine the search direction. An example of such a method would be the Davidson-Fletcher Powell method [46]. Such methods use the gradient as well as an approximation of the Hessian to generate the search direction. The methods vary in the procedures that are used to obtain the approximation of the Hessian. Quasi-Newton methods are desirable as compared to Newton?s method, because they only require first-order derivative information as opposed to the second order information that is required to compute the Hessian. This is desirable for more computationally-intensive problems such as robot dynamics. With the search direction and step size determined, the new value in the parameter space can be obtained, and convergence criteria can be evaluated. If convergence is not reached, the process is repeated with the current x(k+1) value updated to x(k), and a new x(k+1) is found. To summarize, a gradient-based search algorithm would be implemented using the following procedure: 1) Assign initial guess values to the variables. 2) Compute the gradient of the objective function. 3) Construct the search direction vector based on the gradient. 4) ?Move? in the direction of the search direction. 101 5) Check the termination condition, if satisfied, then terminate. If termination condition is not satisfied, go back to step 2. The major challenge in the implementation of such an algorithm is the computation of the gradient of the objective function, Equation 3.57. A common strategy that is used when gradient computation becomes intensive is to use finite- difference gradients. To compute a finite-difference gradient, the gradient of the objective function is estimated by perturbing the variable values by a small amount. Unfortunately, it has been reported that such methods give poor results for robot trajectory optimization problems [41]. In order to conduct a gradient-based optimization for this trajectory generation problem, the gradient of the objective function, Equation 3.57, must be computed with respect to the control points, p, in the B-spline formulation (Equation 3.3). The gradient of the objective function can be formulated as [41]: dtJ p t T p f )( 0 ?? ??=? ? (3.64) Like the work in [41], this function is integrated using a trapezoidal rule, thus the exact gradient of the approximated integral is calculated. In computing the gradient of the objective function, the most significant challenge is to compute the gradient of the joint torque function with respect to the control points that define the path. This is, however, possible, because of the nature of the equations. By using a B-spline formulation, this means that: 102 ),( tp?? = (3.65) because: ),( tpii ?? = (3.66) ),( tpii ?? =?? (3.67) ),( tpii ???? =?? (3.68) and ),,...,,,,...,,,,...,,( 212121 tNNN ????????? = ??????????? (3.69) for a given t, and with i=[1:N], with N being the number of joints in the mechanism. The given formulation means that the gradient of the torque function can be generated by: j k k i j k k i j k k i j i pppp ? ? ? ?+ ? ? ? ?+ ? ? ? ?= ? ? ?? ?? ? ? ? ? ?? ? ?? ? ?? (3.70) The calculation of the partial derivative of the joint angle with respect to the control points is trivial, and can be ascertained from the construction of the functions in Equation 3.3. 103 For the open loop mechanism, computation of Equation 3.69 can be directly performed by differentiating the equations for torque that are produced by the iterative Newton-Euler scheme. An example of such equations is presented in Chapter 4, with Equations 4.2 and 4.3. This computation is relatively straightforward. In the case of the closed-loop mechanism, the computation of the gradient is more complex. Recall that a system of linear equations was used to generate the torque values for the closed-loop mechanism, thus the solutions for torque were computed by inverting a matrix. Since it would impractical to invert an entire 9 X 9 or 12 X 12 matrix symbolically to generate expressions for torque, implicit differentiation must be used to compute the derivatives of torque with respect to the control points. The general formulation of the implicitly differentiated Equations 3.42-3.44 is shown as the following: j ix j ixi j ixi p vm p F p F ? ?= ? ?? ? ? ?+? )1()1( (3.71) j iy j iyi j iyi p vm p F p F ? ?= ? ?? ? ? ?+? )1()1( (3.72) ??? ? ??? ? ? ?+ ? ?+ ??? ? ??? ? ? ?+ ? ?+ ? ?? ? ? + + ? ?? iixi j i i j ixi iixi j i i j ixi j i j i F pp FlF pp Fl pp ? ??????? cossin 2cossin2 )1( )1( )1( )1(1 j i iiyi j i i j iyi iiyi j i i j iyi pIFpp FlF pp Fl ? ?= ??? ? ??? ? ? ?? ? ?? ??? ? ??? ? ? ?? ? ?? ? + + ? ? ??????? sincos 2sincos2 )1( )1( )1( )1( (3.73) 104 Since the values of the forces and torques are already computed, and the derivatives of the kinematics can be computed with respect to p using the same procedure that was used to compute the derivatives of the open-loop system, this system can be re- organized into a new matrix equation: i i j i p fA p F ? ?= ? ? ?1' (3.74) Where the term Fi denotes a vector of the torques and applied forces, as in Equation 3.48, A? is the new coefficient matrix, and fi is a new matrix that is created by combining the inertial derivatives and the terms on the right hand side of Equations 3.70 through 3.72 that do not contain derivatives of Fi. As in 3.48, the derivatives of torque are components of the applied force gradient. The values of Equation 3.73 at the discrete time steps can then be inserted into Equation 3.63, and the gradient computed using a trapezoidal integration. In order to perform this computation, a means of generating Equations 3.70- 3.72 from Equations 3.42-3.44 must be generated. This operation should be performed by an automated means because it would be cumbersome to execute manually. All that would be required to automate the generation of such equations would be a simple string processing algorithm to complete the implicit symbolic differentiation. This would be simple because the terms are restricted to functions of ? and products of these terms with sine and cosine terms. A substitution scheme 105 could be written to complete this operation. This program has not yet been written, and should be included in future work (see Section 6.3.3). 3.5.3. A Heuristic-Based Trajectory Generation Approach In view of the fact that complications arise when generating optimal gaits, a heuristic- based trajectory generation approach was used to demonstrate how trajectories could be generated using the kinematics and dynamics model. This approach should also be able to lend some insight to what trajectories would be better than others in the trajectory generation problem. This approach does not, however, find optimal solutions, and has the following three drawbacks: 1) It is based on a binary approximation of the gradient. 2) It is based on a discrete approximation of the effort metric. 3) It can only search discrete points in the variable space. In general, this approach can be described as a simple perturbation-based search. The approach begins with an initial set of parameters, and the effort metric is approximated. The parameters are then individually perturbed to see if they result in a decrease in effort, and the results are recorded. A new set of parameter values are then generated based on which perturbations resulted in decreased effort. The search continues until a specified number of iterations is reached. To use this approach, the effort metric must first be approximated. The effort metric can be approximated by: 106 tJ N j M m mjjm ? ??? ? ??? ? += ?? = ? = + 1 1 1 2 )1( 22 1)( ??? (3.75) This function estimates the average torque over an interval using the endpoints. There are M-1 intervals, with M boundary points of the intervals. The value of ?t is calculated by taking the number of intervals and dividing by the total time to complete the step. N is the number of joints in the mechanism. The heuristic-based search approach works by having an algorithm that takes the non-boundary control points of the trajectory and generates the effort required by that trajectory as an output. The program is called COMPUTE_DYN and takes a N X M matrix as an input, with N being the number of free control points that define each joint trajectory, and M being the number of free joints in the particular sub-problem. The output of the program is the effort required to achieve robot motion. With the control point data entered, and the fixed boundary control points stored in the program, the complete trajectories of the free (driven) joints are then calculated, along with the associated time derivatives. The results are discretized and stored as discrete point sets. This is done because of the simplicity associated with working with discrete point sets as opposed to continuous functions, as explained earlier. The second step of the algorithm is to calculate the inverse kinematics of the fixed joints. This is accomplished using the method presented previously. At this point, the complete trajectories for each angle in the snake have all been generated. 107 Thus, the shape of the snake, and the rate of change of shape are fully defined and stored as point sets. Upon knowing the inverse kinematics, the direct kinematics of the system must then be computed. This must be done because in order to apply the Newton equation to the system, the rectilinear accelerations of each link must be known. After the direct kinematics are calculated, the matrix equation is then constructed in order to calculate the dynamics of the system, and the torque values of each driven joint are extracted at each step of the time sampling. At this point, constraints on the system must be addressed. The constraints, which have been previously mentioned in the kinematics section, are that each joint of the mechanism must not lie below the position y=0. This is due to the fact that if the joints are configured such that this was the case, then the assumption about the ground contact would be invalid. The second constraint is that the equation that was used to solve the position of the fixed joints must have a real solution. The algorithm tests each of these constraints and determines if both of them are satisfied. The final step of the algorithm is calculating the effort metric. The metric is shown as equation 3.63. A simple penalty scheme is used to address the constraints. The way that the penalty is assessed is that if the constraint criteria are violated, the effort value is set at 100 (arbitrary large number). If the constraint criteria are satisfied, the calculated effort value is the output. With the previous program functioning as the objective function, a separate program was developed to run the search routine. This program uses COMPUTE_DYN and its output to search for a good solution. The program begins 108 with an initial value for the matrix of control points, Co, a number specifying the number of iterations the search process should be attempted, and a value specifying the step size for the search, ?. The program then runs COMPUTE_DYN with the initial control points Co, and obtains the effort value of the gait step that is described by the initial control points. After this value is obtained, an approximated gradient of the effort value with respect to the free control points is calculated. This is accomplished by individually perturbing the control points by both ? and ??. After each perturbation, the new effort value is calculated. If the new effort value is lower than the initial effort value, then a 1 is stored in the direction (?Dir? in Figure 3.14) matrix. If not, a zero is stored. This matrix can then be used to construct an approximated gradient that stores the complete N X M direction of decreasing effort value. It is important to note that this is a coarse solution because it only considers each parameter (control point) individually, and it does not store information related to the amount of effort change achieved by each perturbation. Nonetheless, it results in a direction of decreased effort value in most cases. A search direction is then constructed by multiplying this ?gradient? by ?, and the C matrix is updated by C=C+search. This process is repeated and the search finds trajectories with lower effort values until it reaches the specified number of iterations. A flow chart for this routine is shown in Figure 3.14. 109 Figure 3.13. Architecture of fitness evaluation function ? COMPUTE_DYN(C). Input: C=NXM matrix Generate B- splines and derivatives Calculate Inverse Kinematics Calculate Direct Kinematics Calculate Dynamics Are constraints satisfied? yes no Calculate effort, Output Set effort to 100, Output 110 Figure 3.14. Organization of search algorithm. Initialize : C=Co, count=0, countmax, ? Run COMPUTE_DYN( Co)=Eo Perturb C(i)=C(i)+? Run COMPUTE_DYN (C)=E If E