That said, there are at least a dozen algorithms for autotuning. They
fall into two basic methods (relay and step), but the parameters they
generate can be quite different due to the different desired responses
(e.g. "fastest to reach a certain error after a step change in setpoint"
vs "little or no overshoot after a disturbance", etc.). You have to be
clear about what you're trying to do before you bother trying to tune it.

Large delay and overshoot are common to heater control loops. Placing
the sensor as close as possible to the heater can help, but then you
might not be measuring the thing you want hot. I just had a (maybe)
similar problem that included a requirement for a smooth ramp of the
temperature. That led me to close the loop around the slope (calculated
with an extremely simple FIR filter) during ramping. The slope-loop
worked far better than trying get the temperature-loop to follow a
ramping setpoint.

(thanks for the plug).

I'll bet there's rockets out there with temperature loops.

Autotune is for when you're selling a shrink-wrapped controller that has
to work for anything -- and autotune is often considered to be a good way
to get the tuning in the ballpark so that a human can get involved and
actually make it work right.

Unless you need to adapt to a variety of different, unexpected boiler
combinations -- that don't change as the boiler is operating -- then
there's not much value in autotune, IMHO.

Any sort of tuning exercise involves making some assumptions about the
system you're controlling, poking it with some excitation, seeing how it
responds, then formulating a controller for the thing.  In some cases you
have a step in there where you create a mathematical model of your plant,
in others you don't.  The process is the same with autotuning, except
that you hope to have a machine doing the tedious bits for you, instead
of you having to run around the world tuning up coffee makers.

The Aostroem-Haggluend method never develops that explicit model, nor
does it work with just any old excitation -- it just pokes the system in
a specific way, extracts some parameters that aren't really closely
related to what control theorists are used to (but which are practically
quite useful), then gets PID tuning parameters from those measured system
parameters.

Your problem is that you're not really poking the system in quite the
right way, so the Aostroem-Haggluend method is breaking down for you.

Clearly there are two ways you can go:  one, poke the system the _right_
way, and two, abandon the A-H method.  You _could_ use excitation and
response with more 'university' style adaptive control methods to derive
a system model and develop a controller -- this is not a bad way to go if
you're comfortable wrangling the math.  Or you can try to fix your
excitation, or you can use the open-loop A-H method of data collection.

Have you tried turning your drive way down and adding some substantial
hysteresis to your relay function?  I.e. instead of the relay being a
static rule that says "output = on if above threshold, output = off if
below", you make the rule say "go from off to on if above a low
threshold, go from on to off if above a high threshold".  Make the two
thresholds far enough apart (5 or 10 degrees?) to insure you capture good
data, then find a value for your drive that seems to give good results
for a variety of boiler sizes.

Or you can use the open-loop A-H -- this is actually the original method
that Ziegler and Nichols used (as far as I know).  In it you start from
steady state, make a step change in the drive, and look for a ramp
response in the output.  You deduce gain and delay from the slope of the
ramp and the delay from that ramp to an ideal 'immediate' ramp.  In your
case you probably want to take off from a fairly hot temperature, so you
may want to get up to your launch temperature with a really, really slow
integrator-only loop or some other means that'll get you at a steady
temperature safely.  Once you're at a constant temperature and drive, you
can step the drive and start collecting data points on the response.

Or hire me :-).

Any sort of tuning exercise involves making some assumptions about the
system you're controlling, poking it with some excitation, seeing how it
responds, then formulating a controller for the thing.  In some cases you
have a step in there where you create a mathematical model of your plant,
in others you don't.  The process is the same with autotuning, except
that you hope to have a machine doing the tedious bits for you, instead
of you having to run around the world tuning up coffee makers.

The Aostroem-Haggluend method never develops that explicit model, nor
does it work with just any old excitation -- it just pokes the system in
a specific way, extracts some parameters that aren't really closely
related to what control theorists are used to (but which are practically
quite useful), then gets PID tuning parameters from those measured system
parameters.

Your problem is that you're not really poking the system in quite the
right way, so the Aostroem-Haggluend method is breaking down for you.

Clearly there are two ways you can go:  one, poke the system the _right_
way, and two, abandon the A-H method.  You _could_ use excitation and
response with more 'university' style adaptive control methods to derive
a system model and develop a controller -- this is not a bad way to go if
you're comfortable wrangling the math.  Or you can try to fix your
excitation, or you can use the open-loop A-H method of data collection.

Have you tried turning your drive way down and adding some substantial
hysteresis to your relay function?  I.e. instead of the relay being a
static rule that says "output = on if above threshold, output = off if
below", you make the rule say "go from off to on if above a low
threshold, go from on to off if above a high threshold".  Make the two
thresholds far enough apart (5 or 10 degrees?) to insure you capture good
data, then find a value for your drive that seems to give good results
for a variety of boiler sizes.

Or you can use the open-loop A-H -- this is actually the original method
that Ziegler and Nichols used (as far as I know).  In it you start from
steady state, make a step change in the drive, and look for a ramp
response in the output.  You deduce gain and delay from the slope of the
ramp and the delay from that ramp to an ideal 'immediate' ramp.  In your
case you probably want to take off from a fairly hot temperature, so you
may want to get up to your launch temperature with a really, really slow
integrator-only loop or some other means that'll get you at a steady
temperature safely.  Once you're at a constant temperature and drive, you
can step the drive and start collecting data points on the response.
        <end restored context>

I do not believe that your temperature response to heat input is as
nonlinear as you think it is.  This is partially because in my experience
thermal systems themselves are pretty linear (and therefore act the same
in both directions), and partially because looking at your graph I don't
see any true signs of underdamped behavior -- I see a system that is
responding to asymmetrically, yes, but it looks like a linear response to
an asymmetrical input.

To hazard a guess, I'd say that one way or another when you command a 6%
drive to your heater you're getting 1/4 as much heat as when you command
a 12% drive -- almost as if you're commanding a steady voltage to the
heater, or you're commanding the timing on an SCR drive, or something.  
The response that you're getting looks very much like the response you'd
expect with a 3/4 'on' drive, and a -1/4 'off' drive, which is consistent
with an ambient cooling at your set point temperature that's 1/4 as
strong as the heating you get when the thing is on.

If you're really exciting a nonlinearity in the heating system you want
to find it and characterize it now, rather than struggling with
mysterious voodoo code for the rest of your career.

My recommended method would be to do it by analysis, but since you're
already set up for measurements, making a chart of heater commands vs.
final temperature, from 0 up through whatever gets to the maximum water
temperature you can tolerate (I'd go for a gentle simmer, unless that
causes some non-reversible safety mechanism to go off).  If the chart
shows a curved line you have a nonlinearity in your drive that you need
to deal with (otherwise you have a nonlinearity somewhere else).

Ultimate gain can be computed just fine, it doesn't matter much what output
steps are used during autotuning. The  Åström/Hägglund result is always ~25%
Kc gain and that works fine and seems right; manual tuning suggests a
similiar value.

And what is "heat", IOW how do you control the heater - phase angle,
full wave? As Tim wrote, there might be a nonlinear function. And if
you control a SCR without mains synchronisation, you might get huge
uncertainties for low power values.

Did you notice that there is a word that appears many times in my
description above?

Want to guess what the word is?

That word is "linear".

A system with a time delay is not described by linear differential
equations.  Strapping a PID controller onto it is bad math.

One of the more classic examples is a shower or an industrial process that
mixes fluids of varying temperature and the sensor is located substantially
downstream from the mixing value.  This is a pure time delay.  My shower at
home is like that.  I turn the water a little hotter.  Nothing happens.  I
turn it a little more hotter.  Nothing happens.  Then I turn it a little
more hotter.  Then the wave of hot liquid hits me and I scream in agony.

Over time, I've adapted to my shower.  I don't burn myself anymore.

I think the control algorithms you want to use for a system like yours fall
outside the range of PID.  I'm sure there is a body of theory that covers
it, but I don't know what that is.

I would heat the system full bore for a fixed period of time, then stop and
wait to see how the temperature catches up.  And work from there.

The best control strategy for that system isn't going to be PID.  That is a
non-linear system.

http://en.wikipedia.org/wiki/PID_controller

<QUOTE>
Another problem faced with PID controllers is that they are linear. Thus,
performance of PID controllers in non-linear systems (such as HVAC systems)
is variable. Often PID controllers are enhanced through methods such as PID
gain scheduling or fuzzy logic. Further practical application issues can
arise from instrumentation connected to the controller. A high enough
sampling rate, measurement precision, and measurement accuracy are required
to achieve adequate control performance.
</QUOTE>

I don't know what the best control strategy is, but it ain't PID.

Systems with delay can be perfectly linear, as well as time invariant --
they just can't be described by ordinary differential equations with a
finite number of states.

To be linear, a system only needs to satisfy the superposition property.  
A delay element satisfies superposition just fine.

And while a PID controller may not be the theoretically best controller
for a system with delay, in many cases it's not a bad choice at all.  PID
controllers can and will give perfectly satisfactory service with plants
that have significant delay.  The thousands, if not millions, of PID
controllers in mills and factories around the world that are controlling
plants whose responses are dominated by delay certainly belie any
declaration that the PID controller isn't a good choice to control a
plant with delay.

None of the above is intended to minimize the difficulty in analyzing and
designing a truly optimal controller for a plant with pure delay --
that's an exercise that can make your brain hurt, and fast.  And nothing
of the above is intended to chase you away from taking plant delays more
directly into account if a discrete-state controller such as a PID won't
let you eke the performance that you need out of your plant.  

But in the absence of significant nonlinearities or time varying behavior
you can use all the analysis tools that are suitable for linear time
invariant systems on a system with delays just fine.  You can do good
design work, without ever having to explicitly write out the differential
equations, much less solving them.

So if you don't want to get lost in Mathemagic Land searching for
performance that isn't necessary for your product's success, a good ol'
PID controller may be exactly the optimal controller -- in terms of
adequate performance and reasonable engineering time -- even if it
doesn't satisfy any egghead academic measure of "optimal" for the
particular plant you're trying to control.

I might have missed something significant here.

It is my assumption that a system with a pure time delay is inherently
non-linear.

Let's take my shower example with a pure delay in the pipes ...

With no delay, you can just say that

   Temperature(t) = Valve_Position

or perhaps with a little thermal mass thrown in you can say that:

   d Temperature / dt = K * (Valve_Position - Temperature)

where of course I'm assuming that valve position and water temperature are
the same thing.

The first is I think a 0'th order linear differential equation and the
second is a 1st-order LDE.

But how would you linearize a system with a pure time delay, exactly?

The shower example with a pure pipe delay between the shower valve and my
skin is fine.

Any delay pushes a servo system toward unstable. That's not a linearity
problem.

Auto tune works great when the plant matches the model AND the system
is properly excited.  If not then auto tune doesn't work so well.  Are
the water levels in the boiler constant?  If not can the water level
be detected?  Obviously the temperature will rise more slow or not as
fast if the boiler is full of water as opposed to being empty.

Does the tuning need to be better for a coffee machine?  Manual tuning
should be easy enough.

When I get serious I prefer to make a model of the system.  The
excitation requires a few steps in the control output.  The steps
should be big enough so the response is clearly more significant than
the noise.  The dead time should be clearly visible and the same goes
for the rise time. One can often get the plant gain, time constant and
dead time by inspection.  If not then one must log the control output
and the response.  Then one fits a FOPDT or SOPDT model to your coffee
machine.  I do this using Scilab's optim or lsqrsolve.  Then one goes
to the www.controlguru.com site and uses the IMC, internal model
control, equations there for computing the gains.  For a FOPDT
Kc=t1/((tc+dt)*K)
ti=t1
Where:
Kc is the controller gain.  It should have units of %output per
degree.
ti is the integrator time constant which is usually in minutes.
t1 is the plant time constant
dt is the dead time
K is the plant gain.  This has units of degree per % control output.
tc is the closed loop time constant.  tc is made smaller for more
aggressive tuning and longer for more conservative tuning.  The value
for tc is dependent on the plant time constant and dead time.  The
formula for tc on on the www.controlguru.com site.

You can see from the equation that the dead time reduces the gain.
Also, if the plant gain changes due to the water level then K will be
a function of water and the controller gain will then be modified as a
function of water level.
Kc=t1/((tc+dt)*K(WaterLevel))

I would start here.  Once the plant gain, time constant and dead time
are know there are other options.  On the www.controlguru.com site
there are formulas for adding the derivative time constant td.   One
can also implement a Smith Predictor.   A Smith Predictor isn't that
hard to implement.  The hard part is finding the plant parameters.

I talked to someone else on the phone about making a high end coffee
or espresso machine a few months back.  Our product was gross overkill
but would have made a nice research tool.

Take the system y = h(x, t) ==> y(t) = x(t - td).  Testing this with
superposition we get

y1(t) = x1(t - td),
y2(t) = x2(t - td),

y1(t) + y2(t) = x1(t - td) + x2(t - td)

which is both h(x1, t) + h(x2, t) and h(x1 + x2, t) -- therefore the
system is linear.

Note that as Jerry points out a shower isn't necessarily a linear system,
unless your shower valve insures a constant flow and the pipes don't have
any turbulence.  Let a vastly simplified version be

y(t) = x(t - kd * x(t)),

(this doesn't capture the delay behavior in even a perfect pipe)

Then we try superposition:

y1(t) = x1(t - kd * x1(t)),
y2(t) = x2(t - kd * x2(t)).

This does _not_ equal the system output to the sum:

ys(t) = x1(t - kd * (x1(t) + x2(t))) + x2(t - kd * (x1(t) + x2(t))).

so this system isn't linear -- but not for the reason that you thought.

For that matter, how about modeling the whole range of coffeemakers that
you expect (or that you're willing to warrant the device as working).  
Then see if you can get reasonable performance with just one tuning
setting*.  Then instead of telling the customer he can mess around with
autotune, you can tell him he can just plug & play.

* I've done this on blood pressure monitor; we expected to need four
different tunings for the whole range of cuffs from 'premie arm' to 'fat
guy thigh', and ended up needing just one.

Control problems seem to attract overly complicated solutions; so one of
the things a responsible control engineer always needs to do is to ask
"is there some bone-head simple way to do this that will be adequate".

Of course, if "PID control" has become a sales point, then you'd better
have it in there.

* I may do so wistfully if work were slow, but I'd still do it.