Simplified and Abstracted Geometry for Forward Dynamics - Revision history

D Wilkie at 18:13, 8 February 2007

2007-02-08T18:13:54Z

D Wilkie: /* Example Problem */

2006-10-17T05:00:08Z

Example Problem

D Wilkie: /* Introduction */

2006-10-17T04:58:50Z

Introduction

D Wilkie: /* Introduction */

2006-10-17T04:57:20Z

Introduction

D Wilkie: /* Introduction */

2006-10-17T04:54:46Z

Introduction

D Wilkie: /* Introduction */

2006-10-17T04:27:22Z

Introduction

D Wilkie: /* Introduction */

2006-10-17T04:16:33Z

Introduction

D Wilkie: /* Approach */

2006-10-16T16:31:34Z

Approach

D Wilkie: /* Example Problem */

2006-10-16T16:31:14Z

Example Problem

D Wilkie: /* Background */

2006-10-16T16:30:39Z

Background

@@ Line 1: / Line 1: @@
-''Draft''
+(eventually this will be fixed...)
-==Abstract==
-==Introduction==
-	Before the ascent of CAD programs in engineering design, engineers worked with what mathematics and formalisms they could, but had to fill the gaps with intuition and guesswork.  They designed on paper and on the physical object itself.  For example, World War I era engineers designed propellers not with strict mathematical models, but with a visual sense of what a propeller should look like.  Some of the geometric design for the propellers could be done on paper, but this too was an artistic and generally inefficient method of design.  With the advent of CAD, however, vast new design spaces opened up, allowing engineers to efficiently model their ideas in silico and effectively communicate their ideas to others in a mathematically precise way.  Many testing and tuning problems are still handled by engineers in a manner similar to the pre-CAD design practice: computational processes are used when possible, but most of the work is done by the engineers getting their hands dirty on the physical object.
-−
-	It is trivial to say that were testing, tuning, and other tasks done accurately in silico instead of on physical systems, there would be improvements in the efficiency and quality of the design process.  Computer simulation of complex mechatronic systems offers many advantages over reliance on physical prototyping and analytical formalisms.  In simulation, the system can be placed in conditions in which it would risk damage or destruction.  In fact, it may be pertinent to some technical inquiries to damage or destroy the system intentionally.  Needless to say, such damages and risks impose a heavy cost on engineering teams who are testing on physical systems.  Even tests with a low risk of damage to the system have a higher cost than equivilent tests done with simulation.  Simulation also provides a boon to empirical testing as the exact conditions can be replicated for every expirement, something that is implossible with testing done on physical systems.  Tests can also be run faster than "real time" and in parallel, allowing an engineering team to test in and hour conditions that would take years to test on physical systems.
-−
-	//THIS IS A BAD PARAGRAPH//Given the desirability of replacing physical systems with appropriate simulations in the design cycle, one must ask: why isn't this done?  The answer is that to a large extent it is done: it's common practice to use simulation for such things as FEA, fluid dynamics, etcetera.  However, there are many other problems for which no computationally efficient model exists that can produce results with a great enough fidelity to forgo physical testing.  One example of this is the simulation of the forward dynamics of robotic systems with many  DOFs.  If such simulation could be done efficiently with satisfactory fidelity, it could be incorperated at many points in the design cycle.  For examlpe, it could be used as an objective function for evaluating design alternatives.  This kind of simulation would also be useful for path planning.  Traditional path planning now is done strictly with kinematic constraints incorperated, few if any dynamic properties.  This has the disadvantage of not being able to elegently take into account physics within the path planning.  Such an absence means that a path cannot be optimized for minimizing power usage or torques, and the path my incorrectly treat operations such as cantilevering over a crevice of crawling over obstacles.  Additionally, new and promising robotic designs focusing on reconfigurability will require multibody dynamical simulation to ensure that new configurations are stable and can effect the desired task.  The high dimensionality of this kind of dynamic path planning has made it largely infeasible.
-−
-	These simulations might be feasible, however, if efficient models can be derived for the system and the problem at hand.  In the CAD models of these systems, there are an "irrelevant many and a vital few"[simulation book...] for dynamics simulation.  Both the geometric model and the assembly of the system as described in a CAD program are up for abstraction and simplification.  What homomorphism is appropriate depends on the context:  a robot walking straight will require a much simpler representation than one undergoing unpredictable actions in a complex environment.
-−
-	//FAILS TO MENTION CURRENT FORWARD DYNAMICS ALGORITHMS TIME DEPENDENCY ON DOFs/JOINTS//The need for simulation and abstraction of robot and mechanism geometry arises out of the large size of CAD data and the computational cost of simulations involving them. Typical tessellations for CAD data viewing, inside CAD programs, results in a very high number of triangles, more than can be effectively simulated with current hardware. Even with hardware advances, it will always be advantageous in some situations to cull away data irrelevent to answering a posed technical problem. The motivation for simplification and abstraction then exists, but how to simplify or abstract the system is a question that to our knowledge has not been addressed in the area of forward dynamics simulation incorperating geometric data.
-−
-	Geometric simplification has played an important role in the computer graphics field by allowing believable viewing of scenes too complex for timely computation. However, the approaches used in computer graphics for geometric simplification have as their goal the realistic portrayal of a scene to a viewer, not the similarity between the simplified or abstracted system and the physical ground truth. In physical simulations, the model does not need to look like the original. If a robot's legs can be abstracted as a pair of oval wheels that hit contact points appropriately, this might be acceptable for a physical simulation. However, it would be completely inappropriate for a graphical system. This offers a freedom of abstraction and simplification that does not exist in the graphics world. However, other constraints apply: in rigid-body dynamics simulations of robots and complex mechanisms, geometry plays a key role in determining where the contact points, and thus collision joints, occur; different simplification methods will lead to different simulated results.  The choice of simplification method can be the determining factor of whether a simulation is accurate and efficient enough.
-−
-// simplifications and abstractions must preserve certain semantics (joints, contacts, and other)
-−
-// paragraph on contextual simplification and abstraction
-−
-//paper organization paragraph
-−
-==Background==
-//paragraph introducing/justifying snake platform
-−
-Snake-like robots [1] offer several advantages over conventional wheeled or legged robots. For example, robotic snakes have a low center of gravity, which makes them very stable when moving on inclines. In addition, if a snake-like robot were to fall over, it could easily recover by articulating its body in the proper way. Unlike their walking or wheeled counterparts, snake-like robots spread their weight out over a large area, thus exerting less force per unit area over the surface on which they are moving. This characteristic means that robots of this class are better suited for moving over soil or sand, compared to wheeled and legged robots that are very likely to get stuck in such environments.
-−
-We have designed a robotic snake capable of undergoing efficient rectilinear motion Currently, robotic snakes are available which can perform rectilinear motion by articulation each of their segments in a repeated sequence. A paper published in IEEE Transactions on Robotics and Automation titled “The Kinematics of Hyper-Redundant Robot Locomotion” [3] outlines various methods for accomplishing this task. In fact, this paper concentrates on creating rectilinear locomotion through body movements alone. Chirikjian classifies snake-like robots as either inextensible or extensible. The former are capable of only bending their segments with respect to each other while the latter can actually expand and contract like an accordion. He outlines several locomotion algorithms for robots of these types, but does not address the construction of such robots. We observe that robots of this family tend to be slow and require extensive operator input. In addition, the precise interaction between segments, which is required for efficient locomotion, can be difficult to achieve. “Limbless locomotion: Learning to crawl with a snake robot,” [1] goes to great detail in discussing the possible construction of inextensible snake-like robots, but does not settle on a particular design.
-−
-Our approach, developed through the study of these papers, as well as several prototypes that were built earlier in Philadelphia-area laboratories, proposes a completely new robotic snake design. This design does not fall into any of the previous classes, as our robot would propel itself using many small “feet”, with locomotion similar to that of a millipede. Obviously, a robot of this design will be efficient at performing rectilinear motion. Since this robot will actually walk, rather than drag itself, it should be capable of navigating rough terrains easily and efficiently. For this reason, it is expected that our design would be more maneuverable that existing prototypes.
-−
-//rigid dynamics background
-−
-//geometric simplification background
-−
-//levels of detail background
-−
-//adaptive dynamics background
-−
-==Example Problem==
-        //Former paragraph was terrible: introduce better forward dynamics as example problem (too narrow?)
-−
-	The space of forward dynamics is far too large:  even a simple robotic system can have numerous torque inputs and can locomote over infinitely many terrains.  However, most of the actions possible for robotic systems will never be used, and most of the conceivable terrains will never be encountered.  The investigated scenarios are thus not chosen randomly from the space, but based on desired "behaviors" of our robotic system, such as rectilinear movement, following a curve, and cantilevering.*  Each of these behaviors will be undertaken on different terrains and with different paths with every model.  The models will then be independently evaluated within the context of the test.
-−
-	To derive our models, we decided to use our CAD model as a basis.  This is not necessary: in practice, an engineer could create a computable model from his knowledge of the design.  One advantage in deriving the simulation model from the CAD model is that, once the process is automated, the engineer is no longer required to repeat modeling work.  The automated process will also be more efficient, allowing for rapid, contextual modeling based on desired behaviors, terrains, paths, and any number of other parameters.
-−
-//various methods of simplification and abstraction will be tested
-−
-	Perhaps the simplest mapping from a CAD model to a computationally efficient model for simulation is low detail mesh tesselation or mesh simplification.  This process takes as input either a high detail mesh or a CAD solid model and produces a lower detail mesh.  There are numerous algorithms for mesh simplification that have been in use in the graphics community for years.  (INVESTIGATE AND FORMALLY DESCRIBE TECHNIQUES TO USE.)
-−
-	Another method of CAD model geometric simplification is the use of convex hulls, bounding boxes, or geometric primitives (spheres, cylinders, capsules, etc.) to represent individual components.  (INSERT FORMAL DEFINITION OF CONVEX HULL AND INVESTIGATE TECHNIQUES TO USE.) In the engineering context, this mapping is complicated (as all the mappings discussed) by the fact that certain assembly interactions are determined in part by the geometry of the system: self-intersections caused by the abstractions are an example of this problem.
-−
-	Less often done is the abstracting of sub-assemblies by more primitive assemblies, meshes, or primitives.  In graphics, such an abstraction would be visually distinct to such a degree that the technique would be useless (few movie audiences would accept a character whose legs had been replaced with rotating ovals).  In the context of simulation, however, such retinal properties are irrelevant.   All that matters is the accuracy of the simulated variables of interest. (INVESTIGATE AND DESCRIBE ABSTRACTION PRACTICES HERE.  ALSO, PROBABLY GET RID OF "RETINAL" COMMENT.)
-−
-//evaluation will be based on divergence from physical result and computational cost: obvious trade off.
-−
-==Approach==
-//list of simplifications and abstractions that will be tested and how they were obtained.
-−
-//Adams software paragraph and integration talk
-−
-//definition of each simulation scenario
-−
-//specification of metrics:
-	//distance (based on least squares?) of simulated contact points from
-measured true contact points.
-	// difference in power, torque, output as from measured
-	//computational cost: cycles (how can these be measured in Adams? start count before hand and end after in perl or something?)
-−
-==Empirical Results==
-==Conclusions==
-==References==
-−
-[http://gamma.cs.unc.edu/cohenj/Manocha-Cohen-Simplification.pdf Model Simplification(PDF)]
-−
-[http://delivery.acm.org/10.1145/1080000/1073294/p936-redon.pdf?key1=1073294&key2=4836720611&coll=GUIDE&dl=GUIDE&CFID=1593890&CFTOKEN=71462887 Adaptive Dynamics(PDF)]
-−
-[http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6TYR-4J6X4NY-1-11&_cdi=5625&_user=95578&_orig=search&_coverDate=04%2F30%2F2006&_sk=999619995&view=c&_alid=463329875&_rdoc=9&wchp=dGLbVzz-zSkzS&md5=8366a7529b7a9a9b6f606a1976d1c883&ie=/sdarticle.pdf Milling Machine Simplification(PDF)]
-−
-[http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6TYR-49NPTYT-1-55&_cdi=5625&_user=95578&_orig=search&_coverDate=08%2F31%2F2004&_sk=999639990&view=c&_alid=463330650&_rdoc=3&wchp=dGLbVtb-zSkWA&md5=3ded555ed960d692cc5a947c9487dc82&ie=/sdarticle.pdf Geometric Model Simplification for CAD(PDF)]
-−
-[http://epubl.luth.se/1402-1617/2005/270/LTU-EX-05270-SE.pdf Relevant Master's Thesis]

@@ Line 38: / Line 38: @@
 ==Example Problem==
-	The computational model we're investigating is ultimately applicable to planning, testing, tuning, and a number of other problems.  However, the atomic operation all of these would make use of is the forward dynamics simulation.  Therefore, this will be the test that our models will undergo to demonstrate thier computational fidelity and efficiency.
+        //Former paragraph was terrible: introduce better forward dynamics as example problem (too narrow?)
 	The space of forward dynamics is far too large:  even a simple robotic system can have numerous torque inputs and can locomote over infinitely many terrains.  However, most of the actions possible for robotic systems will never be used, and most of the conceivable terrains will never be encountered.  The investigated scenarios are thus not chosen randomly from the space, but based on desired "behaviors" of our robotic system, such as rectilinear movement, following a curve, and cantilevering.*  Each of these behaviors will be undertaken on different terrains and with different paths with every model.  The models will then be independently evaluated within the context of the test.

@@ Line 12: / Line 12: @@
 	//FAILS TO MENTION CURRENT FORWARD DYNAMICS ALGORITHMS TIME DEPENDENCY ON DOFs/JOINTS//The need for simulation and abstraction of robot and mechanism geometry arises out of the large size of CAD data and the computational cost of simulations involving them. Typical tessellations for CAD data viewing, inside CAD programs, results in a very high number of triangles, more than can be effectively simulated with current hardware. Even with hardware advances, it will always be advantageous in some situations to cull away data irrelevent to answering a posed technical problem. The motivation for simplification and abstraction then exists, but how to simplify or abstract the system is a question that to our knowledge has not been addressed in the area of forward dynamics simulation incorperating geometric data.
-	Geometric simplification has played an important role in the computer graphics field by allowing believable viewing of scenes too complex for timely computation. However, the approaches used in computer graphics for geometric simplification have as their goal the realistic portrayal of a scene to a viewer, not the similarity between the simplified or abstracted system and the physical ground truth. In physical simulations, the model does not need to look like the original. If a robot's legs can be abstracted as a pair of oval wheels that hit contact points appropriately, this might be acceptable for a physical simulation. However, it would be completely inappropriate for a graphical system. This offers a freedom of abstraction and simplification that does not exist in the graphics world. However, other constraints apply: in rigid-body dynamics simulations of robots and complex mechanisms, geometry plays a key role in determining where the contact points, and thus collision joints, occur; different simplification methods will lead to different simulated results.  The choice of simplification method can be the determining factor of whether a simulation is accurate enough.
+	Geometric simplification has played an important role in the computer graphics field by allowing believable viewing of scenes too complex for timely computation. However, the approaches used in computer graphics for geometric simplification have as their goal the realistic portrayal of a scene to a viewer, not the similarity between the simplified or abstracted system and the physical ground truth. In physical simulations, the model does not need to look like the original. If a robot's legs can be abstracted as a pair of oval wheels that hit contact points appropriately, this might be acceptable for a physical simulation. However, it would be completely inappropriate for a graphical system. This offers a freedom of abstraction and simplification that does not exist in the graphics world. However, other constraints apply: in rigid-body dynamics simulations of robots and complex mechanisms, geometry plays a key role in determining where the contact points, and thus collision joints, occur; different simplification methods will lead to different simulated results.  The choice of simplification method can be the determining factor of whether a simulation is accurate and efficient enough.
 // simplifications and abstractions must preserve certain semantics (joints, contacts, and other)

@@ Line 10: / Line 10: @@
 	These simulations might be feasible, however, if efficient models can be derived for the system and the problem at hand.  In the CAD models of these systems, there are an "irrelevant many and a vital few"[simulation book...] for dynamics simulation.  Both the geometric model and the assembly of the system as described in a CAD program are up for abstraction and simplification.  What homomorphism is appropriate depends on the context:  a robot walking straight will require a much simpler representation than one undergoing unpredictable actions in a complex environment.
-	The need for simulation and abstraction of robot and mechanism geometry arises out of the large size of CAD data and the computational cost of simulations involving them. Typical tessellations for CAD data viewing, inside CAD programs, results in a very high number of triangles, more than can be effectively simulated with current hardware. Even with hardware advances, it will always be advantageous in some situations to cull away data irrelevent to answering a posed technical problem. The motivation for simplification and abstraction then exists, but how to simplify or abstract the system is a question that to our knowledge has not been addressed in the area of forward dynamics simulation incorperating geometric data.
+	//FAILS TO MENTION CURRENT FORWARD DYNAMICS ALGORITHMS TIME DEPENDENCY ON DOFs/JOINTS//The need for simulation and abstraction of robot and mechanism geometry arises out of the large size of CAD data and the computational cost of simulations involving them. Typical tessellations for CAD data viewing, inside CAD programs, results in a very high number of triangles, more than can be effectively simulated with current hardware. Even with hardware advances, it will always be advantageous in some situations to cull away data irrelevent to answering a posed technical problem. The motivation for simplification and abstraction then exists, but how to simplify or abstract the system is a question that to our knowledge has not been addressed in the area of forward dynamics simulation incorperating geometric data.
 	Geometric simplification has played an important role in the computer graphics field by allowing believable viewing of scenes too complex for timely computation. However, the approaches used in computer graphics for geometric simplification have as their goal the realistic portrayal of a scene to a viewer, not the similarity between the simplified or abstracted system and the physical ground truth. In physical simulations, the model does not need to look like the original. If a robot's legs can be abstracted as a pair of oval wheels that hit contact points appropriately, this might be acceptable for a physical simulation. However, it would be completely inappropriate for a graphical system. This offers a freedom of abstraction and simplification that does not exist in the graphics world. However, other constraints apply: in rigid-body dynamics simulations of robots and complex mechanisms, geometry plays a key role in determining where the contact points, and thus collision joints, occur; different simplification methods will lead to different simulated results.  The choice of simplification method can be the determining factor of whether a simulation is accurate enough.

@@ Line 6: / Line 6: @@
 	It is trivial to say that were testing, tuning, and other tasks done accurately in silico instead of on physical systems, there would be improvements in the efficiency and quality of the design process.  Computer simulation of complex mechatronic systems offers many advantages over reliance on physical prototyping and analytical formalisms.  In simulation, the system can be placed in conditions in which it would risk damage or destruction.  In fact, it may be pertinent to some technical inquiries to damage or destroy the system intentionally.  Needless to say, such damages and risks impose a heavy cost on engineering teams who are testing on physical systems.  Even tests with a low risk of damage to the system have a higher cost than equivilent tests done with simulation.  Simulation also provides a boon to empirical testing as the exact conditions can be replicated for every expirement, something that is implossible with testing done on physical systems.  Tests can also be run faster than "real time" and in parallel, allowing an engineering team to test in and hour conditions that would take years to test on physical systems.
-	Given the desirability of replacing physical systems with appropriate simulations in the design cycle, one must ask: why isn't this done?   The answer is that to a large extent it is done: it's common practice to use simulation for such things as FEA, fluid dynamics, etcetera.  However, there are many other problems for which no computationally efficient model exists that can produce results with a great enough fidelity to forgo physical testing.  One example of this is the simulation of the forward dynamics of robotic systems with many  DOFs.  If such simulation could be done efficiently with satisfactory fidelity, it could be incorperated at many points in the design cycle.  For examlpe, it could be used as an objective function for evaluating design alternatives.  This kind of simulation would also be useful for path planning.  Traditional path planning now is done strictly with kinematic constraints incorperated, few if any dynamic properties.  This has the disadvantage of not being able to elegently take into account physics within the path planning.  Such an absence means that a path cannot be optimized for minimizing power usage or torques, and the path my incorrectly treat operations such as cantilevering over a crevice of crawling over obstacles.  Additionally, new and promising robotic designs focusing on reconfigurability will require multibody dynamical simulation to ensure that new configurations are stable and can effect the desired task.  The high dimensionality of this kind of dynamic path planning has made it largely infeasible.
+	//THIS IS A BAD PARAGRAPH//Given the desirability of replacing physical systems with appropriate simulations in the design cycle, one must ask: why isn't this done?  The answer is that to a large extent it is done: it's common practice to use simulation for such things as FEA, fluid dynamics, etcetera.  However, there are many other problems for which no computationally efficient model exists that can produce results with a great enough fidelity to forgo physical testing.  One example of this is the simulation of the forward dynamics of robotic systems with many  DOFs.  If such simulation could be done efficiently with satisfactory fidelity, it could be incorperated at many points in the design cycle.  For examlpe, it could be used as an objective function for evaluating design alternatives.  This kind of simulation would also be useful for path planning.  Traditional path planning now is done strictly with kinematic constraints incorperated, few if any dynamic properties.  This has the disadvantage of not being able to elegently take into account physics within the path planning.  Such an absence means that a path cannot be optimized for minimizing power usage or torques, and the path my incorrectly treat operations such as cantilevering over a crevice of crawling over obstacles.  Additionally, new and promising robotic designs focusing on reconfigurability will require multibody dynamical simulation to ensure that new configurations are stable and can effect the desired task.  The high dimensionality of this kind of dynamic path planning has made it largely infeasible.
 	These simulations might be feasible, however, if efficient models can be derived for the system and the problem at hand.  In the CAD models of these systems, there are an "irrelevant many and a vital few"[simulation book...] for dynamics simulation.  Both the geometric model and the assembly of the system as described in a CAD program are up for abstraction and simplification.  What homomorphism is appropriate depends on the context:  a robot walking straight will require a much simpler representation than one undergoing unpredictable actions in a complex environment.