Gilles Bailly, Antti Oulasvirta
Menu interfaces for command selection first appeared in 1968 with the AMBIT/G system and were later popularized in the Xerox Star in 1981. Today, menus are among the most commonly used user interface types. The design of menus thus strongly affects the usability and user experience of interactive computing. Evidence for their relevance is the fact that menu designs of important applications have at times received wide media publicity. Recent examples include the iPhone application menu, the ribbon of Microsoft Office, the privacy settings panel of Facebook, and the application launch menu of Microsoft Metro.
Here we discuss a holy grail in user interface design: the possibility of designing an optimal menu. The "optimal menu" is the particular design that best meets all usability goals while respecting the relevant constraints. We present menu design as an optimization problem and discuss five challenges that researchers should address in relation to this goal.
Despite the apparent simplicity of menus as an interface, designing great menus is very challenging solely from a combinatorial perspective. Consider the problem of how to assign n commands to a menu. The number of alternative designs grows exponentially 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 medium-size 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.
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 .
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.
Menu design can be approached similarly: The problem is how to organize items into a hierarchy . 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.
Menu design entails much more than just ordering commands in a hierarchy. Implementing better optimization algorithms (e.g., simulated annealing) is insufficient. For this reason, menu-based interaction has attracted a lot of research attention and resulted in a number of interaction techniques, user studies, and models. To expand the scope of optimizable menu designs, we need to start to address them. We identified five challenges, which we discuss here.
Challenge 1: Design space. As mentioned earlier, the search space of menus is immense because it comprises numerous dimensions, such as the item dimensions, visual cues, and menu layout, but also hotkeys, gestures, temporal considerations, and so on. Unfortunately, not all main dimensions of this design space have been characterized. Besides hierarchical command assignment, the design space of existing major menu techniques has not been defined.
The lack of a problem definition is of course natural for a new research topic. Although research in menu design began several decades ago, we think that it is still in its early stages due to its inherent complexity and the constant evolution of techniques. The possibilities and decision variables are just starting to be explored.
Thus, the first major challenge we see is to analyze the features of existing menu systems to identify the most important design variables (e.g., geometric, visual cues, semantic, etc.) beyond the ordering of items. This will help target work to the most pertinent menu types and will guide work on developing predictive models.
A related question is to which novel techniques to first expand. Almost 100 novel visual menus have been proposed the past few decades (www.gillesbailly.fr/menua/). While for some tasks they can be more efficient, they add new trade-offs. For instance, Figure 3 shows examples of two designs with different appearance and interaction properties. They are based on circular layout and gestural interaction, reminding us that menu organization need not be systematically linear but can also be circular. Such menus have several interesting properties for selection time and spatial memory.
To prioritize the design space, we need to better understand existing menu techniques, in particular which features offer the largest positive effects to users. To do that, it is necessary to conduct empirical studies of menu behavior. However, the difficulty is that the experimental designs tend to quickly get complex because there are subtle interactions among properties of even very simple menus .
Challenge 2: Multiplicity of objectives, users, and constraints. Menu designers typically have multiple objectives. They want not only to improve speed, but also to consider errors, discoverability, aesthetics, learnability, comfort, and so on. These latter objectives are less studied. Moreover, in a real design case the objectives can be contradictory. For example, fast, precise menus may be difficult to learn.
It is thus necessary to explicitly deal with complex trade-offs during optimization. This is technically challenging because the search process becomes more complicated. It also requires designers to be able to define their objectives more clearly. It may be that it is easier to simply try to design the menu than specify all the constraints, objectives, and assumptions to a computer.
This also calls for new ideas in how to represent users in code. Previous work in menu optimization has assumed a "generic user" represented as a statistical distribution. It has disregarded constraints and nuances arising in different contexts and user groups.
However, there is also an unavoidable chicken-and-egg problem in task definition: How can we predict how a menu will be used and by whom? If successful, a design will attract new users, change behaviors, and extend to contexts that were not known at design time. A challenge is to find ways to optimize for "robust" designs that are not as dependent on particular use characteristics.
Challenge 3: Predictive models of user performance. Optimization methods evaluate the quality of a menu based on a predictive model. A predictive model is the engine of the approach: It allows menus to be evaluated without empirical studies. However, the scope of these evaluations depends on the available predictive models.
We recently proposed a novel analytic model of menu performance at CHI'14 . It assumes two visual search strategies, serial and directed, and a pointing subtask. It captures the change of performance with five factors: menu length, menu organization, target position, absence/presence of target, and practice. One novel aspect is the model is expressed as probability density distribution of gaze (when and what items users are looking at), which allows for deriving total selection time.
While it is one of the more advanced predictive models of menu performance, we are still far from proposing a model mature enough to avoid empirical studies. Indeed, existing predictive models are limited to a small subset of possible menu designs and menu properties. For instance, they do not cover hotkeys, gestures, or semantics, major factors of performance.
A main challenge will be to develop predictive models that better cover existing features and then expand to advanced menu techniques such as those in Figure 3.
Unfortunately, in contrast with the first challenge, there is significantly less work on predictive models of 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  used a genetic algorithm and considers item frequency with strong assumptions about the hierarchy. We recently proposed a hybrid algorithm  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 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 .
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 allowing them to delegate combinatorial subproblems to an optimizer that should solve them rapidly enough not to disrupt the design process.
At UIST 2013 we proposed MenuOptimizer (Figure 4), a tool for designing menus integrated into Qt Designer, a widely used interface builder. It supports the design of static (non-adaptive) hierarchical menu systems, a type of menu that is common in most desktop applications today. Two design scenarios are supported:
- In updating existing menu systems, user behavior is partially known from, for example, logs or interviews.
- Sketching novel menu systems involves assumptions about usage and objective, which can change during design.
Both scenarios are supported with the same functionality: Designers can edit a menu by adding, removing, renaming, and moving commands in it. Importantly, every edit updates the optimizer to work with the present menu design.
The optimizer provides suggestions at item level (optimal placement for a clicked item), menu level (improvements made by moving items), and the menu-system level (menu templates). Designers can specify and change their assumptions about use and users by editing distribution graphs directly. To direct the optimizer, designers can also change the objective function by setting the relative weight of user performance, consistency (expectations as to item locations), and edit distance to the present design. With multiple optimization objectives, the optimizer's suggestions are plotted in real time on a Pareto front plot. Designers can also lock items, which restrict the optimizer's search space.
A user study showed that novice designers generate designs that equally satisfy them but with 38 percent less editing. However, the study was limited to students with no design background, and several questions remain open for future work.
Menus and, more generally, command selection, are an active and important field of research that goes beyond traditional GUIs to consider novel modalities such as gestural interaction. Previous papers on menu interaction have not sought to formulate the exact design space, constraints, objective function, and the process of search. We believe that research in menus could benefit from a more systematic approach.
The optimization approach invites researchers and designers to characterize the design space of menus, explicate assumptions about users, formulate testable hypotheses that are based on prior studies, build predictive models of performance, and, finally, develop optimization methods robust enough to deal with uncertainty.
While all the directions we have outlined should be investigated, we think the lack of accurate predictive models of menu performance is the main bottleneck to optimization. Numerous menu techniques have been proposed and numerous user studies have been conducted; it is now time to capitalize on these results and integrate them into predictive models.
Gilles Bailly is a senior CNRS researcher at Telecom ParisTech. He is working on command selection, including traditional GUI and gestural interaction. firstname.lastname@example.org
Antti Oulasvirta was a senior researcher at Max Planck Institute for Informatics and Saarland University at the time of this writing. He is now an associate professor at Aalto University in Helsinki, Finland. He works on computational user interface design and human factors. email@example.com
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.
©2014 ACM 1072-5220/14/07 $15.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2014 ACM, Inc.