Underactuated Robotics theory. Optimal control. First steps

With initial experience and basic level of knowledge of the dynamics and stability, we will try to take the first steps of an elementary virtual robot. Robot, which took in account own dynamics, and, if possible, use it to good use.

But before proceed to apply existing knowledge, I will try to expand the list of theories to help us in the way of understanding the dynamics of walking robots.

In additional, here we will try addressing some of the real conditions to be encountered during implementation of mathematical model in real world.

Underactuated Robotics theory, Preparing for first step

The most robotics enthusiasts lack the necessary theoretical knowledge. The lack of this knowledge mainly argumented by the complexity of these theories.

It is for reason that enthusiasm is not supported by the knowledge of theory the result work looks like a child's play. Huge efforts and waste of time, most of the initiatives ends regular structure, similar to hundreds of other similar structures and does not have any different.

I would like to start a series of articles that demonstrate the possibility of studying the necessary theories at the own example. A month ago, I began to study the subject "Under-actuated robotics", presented by the Massachusetts Institute of Technology and is open to the public (MIT, Underactuated Robotics, OpenCourceWare).

Programmer Competency Matrix

Some time ago I discovered on the Internet one short but very useful post.

Original post was taken from here.

The main idea is a compressed representation of the classification table of qualifications in various aspects of knowledge and experience in software development.

Another benefit from this matrix seems to me the mathematical evaluation of the time required for the implementation of conditional task. (2ⁿ  ... log (n)). For me, a person familiar with the math, this feature seems perfect in their utility.


Here I would like to repost this table for myself to review it each time when I think about the qualifications of the employee.

In addition, all the more important it seems to me the task of expanding this list as you add new examples to describe the level of qualification in one or another branch of programming, and by adding branches with the list of qualifications and examples.

Computer Science
	2n (Level 0)	n2 (Level 1)	n (Level 2)	log(n) (Level 3)
data structures	Doesn't know the difference between Array and LinkedList	Able to explain and use Arrays, LinkedLists, Dictionaries etc in practical programming tasks	Knows space and time tradeoffs of the basic data structures, Arrays vs LinkedLists, Able to explain how hashtables can be implemented and can handle collisions, Priority queues and ways to implement them etc.	Knowledge of advanced data structures like B-trees, binomial and fibonacci heaps, AVL/Red Black trees, Splay Trees, Skip Lists, tries etc.
algorithms	Unable to find the average of numbers in an array (It's hard to believe but I've interviewed such candidates)	Basic sorting, searching and data structure traversal and retrieval algorithms	Tree, Graph, simple greedy and divide and conquer algorithms, is able to understand the relevance of the levels of this matrix.	Able to recognize and code dynamic programming solutions, good knowledge of graph algorithms, good knowledge of numerical computation algorithms, able to identify NP problems etc.
systems programming	Doesn't know what a compiler, linker or interpreter is	Basic understanding of compilers, linker and interpreters. Understands what assembly code is and how things work at the hardware level. Some knowledge of virtual memory and paging.	Understands kernel mode vs. user mode, multi-threading, synchronization primitives and how they're implemented, able to read assembly code. Understands how networks work, understanding of network protocols and socket level programming.	Understands the entire programming stack, hardware (CPU + Memory + Cache + Interrupts + microcode), binary code, assembly, static and dynamic linking, compilation, interpretation, JIT compilation, garbage collection, heap, stack, memory addressing...
Software Engineering
	2n (Level 0)	n2 (Level 1)	n (Level 2)	log(n) (Level 3)
source code version control	Folder backups by date	VSS and beginning CVS/SVN user	Proficient in using CVS and SVN features. Knows how to branch and merge, use patches setup repository properties etc.	Knowledge of distributed VCS systems. Has tried out Bzr/Mercurial/Darcs/Git
build automation	Only knows how to build from IDE	Knows how to build the system from the command line	Can setup a script to build the basic system	Can setup a script to build the system and also documentation, installers, generate release notes and tag the code in source control
automated testing	Thinks that all testing is the job of the tester	Has written automated unit tests and comes up with good unit test cases for the code that is being written	Has written code in TDD manner	Understands and is able to setup automated functional, load/performance and UI tests
Programming
	2n (Level 0)	n2 (Level 1)	n (Level 2)	log(n) (Level 3)
problem decomposition	Only straight line code with copy paste for reuse	Able to break up problem into multiple functions	Able to come up with reusable functions/objects that solve the overall problem	Use of appropriate data structures and algorithms and comes up with generic/object-oriented code that encapsulate aspects of the problem that are subject to change.
systems decomposition	Not able to think above the level of a single file/class	Able to break up problem space and design solution as long as it is within the same platform/technology	Able to design systems that span multiple technologies/platforms.	Able to visualize and design complex systems with multiple product lines and integrations with external systems. Also should be able to design operations support systems like monitoring, reporting, fail overs etc.
communication	Cannot express thoughts/ideas to peers. Poor spelling and grammar.	Peers can understand what is being said. Good spelling and grammar.	Is able to effectively communicate with peers	Able to understand and communicate thoughts/design/ideas/specs in a unambiguous manner and adjusts communication as per the context
code organization within a file	no evidence of organization within a file	Methods are grouped logically or by accessibility	Code is grouped into regions and well commented with references to other source files	File has license header, summary, well commented, consistent white space usage. The file should look beautiful.
	2n (Level 0)	n2 (Level 1)	n (Level 2)	log(n) (Level 3)
code organization across files	No thought given to organizing code across files	Related files are grouped into a folder	Each physical file has a unique purpose, for e.g. one class definition, one feature implementation etc.	Code organization at a physical level closely matches design and looking at file names and folder distribution provides insights into design
source tree organization	Everything in one folder	Basic separation of code into logical folders.	No circular dependencies, binaries, libs, docs, builds, third-party code all organized into appropriate folders	Physical layout of source tree matches logical hierarchy and organization. The directory names and organization provide insights into the design of the system.
code readability	Mono-syllable names	Good names for files, variables classes, methods etc.	No long functions, comments explaining unusual code, bug fixes, code assumptions	Code assumptions are verified using asserts, code flows naturally - no deep nesting of conditionals or methods
defensive coding	Doesn't understand the concept	Checks all arguments and asserts critical assumptions in code	Makes sure to check return values and check for exceptions around code that can fail.	Has his own library to help with defensive coding, writes unit tests that simulate faults
	2n (Level 0)	n2 (Level 1)	n (Level 2)	log(n) (Level 3)
error handling	Only codes the happy case	Basic error handling around code that can throw exceptions/generate errors	Ensures that error/exceptions leave program in good state, resources, connections and memory is all cleaned up properly	Codes to detect possible exception before, maintain consistent exception handling strategy in all layers of code, come up with guidelines on exception handling for entire system.
IDE	Mostly uses IDE for text editing	Knows their way around the interface, able to effectively use the IDE using menus.	Knows keyboard shortcuts for most used operations.	Has written custom macros
API	Needs to look up the documentation frequently	Has the most frequently used APIs in memory	Vast and In-depth knowledge of the API	Has written libraries that sit on top of the API to simplify frequently used tasks and to fill in gaps in the API
frameworks	Has not used any framework outside of the core platform	Has heard about but not used the popular frameworks available for the platform.	Has used more than one framework in a professional capacity and is well-versed with the idioms of the frameworks.	Author of framework
	2n (Level 0)	n2 (Level 1)	n (Level 2)	log(n) (Level 3)
requirements	Takes the given requirements and codes to spec	Come up with questions regarding missed cases in the spec	Understand complete picture and come up with entire areas that need to be speced	Able to suggest better alternatives and flows to given requirements based on experience
scripting	No knowledge of scripting tools	Batch files/shell scripts	Perl/Python/Ruby/VBScript/Powershell	Has written and published reusable code
database	Thinks that Excel is a database	Knows basic database concepts, normalization, ACID, transactions and can write simple selects	Able to design good and normalized database schemas keeping in mind the queries that'll have to be run, proficient in use of views, stored procedures, triggers and user defined types. Knows difference between clustered and non-clustered indexes. Proficient in use of ORM tools.	Can do basic database administration, performance optimization, index optimization, write advanced select queries, able to replace cursor usage with relational sql, understands how data is stored internally, understands how indexes are stored internally, understands how databases can be mirrored, replicated etc. Understands how the two phase commit works.
Experience
	2n (Level 0)	n2 (Level 1)	n (Level 2)	log(n) (Level 3)
languages with professional experience	Imperative or Object Oriented	Imperative, Object-Oriented and declarative (SQL), added bonus if they understand static vs dynamic typing, weak vs strong typing and static inferred types	Functional, added bonus if they understand lazy evaluation, currying, continuations	Concurrent (Erlang, Oz) and Logic (Prolog)
platforms with professional experience	1	2-3	4-5	6+
years of professional experience	1	2-5	6-9	10+
domain knowledge	No knowledge of the domain	Has worked on at least one product in the domain.	Has worked on multiple products in the same domain.	Domain expert. Has designed and implemented several products/solutions in the domain. Well versed with standard terms, protocols used in the domain.
Knowledge
	2n (Level 0)	n2 (Level 1)	n (Level 2)	log(n) (Level 3)
tool knowledge	Limited to primary IDE (VS.Net, Eclipse etc.)	Knows about some alternatives to popular and standard tools.	Good knowledge of editors, debuggers, IDEs, open source alternatives etc. etc. For e.g. someone who knows most of the tools from Scott Hanselman's power tools list. Has used ORM tools.	Has actually written tools and scripts, added bonus if they've been published.
languages exposed to	Imperative or Object Oriented	Imperative, Object-Oriented and declarative (SQL), added bonus if they understand static vs dynamic typing, weak vs strong typing and static inferred types	Functional, added bonus if they understand lazy evaluation, currying, continuations	Concurrent (Erlang, Oz) and Logic (Prolog)
codebase knowledge	Has never looked at the codebase	Basic knowledge of the code layout and how to build the system	Good working knowledge of code base, has implemented several bug fixes and maybe some small features.	Has implemented multiple big features in the codebase and can easily visualize the changes required for most features or bug fixes.
knowledge of upcoming technologies	Has not heard of the upcoming technologies	Has heard of upcoming technologies in the field	Has downloaded the alpha preview/CTP/beta and read some articles/manuals	Has played with the previews and has actually built something with it and as a bonus shared that with everyone else
	2n (Level 0)	n2 (Level 1)	n (Level 2)	log(n) (Level 3)
platform internals	Zero knowledge of platform internals	Has basic knowledge of how the platform works internally	Deep knowledge of platform internals and can visualize how the platform takes the program and converts it into executable code.	Has written tools to enhance or provide information on platform internals. For e.g. disassemblers, decompilers, debuggers etc.
books	Unleashed series, 21 days series, 24 hour series, dummies series...	Code Complete, Don't Make me Think, Mastering Regular Expressions	Design Patterns, Peopleware, Programming Pearls, Algorithm Design Manual, Pragmatic Programmer, Mythical Man month	Structure and Interpretation of Computer Programs, Concepts Techniques, Models of Computer Programming, Art of Computer Programming, Database systems , by C. J Date, Thinking Forth, Little Schemer
blogs	Has heard of them but never got the time.	Reads tech/programming/software engineering blogs and listens to podcasts regularly.	Maintains a link blog with some collection of useful articles and tools that he/she has collected	Maintains a blog in which personal insights and thoughts on programming are shared

Note that the knowledge for each level is cumulative; being at level n implies that you also know everything from the levels lower than n.

PrintMe (print my source code)

Hi all my readers.

Some time ago I bet to write a program that prints its own source code.

The restriction was - to use only C/C++, and that the result of the program can be substituted into the source code, recompile, which would receive the same result.

As far as I remember, it's funny, a little problem with a solution, though not simple. I wrote it and won the bet.

Then I asked how many solutions to this problem has been posted on the Internet? And to my surprise, it turned out that the Internet is almost no such solutions.

I decided to remedy this situation and show the solution here. If someone will have any questions or clarifications, I would be happy to discuss it in the comments.

 #include <stdio.h>
 #include <string>
 #include <iostream>
 #include <fstream>
 std::string a = "\
      std::ofstream     myfile(@PrintMe.txt@);$\
      std::string          b(a);$\
      std::string::iterator     it(b.begin());$\
      while (it != b.end())$\
      {$\
           if (*it == 36)$\
           {$\
                it = b.insert(++it, '__');$\
                it = b.insert(++it, '_n');$\
           }$\
           ++it;$\
      }$\
      myfile << @#include <stdio.h>@ << std::endl;$\
      myfile << @#include <string>@ << std::endl;$\
      myfile << @#include <iostream>@ << std::endl;$\
      myfile << @#include <fstream>@ << std::endl;$\
      myfile << @std::string a = _@__@ << std::endl;$\
      myfile << b << @_@;@ << std::endl;$\
      it = a.begin();$\
      while (it != a.end())$\
      {$\
           if (*it == 64)$\
           {$\
                *it = '_@';$\
           }$\
           else$\
           if (*it == 36)$\
           {$\
                *it = '_n';$\
           }$\
           else$\
           if (*it == 95)$\
           {$\
                *it = '__';$\
           }$\
           ++it;$\
      }$\
      myfile << @void main()@ << std::endl;$\
      myfile << @{@ << std::endl;$\
      myfile << a << std::endl;$\
      myfile << @}@ << std::endl;$\
      myfile.close();$\
 ";
 void main()
 {
      std::ofstream     myfile("PrintMe.txt");
      std::string          b(a);
      std::string::iterator     it(b.begin());
      while (it != b.end())
      {
           if (*it == 36)
           {
                it = b.insert(++it, '\\');
                it = b.insert(++it, '\n');
           }
           ++it;
      }
      myfile << "#include <stdio.h>" << std::endl;
      myfile << "#include <string>" << std::endl;
      myfile << "#include <iostream>" << std::endl;
      myfile << "#include <fstream>" << std::endl;
      myfile << "std::string a = \"\\" << std::endl;
      myfile << b << "\";" << std::endl;
      it = a.begin();
      while (it != a.end())
      {
           if (*it == 64)
           {
                *it = '\"';
           }
           else
           if (*it == 36)
           {
                *it = '\n';
           }
           else
           if (*it == 95)
           {
                *it = '\\';
           }
           ++it;
      }
      myfile << "void main()" << std::endl;
      myfile << "{" << std::endl;
      myfile << a << std::endl;
      myfile << "}" << std::endl;
      myfile.close();
 }

Hope you will enjoy.
Thanks.

Projecting a point on a Bézier curve

Hi All my readers.

In this post I'd like to show how to perform the projection of a point to rational cubic Bézier curve.

In fact, this procedure may not seem very useful for everyone. In the end, is there any sense to do Bézier curves in problems of geometric programming problems? However, if someone of the readers of this post had heard about such concepts as BSpline or NURBS, I am sure that this post will show them not only interesting but useful too.

Therefore, I will ask my readers to take my word - namely, any BSpline or NURBS-curve can be converted into one (or a series) of Bézier curves. Yes, do not be surprised. It is true. Therefore, knowing how to treat the problem with Bézier curves will always have the opportunity to consider the problems associated with BSpline or NURBS curves in a similar way.

Consider the rational Bézier curve of order 3. We will talk specifically about the Bézier curve of that order.

Rational Bézier curve of order 3 define by:

Denote a point that is projected onto this curve as G;

Next, we use one of the properties of Bézier curves: namely “the transfer of all control points of a Bézier curve by the same vector does not affect the shape of the curve" and give the origin of the system coordinates of the Bézier curve to a point G.

Thus, in view of transfer of control points of the curve, then we will use the following change of variables:

Give the equation of a Bézier curve to a polynomial form:

Make the following change of:

then the equation of a Bézier curve takes the form:

Define the derivative of this equation:

After the algebraic manipulations, we obtain the following equation:

where

Now we can return to the equation of determining the projection of a point on a Bézier curve.
Required equation has the form:

Or:

Now we can obtain a polynomial equation, whose solution will give us the answer to the question "Where are projected onto a point on a Bézier curve?"

where:

There are many ways to solve polynomial equations. In the case of this problem I used the «Bairstow-Newton» method, which allows us to be given up to find the real and complex roots of polynomial equations. This method worked well in terms of both speed and accuracy of search results.

After receiving the results of solving polynomial equations, only one correct result from the list of solutions is necessary to choose.

To do it, consider the following factors:

1. 
   «Bairstow-Newton» method allows us to find as real as imaginary roots. Thus, the roots of polynomial equations, which contain the imaginary part, cannot be useful.
2. Since the domain of definition of a Bézier curve lies between the values [0..1], those are real roots, which are not included in this area are not correct.
3. Because of solutions of polynomial equations obtained several real roots, then choose follows the root, which corresponds to the minimum distance between a point on the Bézier curve and the projected point.
4. If resulting solutions of polynomial equations obtained several real roots, and the distance between corresponding points on the Bézier curve and the projected point are equal, then this situation should be considered as a special (exceptional). For example if the projected point on the circle from the center of this circle.
   

Also, you should noticed that the described method is limited in its application. Thus, in the case of projecting a point to a non-rational Bézier curve, (when all the weights [w] are equal), then the coefficients a, b and c are equal to zero, and the polynomial equation transformed into the identity 0 = 0. Such a way before using the method described above should be checked for equality of weights with each other (or the vanishing of the coefficients [a],[b],[c]).

In fact, the case of projecting a point on a non-rational Bézier curve is a lot easier than projecting on a rational Bézier curve. Using similar steps, we can see that the degree of the polynomial equation of the projection points to a non-rational cubic Bézier curve is a fifth degree (rather than the tenth, as in the case of a rational curve).

Okay. For those experienced programmers who do not know why the computer was invented, I will cite the results of similar work for a non-rational Bézier curves of third order.

The equation of the non-rational cubic Bézier curve is:

Transfer the origin of the coordinates of the curve of the projected point:

Let:

And then a polynomial equation takes the form:

where:

Printable version of this post you can download here.

That's it.
Now you can enjoy the programming.

Thanks.

A bit about math and programming

Hi all of readers.

Often, programmers are faced with various mathematical problems. An example of such problems may be determining whether the choice of object to which your mouse, or sorting a list of numbers.

In most cases, available to programmers are prepared software libraries that provide various functions to facilitate the implementation of mathematical tasks.

Experienced programmers know about these libraries and use the appropriate functions provided by these libraries. But sometimes even experienced programmers will find themselves on an equal footing with inexperienced programmers, when none of the available libraries do not have the necessary functions to solve another math problem. In such cases, a paradoxical situation, when an experienced programmer can decide the outcome of which would be less effective than the decision taken by an inexperienced programmer.

Experienced programmer sits down to solve a mathematical problem as an ordinary skilled programmer. It can take one of the technologies of software development, or to create elements of the working process with the experience of architects and testers. The main mistake the experienced programmer in this situation is that to solve a mathematical problem he will try to come up not as a mathematician, but as a programmer (even if an experienced programmer).

I would like to remind all the programmers, the computer was not invented to solve mathematical problems, and to facilitate their decisions. If someone from the programmer does not know what I would like here to say that most of the algorithms that are programmed for computers that were discovered long before the invention of computers themselves. Work Chebyshev, to quickly implement the integration were open to them in the 19 st century. Work of Bernstein laid the foundations of the modern theory of splines were performed in the early 20 th century.

I'm not trying to say that in modern mathematics does not make new discoveries. Pierre Bézier and Paul de Faget de Casteljau continued development the theory of of splines in the mid of 20 th century . Carl de Boor, Edwin Catmull, Jim Clark, not only continue to develop the theory of splines, and are co-owners and animation studios creating computer graphics and animation. There are still many people who continue the development of mathematics.

But. These people do not rely on the power of modern processors. These people rely on the knowledge. Own knowledge and expertise of their predecessors. They will not allow self to assume that if some iterative algorithm implies the existence of the loop, and to exclude the probability of calculations error, just add the extra 200 iterations of this loop. Although 300 would be better. Probably better.

We have to admit that over the past few decades, the software industry is "rejuvenated". Among the students already there is a perception that programming - it's easy money. It is impossible not to agree that working at a construction site on a lot harder than to exercise the creative mind of a teenager at the time of programming. Surfing the net and not so tired as on construction sites, and moral satisfaction from showing their own creativity encouraged. Can you imagine what would have happened if the pavers brick walls of multistory buildings showed their creativity when laid another brick to the building? And with all this, the work of programmers costs not less than the work of the builders. It is obvious that in this situation as soon as the young man learned the basics of operating system it goes work to the IT-company. Getting a job, a young man begins to realize that his job is already claimed by another 5 connoisseurs of operating systems. And not to be dismissed from the company, a young man starts studying modern technology programming. Extreme Programming, Agaile, etc. Yes, this man becomes an experienced programmer, and it will not be replaced by another expert of operating systems.

It turns out that an experienced programmer is completely helpless against the objectives for which the computer was invented.

I suspect that now you want to tell me - "... the computer is intended not only for mathematical problems, and quite an experienced programmer would be useful for architectural design of client-server applications ...". And here I agree with you. Yes, an experienced programmer will use special patterns of application design. In his hands, fully justified and Extreme Programming and Agile. But. Please spend a little experiment. When you meet an experienced programmer, ask him - if he knew any planning theory of the critical path? Theory of the shortest path? Are there any known examples of problems that have no algorithmic solution? If your interlocutors know at least one of the above questions, then you're in luck. And you'll find that experienced programmers on a lot less than you thought. At the same few, how many skilled mathematicians less than people who know the multiplication table.

Thanks a lot.

Surface Reconstruction Tool for Blender3d. Version 1.2

I salute All and want to congratulate all about end of the winter and to warm spring.

And to continue the good news...

Since the first release passed one and a half months. During this time, people who seemed interesting our product, give us many valuable recommendations. We have accumulated information and return to continue the work.

And now, after six weeks of work, we're giving users a new version of Surface Reconstruction Tool.

Among the improvements that we've added a new version of Surface Reconstruction Tool includes:

1. To the library was included ability to specify the 3DM format version, where user can save the results. By default, Blender-script saves the 3DM-file is the third version of the format (instead of version 4 as it was before). This allows you to open saved 3DM-files using as application Ayam as native Rhino3d.
2. Approximation spline surfaces have become more sophisticated and effective. This will significantly reduce the volume of storage space required to represent the approximating surfaces.
3. For the new version of the library were developed, implemented and tested more sophisticated mathematical algorithms. In particular, it was identified and corrected the defect projection curves on the spline surface with a curved space of parameters, and also developed a fast and reliable analytical algorithm for projecting points on the spline curves. In general, these improvements have accelerated the algorithm several times.

As for the first version of the library, access interface to new version processed through a Python-script for the application Blender3d version 2.49. Ie to start using Surface Reconstruction Tool, Blender's users should download and install our package.

I am sure that our implementation of the library Surface Reconstruction Tool will not only interesting for its current users, but will be in demand for many new users.

We all means try to make our product useful and continue to ask all users to leave their wishes regarding the direction of its development and improvement.

For Download a latest version and more info about installation of Surface Reconstruction Tool, please go to the main post.

Thanks a lot and waiting for your feedbacks.