Menu design can be approached
similarly: The problem is how to
organize items into a hierarchy [ 1].
The ordering of commands in menus
is an instance of a known problem in
optimization called the assignment
problem. Given a quantitative predictive
model of menu performance (e.g., [ 2,
5]), the goal is to identify the design that
maximizes users’ selection performance.
The same black-box optimization
methods used in the keyboard example
can be used to solve it.
Optimization methods require five
steps:
• Characterize the design space by
defining decision variables
• Define constraints
• Define objective function
• Represent problem in code
• Implement and run a suitable
optimization method.
In the context of menus, the
optimizer starts from an unorganized
list of commands or a well-known
menu. In every iteration, it generates
a new menu by transforming the
previous best-known menu (swap of
items or group of items), evaluates user
performance by consulting a predictive
model and the distribution of usage
(what users do), then decides whether
to generate a novel menu depending on
whether the new menu is better or worse
than the best one. Figure 2 illustrates a
menu of 50 commands that have been
generated in 15 minutes.
DOES IT SCALE UP TO REAL-WORLD DESIGN PROBLEMS?
Menu design entails much more than
just ordering commands in a hierarchy.
Implementing better optimization
algorithms (e.g., simulated annealing) is M
as n increases. Figure 1 shows a linear
menu with 10 items. There are 10! =
3,628,800 possibilities to organize
them. With the possibility of menu
hierarchies, the problem size increases
even further. For 50 items, a mediumsize hierarchical menu, the search
space is 100! ≈ 9 x 10157. However, real
applications comprise hundreds (e.g.,
browsers) and even thousands (e.g.,
CAD tools) of commands. In addition
to command assignment, designers
must consider command names and
features like hotkeys or icons. If one also
considers nontraditional menus, the
design space is immensely larger.
Menus also must meet several
simultaneous design goals, such as
efficiency, learnability, aesthetics, and
so on. They must respect constraints
imposed by the application, and possibly
its previous versions, the platform
(desktop, smartphone, smart watch,
etc.), as well as those of diverse user
groups and contexts of use.
Empirical research suggests that
menu design is challenging [ 1, 2, 3]. As
designers cannot explore the entire
space of possible interface designs,
they use heuristic approaches, such
as placing frequently used items at
the top of a menu or grouping items
by similarity. This may be efficient for
small problems but it does not scale up.
When generating alternatives, novices
are likely to get stuck in a local search
space. Although expert designers can
generate a handful of solutions to hard
design problems, they cannot examine
all promising solutions either.
What if there were a method to
somehow produce menus that guarantee
optimality, or even a high chance of
finding the optimum? Not only could
this save enormous amounts of time
and human effort invested into menu
design, but it could also fundamentally
transform the work of designers.
Instead of manually trying out different
organizations and properties, the task
would be to define goals, constraints,
and assumptions to a computer. The
ability to claim that a design is optimal
(or close to optimal) would help
designers convince others of the quality
of their design. As no knowledge of
human factors would be assumed, even
novice designers could design great
menus.
In the rest of the article, we discuss
recent advances in using optimization
methods for menu design and explain
the most difficult challenges in relation
to this goal.
SOLVING COMMAND
ORDERINGS WITH
OPTIMIZATION METHODS
The main area in HCI where
optimization methods (e.g., local
search, simulated annealing, genetic
algorithms) have been used is virtual
keyboard design. The optimization
problem consists of organizing 26
letters to minimize typing time for a
language. Fitts’ Law is typically used
as the objective function. If the size of
buttons is not considered, the problem is
simply to find the design that minimizes
the average finger-travel distance. The
best-known outcome is the Metropolis
keyboard for PDAs [ 4].
T
The ability to claim that a design is
optimal (or close to optimal) would help
designers convince others of the quality
of their design. As no knowledge of human
factors would be assumed, even novice
designers could design great menus.
Title
Name
Icon
Position
Width
Height
Ctrl Hotkey
N
u
m
b
e
r
o
f
i
t
e
m
s
Figure 1. Even
seemingly simple
linear menus
involve multiple
features that
designers must
decide on. The
result is there is
an exponential
number of ways to
organize the items,
in this case more
than 10! = 3,628,800
possibilities. More
sophisticated
menus also involve
features such as
hierarchies.