# Complementing Solutions to Optimization Problems via Crowdsourcing on Video Game Plays
## 2 State of the Art
### Human-Based Computation  
In human-based computation, computers delegate to humans calculation tasks that computers cannot yet solve [13]. For instance, interactive evolutionary computation is used for diverse applications such as graphic arts, speech processing, music generation, knowledge acquisition, robotics, and geophysics [1]. However, traditional algorithms, such as heuristic-based and genetic algorithms, perform poorly in these applications.  
In human-based computation, humans and computers can take two roles, selector or innovator. Depending on the assigned role for the human (H) or computer (C), computation methods are divided into four categories:  
* _H_C: The human is the innovator, and the computer is the selector. For instance, in computer-assisted design, human participants submit a design that is then evaluated by the computer, in terms, for example, of performance.
* _CH_: The computer is the innovator, and the human is the selector. For instance, an interactive genetic algorithm may produce a population of individuals, which is afterwards presented to a human, who is responsible for evaluating the fitness of the individuals.
* _CS_: The computer takes both roles; this approach corresponds to traditional genetic algorithms.
* _HH_: The human takes both roles. For example, in human-based genetic algorithms, humans provide candidate solutions and then evaluate them.  
In particular, in the experiments for scheduling and FLP (see Sections 3.2 and 3.3), we use a computer program to measure the total cost for crowd-sourced candidate solutions. These methods are classified into six dimensions [14]: motivation, quality, aggregation, human skill, participation time and cognitive load. They are defined as follows:  
* _Motivation_ answers the question: why do contributors choose to help?
* _Quality_: answers the question: how does the system cope with fraud?
* _Aggregation_: the question: How does the system combine local computations made by individual participants to solve the global problem?
* _Human skill_: answers the question: what is the special skill that humans possess that makes them valuable in the system?
* _Participation time_: answers the question: what is the minimum amount of time a user must invest to participate?
* _Cognitive load_: answers the question, how much mental energy does the task take?  
Later on in the text, we will demonstrate that we use video games to model optimization problems to help users to feel _motivated_ to solve such problems. _Quality_ is enforced by having controlled playtests. For _human skills_, the games aim at leveraging human spatial intuition. Levels are kept short to decrease the _participation time_ per dataset, encouraging the player to spend more time overall. In this way, we aim to avoid burdening the user with a substantial _cognitive load_.  
Human-based computation has a vast range of applications in diverse areas. For instance, human-computer optimization has been explored through interactive graphical interfaces, specifically to address the capacitated vehicle routing with time windows problem [2]. Studies have also evaluated the optimal methods for strength aggregation of human and computer synergy [15]. In many cases, this technique has been used for military purposes; for example, cooperating teams consisting of humans and computer agents are more effective than a team of only humans in military command and control tasks [16]. In other application domains, we find a combination of both strengths (genetic algorithms and human intelligence), including information retrieval systems [17] and object-oriented software design and development [18].  
The above-mentioned research has drawbacks compared with video games. First, users need training for expertly guiding an algorithm, which reduces the potential use of the population at large. Second, a substantial cognitive load is required; thus, users must anticipate the next step of the computer.