assumptions about user actions. They should be able to accept uncertain or “fuzzy” design knowledge.

Challenge 5: Interactive optimization. Given the challenges we have outlined, it is clear that the design of menus cannot yet be entirely delegated to the system. To overcome this limitation, we recently proposed an optimization method for interactively assisting menu designers with an optimizer in the loop [ 1].

We argued that menu design depends on human judgment, because current predictive models cover only a small subset of decision variables and objectives. Additionally, the constraints that govern the design process may be ill defined or subjective.

The key challenge is how to
support designers’ abilities to cope
with uncertainty, define constraints,
and recognize good solutions while
menu performance. Only a handful of
models have been proposed over the
past few years, and they mainly focus
on a single response variable, such as
menu selection time. Moreover, not all
models are suitable for optimization.

Optimization relies on very fast evaluation of a menu, as there is an immense design space to explore.

This rules out full-fledged cognitive simulations such as EPIC, GOMS, or ACT-R, although there are linearized simplifications such as KLM.

Challenge 4: Optimization methods.

We have argued so far that optimization critically depends on a well-defined design space, realistic objective formulation, and accurate predictive models.

Only two optimization methods have
been proposed specifically for menu
systems. The first [ 6] used a genetic
algorithm and considers item frequency
with strong assumptions about the
hierarchy. We recently proposed a
hybrid algorithm [ 1] that first uses a
local search algorithm but with more
time also uses an ant colony optimizer.

On the one hand, the local search algorithm can produce reasonable local optima very quickly, helping the designer to get an idea of the search space. The ant colony algorithm, on the other hand, operates in the scale of minutes to hours. It makes fewer assumptions about the search space and thus has a chance of finding the global optimum. But it is significantly slower. Our solution was tested with designs of up to 50 commands, and solution times were as long as 15 minutes.

A key challenge will be to develop methods that scale up to thousands of commands and can handle more complex multi-objective tasks. The present methods also depend on explicit

Figure 3. Advanced menu techniques use different layouts and input: Flower menu (left) and multitouch menu (right).

(a) (b)

File search
New
Open
Close
Properties Send to
Quit
Page setup
Print
Print previe w
Save Html
Save

Save

Figure 4. MenuOptimizer assists in the design of menus: While the designer edits the menu, a model-based optimizer updates itself to provide feedback and suggestions.

Designer

Item feedback indicates the frequency (line width)
and user performance over time (color gradient) Hotkeys and separators are
automatically assigned

Optimizer

Item placement to improve
performance is suggested
Designers can lock items together
to accelerate optimization
Designers can normaly edit items
(move, delete, rename, etc.)