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.