How do I select the best configuration for a known workspace, load and task?

Question

Given workspace constraints, load and task to be done, how do I select the best configuration of my robot? How do I select between a cartesian or Scara robot for instance? How do I select a manipulator? How do I determine how many axes that I need?

Most of what I have seen is based on experience, rules of thumb and readily available standard devices, but I would like a more formal answer to quantify my choice. Is there some technique (genetic algorithm?) which describes the task, load, workspace, budget, speed etc. and rates and selects an optimal robot configuration or maybe even multiple configurations? How can I be mathematically ensure I ultimately chose the optimal solution?

The only thing I found online was a thesis from 1999 titled Automated Synthesis and Optimization of Robot Configurations: An Evolutionary Approach (pdf, CMU-RI-TR-99-43). It is a synthesis and optimization tool called Darwin2K presented in a thesis written by Chris Leger at CMU. I am surprised no one has updated it or created a tool similar to it.

To provide some context for my question, we are developing a robot to assist the elderly with domestic tasks. In this instance, the robot identifies and picks food items from a previously stored and known location. The hand opens the package and place it in the oven. The pick and place locations are fixed and nearby so the robot is stationary.

Answer 1

I'll just show why heuristics and experience are relevant in this problem by showing that is nearly impossible to solve optimally. Note, genetic algorithms cannot necessarily always solve a problem optimally, they are just another heuristic-based search.

1. Defining the manipulator Let's simplify things. According to Craig 2005, robot manipulators can be reasonably decomposed into prismatic and revolute joints. Each such joint is one degree of freedom in your input space. That is, a hand on the end of the robot can be specified by a vectors of length $N$, where the robot has $N$ joints of types prismatic or revolute. OK. we can now specify the manipulator position. The set of all possible configurations is called the configuration space. Let's assume we know this completely, as you stated.

2. Defining the task Let's assume that the task consists of moving the manipulator through a series of stages. For example, suppose the manipulator must drill 30 holes in a sheet, then place the sheet on a pallet, or whatever. Since we have the manipulator positions as a vector of length $N$, we can specify each task as a desired position, $X_1, X_2 ... X_M$ for task length $M$. What we've just done is specified a series of points in the configuration space which we defined above.

OK break time to verify the terminology if anyone is confused. Watch this video. The robot has 3 degrees of freedom (each rotation point), so the configuration space is all sets of 3 real numbers (in the range 0-$2\pi$, corresponding to the 3 angles of the 3 revolute joints). The task is to cause the end-effector (the pen) to visit all points on a circle. If this isn't clear, I can clarify.

1. Defining the cost Now that we know the configuration space and the series of points, let's talk about cost. The cost is typically the force exerted by the joints. So suppose (a huge assumption), that we can model this directly as $f(X_1,X_2)$, a function which returns the energy to go from state $1$ to $2$. If we're lucky, the function is a metric. If not, it defines a complete graph with $N\choose 2$ links (the cost to go from any state to any other state).

2. Defining the problem Find the optimal ordering of manipulator states and paths between manipulator states to minimize the cost, $f(X_i,X_{i+1})$ for each sequential task $i$. This is clearly a Travelling Salesperson Problem (See: TSP). Since TSP is NP-Hard, this problem is NP-Complete*.

What does the above mean? Well, for a given robot design, we have arrive at an NP-Complete problem to derive the optimal task sequence: movements, manipulator positions, etc. To optimize the robot itself is even more difficult. First, we have to search over all possible robot configurations (subject to what??), and for each, solve an NP-Complete problem. The best result is the robot configuration we want. For a small-dimensional workspace (say one joint, or $N=1$), and a simple task (say a small number of possitions like $M$=3 or so) this is not too difficult. However, in general, $N$ is unbounded, and $M$ is large.

Even if there is some ordering property on $N$, like a robot of 2 joints is better than a robot of 1 joints, etc, you still have to do $\log(n^\star)$ TSP solutions, where $n^\star$ is the perfect number of robot joints. Remember a TSP solution is incredibly difficult to solve optimally. This gets even worse if we want to say "Well, what about two arms with two joints versus one arm with four joints." I don't want to talk about that complexity ... It's exploding.

So, because you can't solve it perfectly using computers, people pay big money to have an experienced engineer do it for them. Win-win?

*well not really, but along the way we show a polynomial time reduction, so it sorta counts.

---

EDIT What we actually did here was describe the algorithm to select the optimal manipulator design. That should answer your first question. However, it is computationally infeasible to run on a computer, and so heuristics and other design choices are necessary, that should answer your second question.

What this means: We're also having this problem in our lab. Manipulators are very expensive, and we want one that is just good enough to perform some task. What we converged to was an extremely minimal set of joints for each task, instead of one large and capable manipulator for all tasks. My advice: I would design the robot based on budget and programmability, rather than trying to make a claim about the optimal configuration.

Answer 2

The answer by Josh is excellent but here is an industrial perspective.

In my experience, industrial robot design always starts with the requirements of the load and the design decisions ripple back from there.

You need to look at the size, shape and weight of the object (or objects) to be manipulated, how fast you need to move the object and how accurate the control needs to be. Then you can marry this with details of how the object is to be moved. At each stage you work out the worst case and give yourself a little wriggle room in case something doesn't perform up to spec.

Although you can attempt to use average case rather than worst case, it is risky to do so. Just because you think that no-one will ever drive both axis A and B to it's full extent at the same time, doesn't mean that someone won't accidentally try to do it, and if arm AB isn't able to carry the weight in this configuration, it could be dangerous, both to the machine and any people nearby.

If you are lucky, your mechanical designer has access to not only CAD tools, but also CAE tools such as Finite Element Analysis, but many small, specialist robotics firms can't afford expensive CAE systems and rely entirely on experience, judgement and judicious over-engineering.

Even where a company does have access to CAE tools, they will often be used sparingly. Since it is infeasible to simulate the whole of a complex system in one go, subsystems are instead analysed independently of each other.

Ultimately as with many areas of expertise, there is no one-size-fits-all robotics solution. Every requirement has implications on a whole bunch of design decisions, and the effectiveness of the system is limited by the intersection of those design decisions.