Optimization of Switch Keyboards
Xiao (Cosmo) Zhang, Kan Fang, Gregory Francis · 2013 · Proceedings of the 15th International ACM SIGACCESS Conference on Computers and Accessibility (Assets '13) · doi:10.1145/2513383.2513394
Summary
This short paper presents a method for optimizing the character layout of switch keyboards used by people with severe motor control difficulties, including those with locked-in syndrome resulting from spinal cord or brain injury. Switch keyboards work by scanning a cursor across rows and columns of a virtual keyboard; the user triggers a binary switch (via eye blink, puff of air, or similar minimal movement) to first select a row, then a key within that row. Typing speed is extremely slow — measured in characters per minute rather than words per minute — making layout optimization important. The authors reformulate the character placement problem as a mixed integer programming (MIP) optimization, where the objective is to minimize the average time to enter a character given a text corpus while keeping the error rate below an acceptable threshold. The time to input a character at grid position (j,k) is D(j+k), where D is the cursor duration per step. The formulation includes constraints ensuring each character occupies exactly one position and each position holds exactly one character, with certain keys (digits 0-9) fixed in traditional positions. The MIP approach using the Gurobi optimizer finds a guaranteed globally optimal solution in approximately 3 seconds on a desktop computer.
Key findings
The MIP algorithm is approximately 3,600 times faster than the previous hill-climbing algorithm used by Francis and Johnson, which required about 3 hours and could settle on non-optimal solutions. The optimization requires an accurate model of user error probabilities, which the authors model using a Gamma distribution fitted to experimental data from prior switch keyboard studies. Error probability at each grid position depends on the cursor duration and the user's timing ability — the model captures early responses (pressing too soon), correct responses, and missed responses (pressing too late). The Gamma distribution parameters (shape κ and scale θ) showed systematic patterns as a function of elapsed time and cursor duration, suggesting predictable user behavior. Two example optimized keyboards demonstrate the speed-accuracy tradeoff: one optimized for lower error rate (ε=0.30) and another for faster entry time (ε=0.50), each producing different character arrangements. The approach is flexible enough to accommodate various keyboard properties including different cursor paths, switch devices, and shortcuts.
Relevance
For people with severe motor disabilities, every keystroke has a high cost in time and effort, making keyboard layout optimization a meaningful accessibility improvement. This paper contributes a rigorous mathematical framework for a problem that was previously solved with heuristic methods. The 3,600x speedup is practically significant because it enables rapid exploration of design alternatives — clinicians and assistive technology specialists could potentially generate personalized keyboard layouts optimized for individual users' error profiles and text entry patterns. The Gamma distribution error model, fitted to real user data, provides a principled way to account for the variability in switch timing that characterizes users with different motor impairments. For AAC practitioners, the work underscores that even small improvements in scanning keyboard efficiency can meaningfully increase communication speed for users who may type only a few characters per minute. The approach could be extended to optimize other scanning interfaces beyond keyboards.
Tags: switch access · text entry · motor disability · locked-in syndrome · keyboard optimization · scanning · AAC · assistive technology · spinal cord injury