# Genetic-based Constraint Programming for Resource Constrained Job Scheduling

Su Nguyen1 Dhananjay Thiruvady2 Yuan Sun3 Mengjie Zhang4

( 1School of Accounting, Information Systems and Supply Chain, RMIT University
<EMAIL_ADDRESS>
2School of Information Technology, Deakin University
<EMAIL_ADDRESS>
3La Trobe Business School, La Trobe University
<EMAIL_ADDRESS>
4Centre for Data Science and Artificial Intelligence, Victoria University of
Wellington
<EMAIL_ADDRESS>
)

###### Abstract

Resource constrained job scheduling is a hard combinatorial optimisation
problem that originates in the mining industry. Off-the-shelf solvers cannot
solve this problem satisfactorily in reasonable timeframes, while other
solution methods such as many evolutionary computation methods and
matheuristics cannot guarantee optimality and require low-level customisation
and specialised heuristics to be effective. This paper addresses this gap by
proposing a genetic programming algorithm to discover efficient search
strategies of constraint programming for resource-constrained job scheduling.
In the proposed algorithm, evolved programs represent variable selectors to be
used in the search process of constraint programming, and their fitness is
determined by the quality of solutions obtained for training instances. The
novelties of this algorithm are (1) a new representation of variable
selectors, (2) a new fitness evaluation scheme, and (3) a pre-selection
mechanism. Tests with a large set of random and benchmark instances, the
evolved variable selectors can significantly improve the efficiency of
constraining programming. Compared to highly customised metaheuristics and
hybrid algorithms, evolved variable selectors can help constraint programming
identify quality solutions faster and proving optimality is possible if
sufficiently large run-times are allowed. The evolved variable selectors are
especially helpful when solving instances with large numbers of machines.

##  1 Introduction

In the field of scheduling, a number of problems can be formulated as job
scheduling problems. Among these, the variant – resource-constrained job
scheduling (RCJS) with shared resources – is a typical example of a real-world
application. The problem was originally motivated in the mining supply chain
and aims to optimise the throughput of ore from mines to ports. The specific
components of the RCJS problem and their relationship to mining are as
follows. A single batch of ore that needs to be transported is a job. The
modes of transport are typically trains or trucks, which are limited in
number. Therefore, batches of ore that need to be transported concurrently
must share the trains and trucks, and in RCJS, this is modelled by the
resource limit on jobs running in parallel. Ore batches may also need to
arrive in a particular order at ports, which is effectively modelled by
imposing precedences between jobs. A major concern is the untimely arrival of
ore batches at ports, which results in demurrage costs. It is nearly
impossible to ensure that all batches of ore arrive in a timely fashion, but
limiting untimely arrivals can lead to large improvements in the mining supply
chain. This aspect can be modelled as an objective that minimises the total
weighted tardiness (TWT) across all jobs.

Due to the complexity of RCJS, exact approaches on their own have not been
effective. Moreover, the complicating constraints mean that metaheuristics on
their own struggle to find good feasible regions. Hence, a number hybrid
methods and in particular matheuristics have proved most effective [34, 14,
42, 39, 23, 5, 38, 24]. The original studies on this problem investigate
Lagrangian relaxation and column generation based matheuristics, where integer
programming decompositions are combined with simulated annealing, particle
swarm optimisation and ant colony optimisation [34, 14, 42]. All these studies
demonstrate that good feasible solutions can be found in reasonable time
frames, and moreover good lower bounds to the problem can obtained. However,
solving large problems was still a challenge, and hence parallel
implementations were attempted and showed promise [39, 12, 23]. A recent study
by [5] applies a biased random key genetic algorithm, and shows that excellent
results can be found in short time frames. To the authors’ knowledge, the most
recent study by [38] proposes a new matheuristic, merge search, which proves
to be very effective on small to medium sized problems.

Previous studies have also shown that constraint programming (CP) can be
effective on variants of RCJS [43, 12]. [43] showed that CP on its own
requires substantial resources, and hence, they propose a hybrid of CP with
ant colony optimisation and beam search. While this approach proves to be
effective, it still suffered from large run-time requirements. The study by
[12] further aimed to improve efficiency by considering parallel
implementations for RCJS, though there was still significant room for
improvement.

A recent line of research has explored the interface between optimisation and
machine learning, and among the approaches that are gaining popularity,
automated heuristic design (AHD) is of substantial interest [7, 31, 21, 47].
AHD is a hyperheuristic method that departs from traditional optimisation
approaches [10, 46, 18, 15], where the aim is to explore the space of
heuristics rather than the traditional aim of exploring a solution search
space. Several machine learning techniques have been effectively applied for
learning or evolving heuristics, including logistic regression [17], decision
trees [29] and artificial neural networks [19, 2]. An alternative is genetic
programming (GP), a popular method for AHD. The method maintains a population
of programs (depending on fitnesses), which are created and evolved using the
crossover and mutation operators across a number of generations. Typically, a
meta-algorithm is used for fitness evaluations, where the meta-algorithm is a
solution construction procedure or meta-heuristic template, and these are used
to solve a number of simulated scenarios or training instances [21]. The GP
approach has two main strengths, which are search mechanisms and flexible
representations, allowing it to deal very effectively with potentially many
decisions and technical requirements inherent in optimisation problems. GP has
been widely used in scheduling and combinatorial optimisation, including
resource allocation [11], dynamic pickup and delivery [46], production
scheduling [30, 50], and web composition [33]. The strength of the method is
evidenced in these studies, which have shown for a number of applications,
that the evolved GP-based programs or heuristics it finds, often outperform
manually designed heuristics identified by problem domain experts.

The combination between GP and CP has recently been investigated by [25]. In
their study, the proposed GP algorithm is used to evolve variable selectors in
CP for job shop scheduling, and the fitness of a variable selector is the
number of branching steps in CP needed to reach optimal solutions. The results
show that the evolved variable selectors can help CP quickly identify good
solutions and increase the chance of finding optimal solutions. Unlike most
applications of GP for combinatorial optimisation problems, no meta-algorithm
is needed for solution construction (or improvement) as their algorithm can
directly utilise the problem formulation and CP to construct complete
solutions and improve their quality.

In this paper, we introduce the first investigation into the combination of GP
and CP for the RCJS problem. The aim of this study is to examine the extent to
which GP can improve the performance of CP in solving the RCJS problem. We
build upon the approach developed in [25] and propose a novel GP algorithm
that evolves the CP variable selectors for solving the RCJS problem. Our
algorithm introduces three key advancements: (1) a novel representation of
variable selectors for RCJS, (2) a new fitness evaluation scheme, and (3) a
pre-selection mechanism. These advancements are designed to address the
challenges of efficiently evolving variable selectors for RCJS using GP, which
cannot be adequately addressed by the original algorithm developed in [25].

The rest of this paper is organised as follows. Section 2 describes the RCJS
problem and discusses related work. Section 3 presents the proposed GP
algorithm and its key components. Datasets and parameter settings are
presented in Section 4. Section 5 presents the experiment settings and the
results of the proposed algorithm compared to a metaheuristic and a hybrid
method. Finally, conclusions and future work are presented in Section 6.

##  2 Background

###  2.1 Problem formulation

The RCJS can be formally defined as follows. There are a number of machines
$\mathcal{M}=\\{m_{1},\ldots,m_{l}\\}$, jobs $\mathcal{J}$
$=\\{j_{1},\ldots,j_{n}\\}$ and time horizon $\mathcal{T}$, given. A job $i$
has with it the following data associated:

  * •

$r_{i}$: release time

  * •

$p_{i}$: processing time

  * •

$d_{i}$: desired due time

  * •

$w_{i}$: the weight of the job

  * •

$g_{i}$: amount of resource needed

  * •

$m_{i}$: the machine that the job must be scheduled on

Moreover, a set of precedences $\mathcal{P}$ are given, where between two jobs
$i$ and $j$ on the same machine, a precedence relation may exist
($i\rightarrow j$ implies that job $i$ must complete before job $j$
commences). Moreover, resource limits are imposed with the renewable resource
$R$, where all jobs executing at any time point concurrently, must not
cumulatively use more than the limit $R$. The objective is to minimize total
weighted tardiness

$T({\bf\pi})=\sum_{i=1}^{n}w_{\pi_{i}}\times T(\pi_{i})$ (1)

where $\pi$ is a permutation of the jobs and $T(\pi_{i})$ is tardiness of job
$i$.

The RCJS problem can be formulated as a constraint program as follows. We
define the start time and end time variables for all jobs, $s_{j}$ and $e_{j}$
for job $j$, respectively.

$\displaystyle\forall j\in{\mathcal{J}}:$ $\displaystyle s_{j}\geq r_{j}$ (2)
$\displaystyle\forall j\in{\mathcal{J}}:$ $\displaystyle e_{j}=s_{j}+p_{j}$
(3) $\displaystyle\forall i,j\in{\mathcal{J}}:$ $\displaystyle
m_{i}=m_{j}\Rightarrow s_{i}>e_{j}\vee s_{j}>e_{i}$ (4)
$\displaystyle\forall(i,j)\in{\mathcal{P}}:$ $\displaystyle\quad s_{j}>e_{i}$
(5)

Constraint 2 ensures a job starts after it is released. Constraint 3 links the
start and end time variables for all jobs. Constraint 4 are disjunctive
constraints, and ensure that jobs on the same machine cannot execute at the
same time. The precedences between two tasks on the same machine are imposed
by Constraint 5.

Finally, to ensure the resource constraints are satisfied, we make use of the
solver’s in-built high-level constraint, cumulatives($s$,$p$,$e$,$r$,$R$).
This constraint takes as input the start ($s$) time variables, end time ($e$)
variables, and data given by the processing times ($p$), resource requirements
($r$) and resource limit ($R$). The start and end time variables are
determined by considering $p$, $r$ and $R$, so that if two or more tasks
overlap in their execution at any time point (irrespective of their machine),
they must cumulatively use at most resource availability $R$.

###  2.2 Optimisation algorithms for RCJS

A closely related problem to the RCJS that has been studied extensively is
project scheduling [9]. Both problems consist of several similarities,
including jobs with known processing times, shared resources, and precedence
relations. There are also important differences, such as the objectives.
Therefore, approaches to solving project scheduling can also be considered for
RCJS, and numerous such approaches have been applied [1, 9, 13, 20, 44, 8,
37]. Exact approaches on their own are often infeasible in terms of time, and
hence most of these methods focus on metaheuristics, hybrid methods,
matheuristics, decompositions, and parallel implementations. [13] investigates
exact and incomplete approaches and finds that genetic algorithms and
simulated annealing are most effective on variant of the problem. [20]
investigate project scheduling with time windows and devise exact and
heuristic approaches to solve it. [1] investigate a project scheduling variant
that is closely related to RCJS, where the objective is to minimise the
cumulative deviation of the completion times of all tasks. They show that a
local search approach is the most effective on this problem. The net present
value objective has also been considered by recent studies [44, 8, 37], which
show that meta-heuristics and parallel implementations can be used to achieve
high levels of efficiency.

Of particular interest in RCJS, is the TWT objective. This objective has
indeed been considered in several similar problems [35, 36]. The studies by
[35] and [36] use agent-based modelling with relatively little information
sharing. These studies also assume decentralised data. Nonetheless, these
studies demonstrate the complexity of RCJS type problems, especially
considering the TWT objective.

Recently, a variant of RCJS with uncertainty has been investigated [40, 41].
[40] show that a population-based ant colony optimisation with surrogate
models can provide excellent solutions to the problem. Furthermore, [41]
propose an adaptive simulated annealing approach, which outperforms
population-based ant colony optimisation and also proves to be effective on
the original RCJS problem.

We see that several studies have been carried out on RCJS and related
problems, but there is still considerable scope for improvement, particularly
in terms of solution approaches. The most successful methods to date have been
metaheuristics, mixed integer programming, constraint programming and
matheuristics. However, there has been little progress in integrating the
benefits of machine learning and optimisation for tackling such complex
problems. This study aims to make progress in this direction.

###  2.3 Machine learning for combinatorial optimisation

Machine learning (ML) has emerged as a powerful tool to tackle combinatorial
optimisation problems. Integrating ML into combinatorial optimisation focusses
on enhancing traditional algorithms with advanced decision-making capabilities
[4]. This synergy is particularly evident in how ML can approximate complex
computations or develop new policies for decision making, as highlighted in
research on discrete optimisation problems like integer-constrained
optimisation. The methodologies employed in the literature vary from
supervised learning, where ML models mimic expert decisions, to reinforcement
learning, which involves learning and optimising decision functions from
scratch.

The integration of ML into combinatorial optimisation can be categorised into
three distinct approaches [4]. The first, end-to-end learning, involves using
ML models to directly output solutions from given problem instances, with the
ML model acting independently to solve discrete optimisation problems [3]. The
second approach, learning to configure algorithms, uses ML to enhance
traditional combinatorial algorithms. Here, ML aids in configuring algorithm
parameters or providing additional decision-making information, thereby
optimising the algorithm’s performance [6]. The third approach, machine
learning alongside optimisation algorithms, represents a more collaborative
interplay between ML and combinatorial optimisation.

GP has been applied to many combinatorial optimisation problems from
production scheduling [28] to dynamic pickup and delivery [45]. The main goal
of GP in these studies is to automatically discover good heuristics for either
constructing solutions (similar to “end-to-end learning”) or
improving/refining existing solutions (similar to “machine learning alongside
optimisation algorithms” discussed above). A training dataset including
instances from the optimisation problems is usually used to evaluate the
quality of evolved heuristics. Recent work in [25] suggests a simple way to
use GP to enhance the efficiency of constraint programming by designing
effective variable ordering heuristics. A number of advanced GP algorithms
have been proposed to improve the quality of heuristics used to solve
combinatorial optimisation problems [49]. Recent studies on GP with machine
learning techniques often examine feature selection, surrogate modelling,
ensemble learning, and multitask learning [48].

###  2.4 Genetic programming algorithms for RCJS

Recently, GP has also been applied to solve different variants of RCJS. [11]
apply GP to evolve priority dispatching rules for resource-constrained project
scheduling and show that the evolved rules are significantly better than
existing rules and heuristics. In their paper, priority rules are functions
that are used to assign priorities to project activities based on their
characteristics, such as durations and release times. The study by [22] is the
pioneering research that applies GP to develop heuristics for the RCJS. Two
representations based on simple expression trees and iterative rules [27] are
adopted to generate heuristics for RCJS. The experiments show that evolved
heuristics can quickly produce good solutions, especially for large instances.
The main limitation of the method is that there is still a large gap between
solutions generated by evolved heuristics and optimal solutions. Moreover, in
these studies, a solution construction heuristic is always needed to generate
complete and feasible solutions. In the method proposed in this paper,
solution construction heuristic is not needed.

##  3 Proposed method

Figure 1 shows a high-level overview of our proposed genetic-based constraint
programming (GCP) algorithm. The algorithm starts by generating individuals,
which are variable selectors, in a random manner. The population of variable
selectors, denoted as
$\mathbb{S}=\\{\mathcal{S}_{1},\dots,\mathcal{S}_{PS}\\}$, where $PS$
represents the population size, is then evaluated using a CP solver along with
the given problem formulation. In this study, we use Google OR-
Tools111https://developers.google.com/optimization as the CP solver. The
fitness of variable selectors is determined by the quality of solutions (i.e.,
$TWT$) obtained by CP for a subset of training instances $\mathcal{I}_{g}$,
within a fixed time limit. The selector $\mathcal{S}^{*}_{g}$ with the best
fitness in the current generation is then evaluated using the complete
training dataset $\mathcal{I}$ to avoid overfitting. If $\mathcal{S}^{*}_{g}$
shows improvement, it replaces the best-so-far selector $\mathcal{S}^{*}$.
Individuals in the population are selected for crossover and mutation based on
their fitness evaluations to generate new offspring. A simple pre-selection
technique is employed to prevent the generation of poor-performing variable
selectors in the next generation. This technique evaluates variable selectors
using small instances (small numbers of jobs and machines), selecting only the
top $PS$ selectors from these trials to be moved to the next generation. The
algorithm terminates when the maximum generation is reached. The details for
each key component of our GCP algorithm will be provided in the following
subsections.

Figure 1: An overview of our proposed GCP algorithm.

###  3.1 Representation

Figure 2: Representation of variable selector.

We define the CP model $\Omega=(\mathcal{X},\mathcal{D},\mathcal{C})$ to solve
an instance of the RCJS problem. All variables in the problem are represented
by $\mathcal{X}=\\{x_{1},\dots,x_{n}\\}$, that is, the start times of all
jobs. The domains of the variables are represented by
$\mathcal{D}=\\{\mathcal{D}_{1},\dots,\mathcal{D}_{n}\\}$, where
$x_{k}\in\mathcal{D}_{k}$ or the start time variables have discrete domain
values between 0 and $\mathcal{T}$. For example, for job $k$,
$x_{k}\in[0,\ldots,\mathcal{T}-p_{j}]$. The constraints are represented by the
set $\mathcal{C}=\\{C_{1},\dots,C_{L}\\}$, which includes precedence or
disjunctive constraints. Each constraint $C_{l}$ is defined by a relation
$\mathcal{R}_{l}$ and a subset of variables $\mathcal{X}_{l}\in\mathcal{X}$,
which determine the values to which the variables $x\in\mathcal{X}_{l}$ can be
assigned. To find a solution to $\Omega$, the CP solver has a search strategy
that decides: (1) which variable to branch on next, and (2) an appropriate
domain value to assign to the chosen variable. The GCP component attempts to
identify which variable to select next. For the purposes of this study, there
are two sub-strategies for variable selection, which are variable ordering and
domain-based variable selection.

First, in domain-based variable selection, the domain values of all variables
are considered to select which one to branch on next. As a part of the search
method of CP solvers, there will typically be a default strategy, but also
allow different options for domain-based variable selection. For example,
those variables with the smallest domain size or minimum domain value will be
selected next as part of the CP solver’s default strategy. Variable ordering,
on the other hand, is applied as a tie-breaker if the domain-based variable
selection cannot lead to a unique variable to branch on. The motivation behind
these sub-strategies is aimed at identifying feasibility (picking variables
with a few remaining domain values, thereby satisfying constraints) or
identifying high-quality solution (by carefully considering the order of
variables). Our proposed GCP approach focusses on variable ordering with the
aim of guiding CP towards finding higher-quality solutions. In the GCP-evolved
variable selectors, the fixed domain-based variable selection is obtained via
choosing-lowest-domain-value, while the variable ordering is evolved. In order
to reduce the domains of variables (domain reduction strategy), the CP model
uses selecting-min-value.

Variable ordering is performed by calculating the priorities for each decision
variable with a priority function. In GCP, priority functions are expression
trees in which terminal nodes are characteristics of jobs in the RCJS directly
extracted from the CP model, and non-terminal nodes are arithmetic or logical
operators. Figure 2 shows an example of a priority function. The list of
terminals and functions used to compose priority functions is shown in Table
1. Most termimal values, such as $ES,PT,W,DD$, can be obtained directly from
problem instances while values of high-level terminals such as
$WL,maxWL,NPREC,NSUC,WLPREC,WLSUC$ can be obtained when CP models are built.
For the function set, GCP uses a set of arithmetic and logical functions that
are commonly used in the literature [7]. This representation allows GCP to
explore a wide range of priority functions and determine those that produce
efficient variable orderings for CP. Unlike [22] in which priority functions
are applied multiple times to construct complete solutions for each instance,
the priorities of variables are only calculated once in GCP and used as input
for the CP solver.

Table 1: The terminal set and function set (corresponding to a job $j$) used in GCP. Notation | Description
---|---
$ES$ | earliest start time or release time
$PT$ | processing time
$W$ | weight
$DD$ | due date
$WL$ | workload of the machine processing $j$
$maxWL$ | maximum workload for all machines
$NPREC$ | number of precedence jobs
$NSUC$ | number of successors
$WLPREC$ | workload of precedence jobs
$WLSUC$ | workload of successors
$Functions$ | $+,-,*,\%,\max,\min$

###  3.2 Fitness evaluation

In [25], the fitness of an evolved variable selector $\mathcal{S}$ is based on
computational efforts, that is, the number of branches that the CP solver uses
to optimally solve a set of training instances. If a variable selector uses a
smaller number of branching steps to reach optimal solutions, that selector
will have a better fitness. However, this fitness evaluation method is only
feasible if the training instances are small or solvable by the CP solver.
Another issue with this method is overfitting as shown in [25]. To overcome
these issues, we propose here a new fitness function based on solution quality
rather than computational efforts. The fitness of a variable selector
$\mathcal{S}$ can be calculated as follows:

$fitness(\mathcal{S},\mathcal{I}_{g})=\frac{1}{|\mathcal{I}_{g}|}\sum_{I\in\mathcal{I}_{g}}{obj(\mathcal{S},I,T)},$
(6)

where $\mathcal{I}_{g}$ is the set of instances randomly sampled from the
training dataset $\mathcal{I}$ for fitness evaluations in generation $g$, and
$obj(\mathcal{S},I,T)$ is the objective value for $I$ obtained by the CP
solver after a solving time limit $T$. We prioritise evolved variable
selectors that assist the CP solver in rapidly identifying high-quality
solutions within limited time frames rather than focusing on achieving and
proving optimal solutions. This approach is appropriate for scenarios where
problems, such as the RCJS, are difficult to solve optimally and require the
generation of feasible, high-quality, and quick solutions. Furthermore, this
method ensures that the GCP training times are more predictable than the
approach used in [25].

To further improve the training efficiency of GCP, we adopt the sampling
strategy used in [16, 26] for fitness evaluations. For each generation, only a
subset $\mathcal{I}_{g}$ of the complete training set $\mathcal{I}$ is
randomly sampled for fitness evaluations. This strategy has been shown to
improve the population diversity of GP algorithms. In a generation $g$, the
evolved selector $\mathcal{S}_{g}^{*}$ with the best
$fitness(\cdot,\mathcal{I}_{g})$ will be fully evaluated with $\mathcal{I}$
and will replace the best-so-far selector $\mathcal{S}^{*}$ if an improvement
is made.

###  3.3 Genetic operators

Traditional subtree crossover and subtree mutation [32] are used in our
proposed GCP algorithm to produce offspring or new variable selectors. Parents
for these genetic operators are selected using a tournament selection. For
crossover, a subtree is randomly selected from each parent, and two subtrees
are swapped to produce offspring. For mutation, a random subtree is selected
from the selected parent and will be replaced with an entirely new random
subtree.

###  3.4 Pre-selection technique

Since the genetic operators used in GP are highly random, there is a high
chance that poorly performing individuals will be generated. To avoid spending
computational budgets evaluating bad individuals, pre-selection techniques
have been applied as a screening step in which only the most promising
individuals are kept for the next generation. In our study, we developed a new
pre-selection algorithm in Algorithm 1. An intermediate population
$\mathbb{S}^{\prime}$ with newly generated individuals based on the above
genetic operators will go through a trial process, in which small instances
are used to quickly determine their quality. Another advantage of this pre-
selection process is to evaluate the ability to reach optimal or near-optimal
solutions of evolved variable selectors, which is not a main emphasis in the
proposed fitness function.

Algorithm 1 Pre-selection algorithm

1:Input: A set of newly generated variable selectors $\mathbb{S}^{\prime}$
($|\mathbb{S}^{\prime}|>|\mathbb{S}|$), and training dataset $\mathcal{I}$

2:Output: a new population $\mathbb{S}$

3:$\mathcal{I}^{\prime}\leftarrow$ select small instances from $\mathcal{I}$

4:$\mathbb{S}\leftarrow\emptyset$

5:for $\mathcal{S}\in\mathbb{S}^{\prime}$ do

6: $fitness(\mathcal{S},\mathcal{I}^{\prime})\leftarrow$ evaluate
$\mathcal{S}$ with new instances in $\mathcal{I}^{\prime}$

7:sort $\mathbb{S}^{\prime}$ based on $fitness(\cdot,\mathcal{I}^{\prime})$
(lowest to highest)

8:$\mathbb{S}\leftarrow$ select the top $PS$ selectors from
$\mathbb{S}^{\prime}$

9:return the new population $\mathbb{S}$

##  4 Experimental Design

###  4.1 Datasets

For the experimental evaluation, we make use of two datasets. The first one
consists of 1755 randomly generated instances obtained by the instance
generator of [23].222https://github.com/andreas-ernst/Mathprog-
ORlib/blob/master/data/RCJS_new_instances.zip The dataset includes
combinations of different characteristics of RCJS with the following settings:

  * •

Number of machines: {3, 4, 5, 6, 7, 8, 9, 10, 12, 15, 18, 20, 25},

  * •

Network complexities (precedence probability): {0.1, 0.2, 0.3, 0.4, 0.5, 0.6,
0.7 0.8, 0.9},

  * •

Resource utilisation: {0.25, 0.5, 0.75}.

Using the study by [34] as a guide, each machine consists of approximately
10.5 jobs. This dataset was used for training and testing purposes. The second
dataset that we investigate is a well-known benchmark [34, 14, 42, 39], which
has provided the baseline for comparing solution methods in the
literature.333https://github.com/andreas-ernst/Mathprog-
ORlib/blob/master/data/RCJS_Instances.zip In the following sections, we refer
to the first dataset as the nd-rcjs dataset and the second one as the se-rcjs
dataset (the datasets are named after the authors’ initials).

###  4.2 Parameter settings

Table 2 shows the parameters of GCP and the CP solver. These parameters are
similar to those used in [25] and are further fine-tuned through pilot
experiments. We then set the number of generations to 50, which is sufficient
for the population to converge. In our experiments, to avoid biases caused by
instances with different sizes, for our training set, we fix the number of
machines in the chosen instances. Specifically, we only use instances with 6
machines for fitness evaluations. Instances with 6 or fewer machines will be
used for the pre-selection step. These instances are selected based on our
observations in previous studies that RCJS instances with 6 machines or more
are unlikely to be solved to optimality.

Table 2: Parameter settings | Parameter | Value
---|---|---
GCP | Population size | 200, 500, 1000
| Number of generations | 50
| Terminal and function sets | see Table 1
| Initialisation | ramped-half-and-half
| Tournament selection size | 5
| Subtree crossover | 90%
| Subtree mutation | 10%
| Maximum depth | 7
| Intermediate population size |  $=2\times$ population size
| # of training instances $|\mathcal{I}|$ | 81
| # of instances per generation $|\mathcal{I}_{g}|$ | 5
| # of instances for pre-selection | 10
CP | Solver | Google Or-tools
solver | Solving time limit (training) | 30 (s)
| Solving time limit (testing) | 60 (s)

When solving each instance in the training or testing step, the CP solver
terminates when the time limit expires, and the solution with the best
objective value at that point will be reported. Feasibility is not an issue,
since for all RCJS instances we use, the CP solver can always find at least
one feasible solution in the allowed time-frame. The time limit for testing
purposes is allowed to be a bit larger in order to examine whether the
advantages of evolved variable selectors can be realised in the later stages
of the CP search process. The default domain-based variable selection and the
default domain reduction are choosing-lowest-domain-value and selecting-min-
value, respectively. The variable selectors evolved by GCP will be used as
tie-breakers to help choosing-lowest-domain-value decide the next variable to
branch.

###  4.3 Compared algorithms

To validate the effectiveness of the proposed algorithm, we compare GCP with
other GP and optimisation methods. Other GP algorithms compared in our
experiments include GP for evolving a single-pass heuristic and GP for
iterative dispatching rules (IGP) [22]. Compared to the single-pass heuristic,
we examine the performance of evolved selectors against traditional
construction heuristics. On the other hand, IGP aims at evolving improvement
heuristics, which will be a good candidate for verifying the benefits of
combining GP and CP. We also attempt to compare GCP with the GP algorithm
proposed in [25]. However, RCJS instances are too complex to solve to
optimality; therefore, the GP algorithm proposed in [25] failed to make any
significant progress as its fitness function cannot differentiate between good
and bad variable selectors. Optimisation algorithms compared in our
experiments are ant colony optimisation (ACO) [42], and column generation and
ACO (CGACO) [39]. These two algorithms specialise in solving RCJS instances
and employ a wide range of optimisation tricks to improve the search
efficiency. Comparing our algorithms to these two optimisation algorithms
helps access the value of learning efficient variable selectors.

##  5 Results

This section compares the results of GCP with existing GP algorithms and
specialised optimisation methods that have been proposed for RCJS in the
literature. Since RCJS instances are well-known for their complexity, our
paper focuses on comparing the solution quality (objective values of best-
found solutions) rather than the number of optimal solutions. The impact of
population size on the effectiveness of evolved variable selectors is also
examined. The population size represents the computational effort required to
evolve variable selectors. However, as training or evolutionary processes can
be done offline, large population sizes will not influence the solving time of
the CP solver, which only uses the evolved variable selector. In addition,
computational times to execute evolved variable selectors when solving each
instance are very small (less than a fraction of a second) and will not be
discussed.

(a) Objective values (b) % Optimal solutions

Figure 3: The comparison between our proposed GCP and the default setting of
Google OR-Tools (se-rcjs dataset).

###  5.1 Comparisons to the default CP settings

Figure 3 shows the average objective values and percentage of optimal
solutions obtained by Google’s OR-Tools CP solver and GCP with different
population sizes. Note that the instances used in these experiments (from se-
rcjs dataset) are not seen during the training process of GCP. The results
suggest that GCP can produce better solutions than its counterpart and
slightly improves the chances of proving optimality. These results demonstrate
both the effectiveness of GCP and the generalisation of its evolved variable
selectors. It is worth noting that increasing computation effort can greatly
benefit GCP. From Figure 3, it is clear that large population sizes can lead
to more effective variable selectors.

The advantages of GCP are different across different subsets, as seen in
Figure 4 and Figure 5. For small instances with fewer than 7 machines, GCP
does not show any clear advantage as the CP solver can determine optimal or
near-optimal solutions relatively easily regardless of variable orderings. As
the size of the problem increases, we can see the importance of variable
orderings. For the largest instances in the se-rcjs dataset, the objective
values obtained by GCP are nearly half of those obtained by Google OR-Tools.
These results confirm that GCP can enhance the efficiency of the CP solver,
and moreover, increased improvements are seen with increasing problem sizes.

###  5.2 Comparisons to GP algorithms

Figure 4 shows the performance of GCP compared to simple GP (or GP for short)
and IGP, proposed in [22]. The other two GP algorithms in previous studies are
only trained and tested with the se-rcjs dataset, so these algorithms are
expected to be more specialised for the instances in our comparison. The
results show no clear difference between GCP and other GP algorithms when
dealing with small and medium instances (number of machines fewer than 12) –
except for the instances with 3 machines. For larger instances (with 12
machines or more), GCP shows a clearer advantage. For large instances with 20
machines (the hardest instances in the se-rcjs dataset), the solutions
obtained by GCP are 20% lower than those of GP and IGP.

Given that the terminal sets used by GCP and the other two algorithms are
equivalent, the improvements seen here are directly attributable to the
combination of GP and CP. For small instances, the CP solver can complete an
exhaustive search to determine optimal solutions, which are very difficult to
obtain with the heuristics evolved by the other two GP algorithms. For large
instances, the CP solver again gives GCP a better chance to find improvements,
via the systematic search of CP, rather than the construction and improvement
procedures employed in the other two GP algorithms.

Apart from the performance advantages, GCP works directly with user-friendly
problem formulations and does not require low-level heuristics such as
solution construction and improvement heuristics, which are necessary for the
other GP algorithms. This has several practical implications. First, users can
easily address new situations (e.g. additional technological constraints) by
modifying the problem formulation rather than developing new customised
heuristics, which can be time-consuming (for testing and fine-tuning). Second,
if larger run-times are allowed, GCP can make further attempts to identify
better solutions, which is impossible with heuristics evolved by the other GP
algorithms.

(a) Instances with less than 9 machines (b) Instances with 9 machines or more

Figure 4: The comparison between GCP and GP algorithms.

###  5.3 Comparisons to optimisation algorithms

In Figure 5, the evolved variable selectors are compared to other specialised
optimisation algorithms for RCJS. It is noted that the results reported for
ACO and CGACO are obtained after running these algorithms for 60 minutes,
which is 60 times more expensive than GCP (only 60 seconds during the testing
phase). For the se-rcjs dataset, ACO and CGACO are better than GCP for the
small and medium instances (fewer than 12 machines). However, GCP becomes more
competitive for instances with 15 machines and outperforms ACO and CGACO for
instances with 20 machines. Achieving these results with a much smaller
running times show that GCP is a powerful tool to solve RCJS problem.

Given that ACO and CGACO [23] are very sophisticated algorithms with many
specialised heuristics designed for RCJS and the support of advanced integer
programming solvers, these results are very encouraging. One key advantage of
GCP is that it incorporates little or no problem domain knowledge manually
into the solving process, which is the key factor in the success of CGACO.
Therefore, GCP can be easily generalised to work with different variants of
RCJS without major modifications.

(a) Instances with less than 9 machines (b) Instances with 9 machines or more

Figure 5: A comparison of GCP and other specialised optimisation algorithms.

###  5.4 Further analyses

Figure 6 sheds some light on the training or evolutionary process of GCP. GCP
with three different population sizes can converge within 50 generations, and
the results show that a larger population helps GCP identify better variable
selectors (low fitness values). These observations are consistent with the
testing results shown in Figure 3 and indicates no serious overfitting issue
in GCP.

Figure 6: The training progress of GCP.

##  6 Conclusions and future studies

In this study, we propose an automated heuristic design method based on GP to
enhance the performance of constraint programming solvers to tackle resource-
constrained job scheduling. The idea underlying our method is to use GP to
search over a heuristic space, thereby learning variable orderings that can be
used within the search component of CP solvers. An experimental evaluation on
two benchmark datasets shows the following results: (a) CP with the evolved
variable selectors (GCP) is more effective than Google’s OR Tools SAT solver
in terms of solution quality and proving optimality, (b) GCP is more effective
than existing GP techniques for RCJS, and (c) GCP is competitive with existing
optimisation methods specifically designed for RCJS and able to outperform
these methods for large instances with a much smaller running time.

Our proposed GCP approach has demonstrated promise on RCJS and has previously
shown to be effective on job shop scheduling. It could prove to be effective
on RCJS with uncertainty [40, 41], which the authors plan to investigate as
part of future work. Moreover, being problem independent, we conjecture that
this approach can be readily transferred to any problem that can be modelled
efficiently as a constraint program. In doing so, we can expect to find higher
quality solutions in reduced time-frames.

In the context of RCJS, we have seen the excellent performance of our proposed
method. However, it is possible to further improve the method, for example, by
considering other machine learning approaches or making use of other problem
specific heuristics in the terminal set. A more ambitious direction is to
develop automated methods to directly extract high-level patterns, such as
separability, from CP models, which can lead to huge efficiency improvements.

## References

  * [1] F. Ballestin and N. Trautmann.  An Iterated-local-search Heuristic for the Resource-constrained Weighted Earliness-tardiness Project Scheduling Problem.  International Journal of Production Research, 46:6231–6249, 2008.
  * [2] I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio.  Neural Combinatorial Optimization with Reinforcement Learning.  2017\.
  * [3] Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio.  Neural combinatorial optimization with reinforcement learning.  arXiv preprint arXiv:1611.09940, 2016.
  * [4] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost.  Machine learning for combinatorial optimization: A methodological tour d’horizon.  European Journal of Operational Research, 2020.
  * [5] C. Blum, D. Thiruvady, A. T. Ernst, M. Horn, and G. Raidl.  A Biased Random Key Genetic Algorithm with Rollout Evaluations for the Resource Constraint Job Scheduling Problem.  In J. Liu and J. Bailey, editors, AI 2019: Advances in Artificial Intelligence, pages 549–560, Cham, 2019. Springer International Publishing.
  * [6] Pierre Bonami, Andrea Lodi, and Giulia Zarpellon.  Learning a classification of mixed-integer quadratic programming problems.  In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings 15, pages 595–604. Springer, 2018.
  * [7] J. Branke, S. Nguyen, C. W. Pickardt, and M. Zhang.  Automated design of production scheduling heuristics: A review.  IEEE Transactions on Evolutionary Computation, 20(1):110–124, February 2016.
  * [8] O. Brent, D. Thiruvady, A. Gómez-Iglesias, and R. Garcia-Flores.  A parallel lagrangian-aco heuristic for project scheduling.  In 2014 IEEE Congress on Evolutionary Computation (CEC), pages 2985–2991, 2014.
  * [9] P. Brucker, A. Drexl, R. Möhring, K. Neumann, and E. Pesch.  Resource-constrained Project Scheduling: Notation, Classification, Models, and Methods.  European Journal of Operational Research, 112:3–41, 1999.
  * [10] E. K. Burke, M. R. Hyde, and G. Kendall.  Evolving bin packing heuristics with genetic programming.  In Thomas Philip Runarsson, Hans-Georg Beyer, Edmund Burke, Juan J. Merelo-Guervós, L. Darrell Whitley, and Xin Yao, editors, Parallel Problem Solving from Nature - PPSN IX, pages 860–869, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
  * [11] S. Chand, Q. Huynh, H. Singh, T. Ray, and M. Wagner.  On the use of genetic programming to evolve priority rules for resource constrained project scheduling problems.  Information Sciences, 432:146–163, 2018.
  * [12] D. Cohen, A. Gómez-Iglesias, D. Thiruvady, and A. T. Ernst.  Resource Constrained Job Scheduling with Parallel Constraint-Based ACO, pages 266–278.  Springer International Publishing, Cham, 2017.
  * [13] E. Demeulemeester and W. Herroelen.  Project Scheduling: A Research Handbook.  Kluwer, Boston, MA, USA, 2002.
  * [14] A. T. Ernst and G. Singh.  Lagrangian particle swarm optimization for a resource constrained machine scheduling problem.  In X. Li, editor, 2012 IEEE Congress on Evolutionary Computation (CEC), pages 1 – 8, United States of America, 2012. IEEE, Institute of Electrical and Electronics Engineers.  IEEE Congress on Evolutionary Computation 2012.
  * [15] X. Hao, R. Qu, and J. Liu.  A Unified Framework of Graph-Based Evolutionary Multitasking Hyper-Heuristic.  IEEE Transactions on Evolutionary Computation, 25(1):35–47, 2021.
  * [16] T. Hildebrandt, J. Heger, and B. Scholz-Reiter.  Towards improved dispatching rules for complex shop floor scenarios – A genetic programming approach.  In M. Pelikan and J. Branke, editors, Proceedings of 2010 Genetic and Evolutionary Computation Conference, GECCO’10, pages 257–264, Portland, Oregon, USA, 2010. ACM Press.
  * [17] H. Ingimundardottir and T. P. Runarsson.  Supervised learning linear priority dispatch rules for job-shop scheduling.  In C. A. Coello Coello, editor, Learning and Intelligent Optimization, volume 6683 of LNCS, pages 263–277, Berlin and Heidelberg, 2011. Springer.
  * [18] E. Kieffer, G. Danoy, M. R. Brust, P. Bouvry, and A. Nagih.  Tackling large-scale and combinatorial bi-level problems with a genetic programming hyper-heuristic.  IEEE Transactions on Evolutionary Computation, 24(1):44–56, 2020.
  * [19] W. Mouelhi-Chibani and H. Pierreval.  Training a neural network to select dispatching rules in real time.  Computers & Industrial Engineering, 58(2):249–256, 2010.
  * [20] K. Neumann, C. Schwindt, and J. Zimmermann.  Project Scheduling with Time Windows and Scarce Resources.  Springer, Berlin, Germany, 2003.
  * [21] S. Nguyen, Y. Mei, and M. Zhang.  Genetic programming for production scheduling: A survey with a unified framework.  Complex & Intelligent Systems, 3(1):41–66, March 2017.
  * [22] S. Nguyen, D. Thiruvady, A. T. Ernst, and D. Alahakoon.  Genetic programming approach to learning multi-pass heuristics for resource constrained job scheduling.  In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’18, pages 1167–1174, 2018.
  * [23] S. Nguyen, D. Thiruvady, A. T. Ernst, and D. Alahakoon.  A Hybrid Differential Evolution Algorithm with Column Generation for Resource Constrained Job Scheduling.  Computers & Operations Research, 109:273–287, 2019.
  * [24] S. Nguyen, D. Thiruvady, M. Zhang, and D. Alahakoon.  Automated design of multipass heuristics for resource-constrained job scheduling with self-competitive genetic programming.  IEEE Transactions on Cybernetics, 52(9):8603–8616, 2022.
  * [25] S. Nguyen, D. Thiruvady, M. Zhang, and K. C. Tan.  A Genetic Programming Approach for Evolving Variable Selectors in Constraint Programming.  IEEE Transactions on Evolutionary Computation, 2021.
  * [26] S. Nguyen, M. Zhang, D. Alahakoon, and K. C. Tan.  People-centric evolutionary system for dynamic production scheduling.  IEEE Transactions on Cybernetics, 2019.
  * [27] S. Nguyen, M. Zhang, M. Johnston, and K. Tan.  Learning iterative dispatching rules for job shop scheduling with genetic programming.  The International Journal of Advanced Manufacturing Technology, 67(1–4):85–100, 2013.
  * [28] S. Nguyen, M. Zhang, M. Johnston, and K. C. Tan.  A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem.  IEEE Transactions on Evolutionary Computation, 17(5):621–639, 2013.
  * [29] S. Olafsson and X. Li.  Learning effective new single machine dispatching rules from optimal scheduling data.  International Journal of Production Economics, 128(1):118–126, 2010.
  * [30] C. W. Pickardt, T. Hildebrandt, J. Branke, J. Heger, and B. Scholz-Reiter.  Evolutionary generation of dispatching rule sets for complex dynamic scheduling problems.  International Journal of Production Economics, 145(1):67–77, 2013.
  * [31] Nelishia Pillay, Rong Qu, Dipti Srinivasan, Barbara Hammer, and Kenneth Sorensen.  Automated design of machine learning and search algorithms [guest editorial].  IEEE Computational Intelligence Magazine, 13(2):16–17, 2018.
  * [32] R. Poli, W. B. Langdon, and N. F. McPhee.  A Field Guide to Genetic Programming.  Published via http://lulu.com and freely, 2008.
  * [33] A. S. Silva, H. Ma, and M. Zhang.  Genetic programming for QoS-aware web service composition and selection.  Soft Computing, 20(10):3851–3867, October 2016.
  * [34] G. Singh and A. T. Ernst.  Resource Constraint Scheduling with a Fractional Shared Resource.  Operations Research Letters, 39(5):363 – 368, 2011.
  * [35] G. Singh and R. Weiskircher.  Collaborative resource constraint scheduling with a fractional shared resource.  In IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, volume 2, pages 359–365. IEEE, 2008.
  * [36] G. Singh and R. Weiskircher.  A Multi-Agent System for Decentralised Fractional Shared Resource Constraint Scheduling.  Web Intelligence and Agent Systems, 9(2):99 – 108, 2011.
  * [37] D. Thiruvady, C. Blum, and A. T. Ernst.  Maximising the Net Present Value of Project Schedules Using CMSA and Parallel ACO.  In M. J. Blesa Aguilera, C. Blum, H. Gambini Santos, P. Pinacho-Davidson, and J. Godoy del Campo, editors, Hybrid Metaheuristics, pages 16–30, Cham, 2019. Springer International Publishing.
  * [38] D. Thiruvady, C. Blum, and A. T. Ernst.  Solution Merging in Matheuristics for Resource Constrained Job Scheduling.  Algorithms, 13(10), 2020.
  * [39] D. Thiruvady, A. T. Ernst, and G. Singh.  Parallel ant colony optimization for resource constrained job scheduling.  Annals of Operations Research, 242(2):355–372, July 2016.
  * [40] D. Thiruvady, S. Nguyen, F. Shiri, N. Zaidi, and X. Li.  Surrogate-assisted population based aco for resource constrained job scheduling with uncertainty.  Swarm and Evolutionary Computation, 69:101029, 2022.
  * [41] D. Thiruvady, S. Nguyen, Y. Sun, F. Shiri, N. Zaidi, and X. Li.  Adaptive population-based simulated annealing for uncertain resource constrained job scheduling, 2022.
  * [42] D. Thiruvady, G. Singh, and A. T. Ernst.  Hybrids of integer programming and aco for resource constrained job scheduling.  In M. J. Blesa, C. Blum, and S. Voß, editors, Hybrid Metaheuristics: 9th International Workshop, HM 2014, volume 8457, pages 130–144, Hamburg, 2014. LNCS.
  * [43] D. Thiruvady, G. Singh, A. T. Ernst, and B. Meyer.  Constraint-based ACO for a Shared Resource Constrained Scheduling Problem.  International Journal of Production Economics, 141(1):230–242, 2012.
  * [44] D. Thiruvady, M. Wallace, H. Gu, and A. Schutt.  A Lagrangian Relaxation and ACO Hybrid for Resource Constrained Project Scheduling with Discounted Cash Flows.  Journal of Heuristics, 20(6):643–676, 2014.
  * [45] R. R. S. van Lon, J. Branke, and T. Holvoet.  Optimizing agents with genetic programming: an evaluation of hyper-heuristics in dynamic real-time logistics.  Genetic Programming and Evolvable Machines, 19(1):93–120, 2017.
  * [46] Rinde R. S. van Lon, Juergen Branke, and Tom Holvoet.  Optimizing agents with genetic programming: an evaluation of hyper-heuristics in dynamic real-time logistics.  Genetic Programming and Evolvable Machines, 19(1):93–120, Jun 2018.
  * [47] F. Zhang, Y. Mei, S. Nguyen, and M. Zhang.  Evolving scheduling heuristics via genetic programming with feature selection in dynamic flexible job shop scheduling.  IEEE Transactions on Cybernetics, 2020.
  * [48] Fangfang Zhang, Yi Mei, Su Nguyen, and Mengjie Zhang.  Multitask multiobjective genetic programming for automated scheduling heuristic learning in dynamic flexible job-shop scheduling.  IEEE Transactions on Cybernetics, 53(7):4473–4486, 2023.
  * [49] Fangfang Zhang, Yi Mei, Su Nguyen, and Mengjie Zhang.  Survey on genetic programming and machine learning techniques for heuristic design in job shop scheduling.  IEEE Transactions on Evolutionary Computation, pages 1–1, 2023.
  * [50] Fangfang Zhang, Yi Mei, and Mengjie Zhang.  A two-stage genetic programming hyper-heuristic approach with feature selection for dynamic flexible job shop scheduling.  In Proceedings of the Genetic and Evolutionary Computation Conference, pages 347–355. ACM, 2019.


anonymous

# 4Doodle: Two-handed Gestures for Immersive Sketching of Architectural Models

Fernando Fonseca<EMAIL_ADDRESS>Maurício Sousa
<EMAIL_ADDRESS>Daniel Mendes<EMAIL_ADDRESS>Alfredo Ferreira<EMAIL_ADDRESS>Joaquim Jorge
INESC-ID Técnico Lisboa<EMAIL_ADDRESS>Av Rovisco Pais S/N 1049-001
Lisboa Portugal

###### Abstract

Three-dimensional immersive sketching for content creation and modeling has
been studied for some time. However, research in this domain mainly focused on
CAVE-like scenarios. These setups can be expensive and offer a narrow
interaction space. Building more affordable setups using head-mounted displays
is possible, allowing greater immersion and a larger space for user physical
movements. This paper presents a fully immersive environment using bi-manual
gestures to sketch and create content freely in the virtual world. This
approach can be applied to many scenarios, allowing people to express their
ideas or review existing designs. To cope with known motor difficulties and
inaccuracy of freehand 3D sketching, we explore proxy geometry and a laser-
like metaphor to draw content directly from models and create content
surfaces. Our current prototype offers 24 cubic meters for movement, limited
by the room size. It features infinite virtual drawing space through pan and
scale techniques and is larger than the typical 6-sided cave at a fraction of
the cost. In a preliminary study conducted with architects and engineers, our
system showed a clear promise as a tool for sketching and 3D content creation
in virtual reality with a great emphasis on bi-manual gestures.

###### keywords:

bi-manual gestures, 3D sketching, virtual reality, immersive environments,
spacial interactions, content creation

H.5.2Information Interfaces and PresentationUser InterfacesInput devices and
strategies H.5.2Information Interfaces and PresentationUser
InterfacesInteraction styles I.3.4Computer GraphicsGraphics UtilitiesPaint
systems I.3.7Computer GraphicsThree-Dimensional Graphics and RealismVirtual
Reality

##  1 Introduction

Freehand sketching on paper is a highly trained sensorimotor skill used daily
by most designers and architects to provide an understandable view of their
ideas. It appears in different project phases serving the cognitive processes
[kheng Lim 2003]. For example, in some architectural work-flows, sketches are
used for creative purposes, materializing initial ideas and concepts that will
eventually lead to complete buildings, similar to the known works of Frank
Gehry111Gehry Partners, LLP: https://www.foga.com/. Moreover, sketches can be
used when reviewing existing projects in architecture, engineering, and other
fields, either complementing the model with new shapes or creating annotations
of important remarks.

Several solutions for 2D sketching exist, following the pen and paper metaphor
[Olsen et al. 2009]. On the other hand, the interest from both academic
research and industry for extending sketches to the third dimension has been
increasing [Deisinger et al. 2000, Keefe et al. 2001, Keefe et al. 2008].
While a skill such as pen and paper sketching that has been mastered since the
early stages of our lives can hardly be compared with a mostly unfamiliar
combination of virtual environments and 3D freehand sketching techniques,
these later approaches allow for a more direct 3D content creation, allowing
the user to directly sketch in 3D and, at the same time, visualize the virtual
environment from several angles.

While desktop modeling solutions have been a standard until now, they offer a
very small space for visualizing and interacting with digital content. Also,
the two-dimensional view of the virtual environment provides limited
perspective, offering no depth of perception. Stereoscopic tabletops can
overcome some challenges but still have a small interaction space and only
allow for scale model interaction metaphors. Other solutions, such as CAVE
systems or head-mounted displays, can co-locate the user and the model at a
one-to-one scale. These immersive solutions allow users to use their movements
to navigate the virtual environment and sketch in first-person, thus creating
a more intimate relationship between the creator and the artifact.

Figure 1: Our vision of the immersive solution for sketching on 3D content.

Previous works for 3D sketching mainly rely on tracked tools within CAVE-like
scenarios [Israel et al. 2009, Keefe et al. 2001, Keefe et al. 2008, Israel et
al. 2013], but assembling an entire CAVE setup can be expensive. This paper
presents an affordable system that offers a whole room for freehand 3D
sketching. We adopt the Oculus Rift222http://www.oculusvr.com head-mounted
display and an OptiTrack333http://www.naturalpoint.com/optitrack more system
to create a prototype that is completely immersive and accurate, while
achieving a great relation between cost and physical interaction volume.
Indeed, the built-in accelerometer/gyro system already contained in the HMD,
while great for simple locomotion and exploration tasks, is unsuitable for
precision co-location due to drift and stability. The optical tracking system
provides fast and accurate locations of different objects in 3-space.

We use the head-mounted display within a tracking space of 24 cubic meters,
providing the ability to walk and rotate inside the virtual world. Combining
this with a set of devices enables free bi-manual 3D sketching inside that
virtual world, creating a powerful tool with countless different applications,
as depicted in Figure 1. We can engage users in various scenarios by changing
the system’s background and virtual models, creating different possibilities.
For instance, our approach supports quickly materializing new ideas or
reviewing existing models, enabling users to directly sketch on existing model
surfaces in an immersive 3D design review system, which previous work has
already shown to be useful in the design review process [Santos et al. 2007].

In our prototype, the user can freely navigate and sketch in the virtual space
or the existing virtual surfaces. However, the lack of drawing surfaces makes
it difficult to place content in three-dimensional spaces precisely. To ease
this task, we created a proxy geometry tool similar to the one presented in
3D6B Editor [Kallio 2005] and a point laser-like tool to draw in distant
surfaces. We also developed bi-manual gestures to allow the creation of fast
objects and primitives to help express ideas with volume. To enable design
review thought navigation in a one-to-one scale, we can control the virtual
world using pan and scale actions, similar to Grabbing the Air [Bowman et al.
2004, Stoakley et al. 1995]. With these, our system features 24 cubic meters
for physical movement, limited by the room size, and infinite virtual
sketching space.

##  2 Related Work

Addressing the challenge of sketching 3D in a 2D space, Kallio et al. [Kallio
2005] developed a system that enables creating sketches with complex non-
planar 3D strokes while retaining the essence of a pen and paper-based
sketching projecting 2D input form a single viewport to a grid surface that
can be manipulated in real-time. Other studies showed that freehand drawing in
the air needs additional motor coordination compared to pen and paper
counterparts [Deisinger et al. 2000, Mäkelä 2004, Mäkelä et al. 2004]. These
air-sketching studies were also revealed to be less detailed and accurate.
More recently Wiese et al. [Wiese et al. 2010] conducted a study investigating
the learnability in immersive ffreehandsketching, their results suggest
significant sketch quality enhancement over time, however no change in the
time needed to complete the given tasks was noticed.

With CavePainting, Keefe et al. [Keefe et al. 2001] showed that creating
artistic content in a virtual reality environment is possible by using only a
collection of simple brush tools. Makela et al. [Mäkelä et al. 2004] also
stated that their study subjects affirmed that this immersive sketching system
offers new potential for artistic expression. Moreover, a study conducted by
Israel et al. [Israel et al. 2009] showed that three-dimensional line-based
sketching, using pen interactions to keep the similarities of 2D sketching on
paper, provided results regarding the benefits of 3D sketching and its special
features in the design process. Also, Israel et al. [Israel et al. 2013]
allowed designers to model life-size forms in real-time with four different
approaches, searching the potential of immersive modeling even though no
materiality is present. The results suggest that it is possible to achieve
professional manipulative skills within virtual environments comparable to
their work with physical material. Perkunder et al. [Perkunder et al. 2010]
also used 3D sketched strokes as input in an immersive 3D environment to
support automatic shape creations. They compared line-based sketching and
sketch-based modeling, concluding that the usability of a creative sketching
task was perceived to be higher for line-based sketching than for sketch-based
modeling.

Combining augmented reality through head-mounted displays with cameras and
freeform fabrication technology, Yee et al. [Yee et al. 2009] allowed 3D
sketching with live 3D references. The authors used the Optitrack motion
capture system to track the user’s head and wand position and orientation.
Cabral et al. [Cabral et al. 2011] developed an immersive system that allows
the manipulation of simple house elements, such as rooms, doors, and windows.
This work showed that immersive systems can also be used for the initial
conceptual design of architectural models.

Regarding selection and manipulation techniques for 3D interactions, some
methods were developed using virtual pointer metaphor-based techniques. Bowman
et al. [Bowman and Hodges 1997] presented a ray-casting technique where the
user can select an object by pointing a ray to it. Another technique to select
object is based in flashlight and aperture, in this method user uses a
pointing ray as well but it replaces the virtual ray with a conic selection
volume. A modification of this technique originated the aperture technique
that allows the user to control the spread of the selection volume, and the
pointing directions are defined by the 3D position of the tracked head
location and the position of the hand sensor [Forsberg et al. 1996]. Another
selection technique consists of the image-plane family [Pierce et al. 1997],
allowing the user to select an object using only 2DOF by selecting and
manipulating the object in the projection image.

Moreover, virtual hand techniques were developed to allow direct manipulation.
A simple virtual hand technique simulates everyday object interactions, making
them natural. This technique directly maps the user’s hand motion to a virtual
hand’s motion in a virtual environment [Bowman et al. 2004]. Poupyrev et al.
attempted to improve this technique and developed Go-Go [Poupyrev et al.
1996], allowing users to change the virtual arm’s length interactively.

Regarding travel task scenarios using manual manipulation techniques, one
explored method is to allow the user to grab the air. In this technique, when
the user gestures to grab at any point in the virtual world and then moves
their hand, the world as a whole moves while the viewpoint remains stationary
[Bowman et al. 2004].

Other methods to control the user viewpoint have been explored, and the Head
Tracking method to change the viewport position and orientation is a good
example of this [Bakker et al. 1998]. This approach is the most natural and
direct way to change the user viewpoint, and it has been shown that physical
turning leads to higher levels of spatial orientation than virtual turning.
Our system combines most of the techniques discussed to achieve an easy-to-use
immersive sketching system.

##  3 Setup Overview

Figure 2: Our setup consists of an Oculus Rift (A), a Wiimote (B), and a ring
wireless mouse (C). All these devices are tracked using markers.

Our vision is to allow the user to perform freehand sketching inside a virtual
space, taking advantage of an entire physical room. We use OptiTrack, a
motion-tracking system that allows rigid-body triangulation and provides real-
time position and orientation to follow the user inside the room. Our system
uses ten cameras strategically positioned around the room, covering roughly 24
cubic meters (4 x 3 x 2 meters) of interaction space. The physical dimensions
and encumbrance of the room used limit this setup. If a larger room were
available, our setup could support larger design spaces, limited only by
camera resolution.

The system has Oculus Rift, a head-mounted display solution that offers
stereoscopic visualization out of the box to provide an immersive
visualization of the virtual space.

Combining the head-mounted display with visual markers that can be tracked by
our motion capture system, as depicted in Figure 2.A, the system can map the
users’ head position and orientation from the physical to the virtual world.
This ability, allied with a small battery and a wireless HMDI device inside a
small backpack, frees the user of any wire limitation, turning the Oculus Rift
and our system wireless with an insignificant input lag. With the immersive
stereoscopic visualization provided by this head-mounted display, we can allow
the user to move on to the physical world and perceive the same movement in
the virtual space.

Visual markers were fitted in a Wiimote to mimic a common pen, as depicted in
Figure 2.B. This combination allows the physical device to be represented in
the virtual world, matching its movements and orientation in space. Using this
pen in the dominant hand, the user has haptic feedback to freehand sketch in
the virtual world.

In order to add more features to our prototype, the user’s non-dominant hand
is instrumented with visual markers and two buttons, as outlined in Figure
2.C. This technique opens more input possibilities to the system and enables
non-dominant hand gestures. Since both hands have markers, our system also
explores bi-manual gestures.

Our prototype combines the data received from the OptiTrack system, the
signals from both-hand buttons, and the Oculus Rift in the Unity3D rendering
engine.

##  4 4Doodle

The developed system, depicted in Figure 3, followed an iterative process,
with several tests to obtain feedback and improve the system. Some of the
process thoughts and decisions will be demonstrated in this section. Since the
user is immersed in the virtual world and does not see his physical
surroundings, we provide some virtual visual clues. The most important is the
drawing pen, which is physically located in the user’s dominant hand and works
as a drawing instrument that mimics all the user’s hand movements and
rotations. The virtual representation is the same as the real device, the
Wiimote 3D model.

When the user touches the Wiimote buttons, they change color to give the user
additional visual feedback. Although there are many buttons, we decided to use
only two so the user’s hand doesn’t need to constantly change position while
searching for other buttons on the remote controller and can fully concentrate
on creating virtual content.

On the virtual Wiimote representation’s front edge is a small sphere
representing the interaction point. This sphere changes in size and color
depending on the chosen writing trace size, color, and interaction mode.

Our system enables different interaction modes, including a freehand sketching
mode in which the user can freely draw in three-dimensional space. Another
mode is laser sketching, which differs from the normal mode since the sketch
is projected directly on the surface where the pen is pointing. The prototype
also has a mode to create primitives and a mode to allow the user to select
and manipulate any virtual 3D object pre-existent or made in the virtual
scenario. These interactions will be further explained in the next sections.

###  4.1 Air Sketching

Figure 3: user sketching a line in our system. A user is on the left, and his
virtual point of view is on the right.

Our initial approach for sketching lines was cylindrical billboards. This
solution worked well when the user was static creating his sketch, although
when the user started to move around, the billboard effect began to notice a
strange feeling that the sketch was moving along with the user. This sensation
is caused by the billboard’s properties of rotating themselves to always face
the camera and the fact that we have two cameras rendering at the same time,
one for each eye. To solve this problem, we adopted a tube approach, creating
cylinders instead of billboard lines. This gives the sketch a sense of
tridimensional volume that was not very clear with the billboard approach. We
also used a self-illuminated shader, so shadows did not affect the sketches.

Sketching in a 3D space instead of a 2D paper is more difficult [Deisinger et
al. 2000, Mäkelä 2004, Mäkelä et al. 2004]. Aware of this, we developed a tool
to add restrictions and help with more accurate tasks. Inspired by the work in
the 3D6B editor [Kallio 2005], we created a plane to help restrict the drawing
to a 2D space. This tool allows the user to position a semi-transparent grid
plane anywhere in the virtual space and sketch it restricted to that plane
surface. Initially, we allowed a complete orientation-free plane, where the
user could position the plane at any angle in the three axes. However, by
observation and commentaries, we noticed that users usually use this tool to
help sketch objects and when they desire to accomplish perpendicular or
parallel lines. With this in mind, we restrict the plane tool’s orientation to
snap at 15 degrees on each axis. This constraint allows easy perpendicular or
parallel restrictions and better feedback from the subjects. This tool is
depicted in the Figure 4.A.

Figure 4: Two possibilities to place the proxy geometry plane: directly
positioning it with the pen (A) or pointing at the desired surface (B).

Since our system aims to provide the ability to make 3D sketches on existing
models, we developed another method to use the plane tool. Freely positioning
a plane exactly on a surface is as difficult as sketching in 3D. To ease this
task, we give the possibility to position the semi-transparent grid plane
directly in any existing surface in the virtual world and automatically adjust
the grid size to the surface size. To position the plane, the user uses the
pen as a virtual pointer, aiming at the desired surface (depicted in Figure
4.B). This approach allows users to sketch on top of any object’s face or
extend the drawing along that infinite virtual plane created by our tool.
These options are accessible in the two buttons on the user’s non-dominant
hand while the plane is toggled on. After the plane is positioned, to give
visual feedback that the pen is snapped to the plane’s surface, an arrow is
displayed on the back end of the pen, giving the user direct feedback. The
user can then sketch in two different modes, using the distance between the
hands to switch between them. If the hands are closer than a threshold, the
pen will draw straight lines and snap to the grid squares on the auxiliary
plane tool. Otherwise, the pen will freely draw in the 2D plane’s space if the
hands are farther away than a specified threshold.

Using a laser-like metaphor, we give users another way to draw on the desired
surfaces. In this mode, an auxiliary ray is shown to give the user visual
feedback on where they will draw. The user can sketch directly on any surface
without restrictions, Figure 5. When the user starts to sketch in these modes,
an ink drop object is displayed in the back end of the virtual Wiimote to give
additional visual feedback.

Figure 5: Sketching on existing 3D model’s surfaces using the laser tool.

###  4.2 Painter’s Palette

We can create a virtual dynamic menu attached to the users’ hands by equipping
the user’s non-dominant hand with a rigid body marker. The menu attached to
the hand is displayed by facing the palm upwards, as shown in Figure 3; facing
the palm downwards is hidden. Using this implementation of a painter’s palette
metaphor, we can keep the field of view clear when the menu is not needed and
avoid unwanted menu selections while sketching.

Our menu gives a set of different options to change modes and tools. The
options allow you to change the sketching line size and color, toggle the
auxiliary grid plane display, control the world, create primitives, switch
between laser and free sketching, or select and manipulate objects. The user
hovers the button with the pen’s edge to select any of these options. A
highlight will appear, giving visual feedback and helping avoid unwanted
selections. The user must press the sketching button on his dominant hand to
confirm the choice. Also, to avoid starting to draw while trying to select an
option, we deactivate the ability to sketch while the pen is floating near the
menu. If the color option is selected, a sub-menu will appear, which will
allow you to change the sketching color. The currently selected color appears
in the center of the menu, as well as the Wiimote tip. The lines size option
also pops a sub-menu that offers different line sizes with toggle buttons.

###  4.3 Grabbing the air

Figure 6: Three different bi-manual gestures to create a primitive: (A) non-
dominant hand facing upwards, the primitive is created with uniform scale, (B)
non-dominant hand facing the dominant hand, the primitive edges are located in
each user’s hand, to define size and height, (C) non-dominant hand facing
down, the primitive bottom plane is snapped to the ground plane and the hands
define the height and size.

The world option activates the possibility of manipulating the virtual world.
The user can manipulate the world by using the buttons on their non-dominant
hand. To scale the world, the user presses the button and approximates the
hands to lower the scale or moves away from the hands to increase it. The user
can also reset the scale to the initial size by pressing the respective button
in the menu. While pressing the other button, the user controls the virtual
world with a pan gesture. For example, by pressing the button at arm’s length
and making the gesture of pulling, like he is pulling the world to him, this
gesture is depicted in Figure 8, and it is an adaptation of the grabbing the
air technique [Bowman et al. 2004, Stoakley et al. 1995]. The same behavior
happens in any direction in the three different axes.

Since we allow the user to move the virtual world, he can lose the notion of
the physical tracker limits. To keep the user aware of his physical movement
limits, we always render a wired cube present like he is inside a glass box.

Figure 7: Scaling gesture using both hands.

###  4.4 Create and manipulate

The crate menu option allows the user to create one from a set of primitives.
The user selects the primitive and uses bi-manual gestures to rapidly and
naturally define the primitive’s volume. They can dynamically change the
volume creation method using the non-dominant hand orientation. If the palm of
their non-dominant hand faces the dominant hand, the volume of the primitives
will be defined between both hands, like the opposite edges were located in
each hand. This way, a person can freely define the primitive volume with a
bi-manual gesture (Figure 6.B). However, if the non-dominant hand faces
upwards, the primitive will always maintain a uniform scale, and the person
can use the distance between both hands to define the size (Figure 6.A). In
this case, the primitive changes color to gold to give additional visual
feedback. If the non-dominant hand faces downwards, the primitive will be
created from the ground plane, and the user defines the size and height using
both hands’ positions (Figure 6.C). While the user defines the primitive, its
material is semi-transparent, so they can see through it and help position the
object where they want to. When they finalize the primitive, it turns into a
solid material. Before using the bi-manual gestures approach to dynamically
switch between the primitive creation methods, we tried using the left-hand
buttons to switch between the modes. However, users had more difficulties
mapping the buttons to the desired creation method than with the gestures,
which tended to be more immediate.

By changing the pen mode to selection, the user can manipulate every primitive
he created and any pre-existing objects in the scene in 6-DOF. To this end,
the user moves the Wiimote inside the primitive. When there is a collision
between the object and the user’s dominant hand pen virtual representation,
the object’s color slightly changes to give additional visual feedback to the
user. The user needs to press the Wiimote button and select the object,
showing a highlight shading around it. This procedure can be applied to
multiple objects at the same time. The user can then freely manipulate the
selected objects by pressing the other Wiimote button. This technique is based
on the Virtual Hand technique [Bowman et al. 2004]. We also allow the user to
snap the object he is manipulating to any other existing one by facing the
sides of the object to each other. While the user is manipulating an object,
the non-dominant hand menu turns into a garbage bin. If the user releases an
object inside the bin, it is destroyed. This method lets the user remove any
unwanted object from the virtual scene.

##  5 Preliminary Evaluation

Figure 8: Pan gesture using the user’s non-dominant hand.

We prepared a qualitative study with inexperienced users to evaluate our
system’s potential. Our goal was to understand their receptivity to our
system. In this evaluation, we wanted to verify whether our system’s features
were easy and useful for users and whether they could really help them
complete some tasks.

###  5.1 Apparatus

For this evaluation, we used our setup located in our lab, as mentioned above.
Thus, it guarantees a calm and controlled environment. Eleven subjects, two
males and two females, participated in our experiments. Since we wanted to
evaluate our system with potential users, we gathered a group of six
architects from a PhD course and five engineers from both Masters and PhD
courses. Participants ranged from 25 to 60 years old (where 82% were between
25 and 34 years old). None of the selected subjects had contact with our
prototype before; only one had previously experienced head-mounted displays
with no position tracking.

###  5.2 Methodology

Our evaluation included three different scenarios where users could sketch.
The first was an enclosed virtual room, encouraging the user to move around
the physical space, while the second and third were open virtual spaces
requiring navigation features.

The first scenario consisted of a closed room, where the surrounding walls
represent the limits of the physical room. This scenario also contains a
floating cube in the middle, which the user can freely go through, Figure 9.
In this scenario, we explained how the system works without explaining the God
mode features and let users freely sketch and get used to the system for
fifteen minutes. After this time, we asked users to draw in the floating cube
sides, adding doors, windows, and a roof. During this trial, we encouraged
users to try using the auxiliary plane tool and also to switch between pen and
laser tools.

Figure 9: Scenarios used in our evaluation. One consists of a closed room with
a floating cube (A), and the other is an open field with a model of a house
(B)

In the second scenario, subjects had an open space with a 3D model of a house
without textures. Here, we explained the features of world manipulation and
scale and how they work. We gave the user ten minutes to get used to it. After
being ready, we asked to draw a door and two windows in an existing yellow
wall of the house. After completing this task, we asked to create an extension
to the house (a cube coming out of the wall) in a red wall on the other side
of the house, using primitives.

For the third task, in an empty scenario, we asked the users to be creative
and create a small neighborhood using the features of our prototype, with at
least five different objects representing different buildings.

After completing the tasks, subjects were asked to answer a questionnaire.
Overall, each session in the experiment took around fifty minutes, although no
time restrictions were imposed.

###  5.3 Results

The questionnaire users answered was composed of questions with six values
Likert scale (1 - strongly disagree, 6 - strongly agree) to classify some
aspects of the system and open-answer questions. From these surveys, we could
collect interesting results.

None of the subjects showed relevant body fatigue, but when asked, they
revealed that they felt more tired after using the system but did not feel it
while using it. They indicated that this fatigue was especially caused by
eyestrain due to the head-mounted display. Since our prototype setup is
wireless, we asked our subjects if they felt any delay between their movements
and what they saw through the head-mounted display. 63% of the subjects didn’t
feel any input lag; the others only reported minor momentary lag, probably
related to the momentary loss of a rigid body by the tracking system.

Regarding the system acquaintance, subjects strongly agree that with more
time, their results would certainly be better (Figure 10). From this chart, it
is also possible to verify that subjects agreed that as long as they got more
used to the system, the sketches became more precise. This fact was already
evidenced in previous studies [Wiese et al. 2010]. Subjects also agreed that
they had a good spatial perception of the virtual environment and could
coordinate their movements with what they saw in the virtual world.

Figure 10: Mean values for perception and system acquaintance along time.
Figure 11: Mean times regarding tools easiness to use.

From the graph of Figure 11, we can notice that all subjects agreed the tools
in our developed prototype are easy to use. This outcome results from the
iterative process of developing our system. It is also possible to notice that
all the prototype’s tools were considered useful, as shown in Figure 12.

However, the laser tool was considered the least useful and easiest. The
opposite happened with the plane tool, regarded as the least easy to use but
the most useful tool. One subject even said, during the experiment, that the
laser tool does the same as the plane tool but with less accuracy since it can
be used from far away.

Figure 12: Mean times regarding tools usefulness.

When asked about the bi-manual gestures implemented in our system, the
subjects strongly agreed they were well mapped to the respective feature (mean
time of 5,27 in 6 points). From all the gestures in our prototype, the least
liked by the subjects was the one to control the menu visibility and its
relation to the pen being snapped to the proxy geometry plane tool when it was
present (Figure 13). Along with the gesture to control the menu visibility,
the gesture to scale the world was also a least liked one. In this case,
subjects complained that the virtual scale was happening too fast. On the
other hand, the gestures to change the primitive creation method were the most
liked ones, and when asked if these gestures make the primitive creation task
fast, they all strongly agreed (mean time 5,36 out of 6 points).

Figure 13: Mean times regarding gestures easiness to use.

On the questionnaires, subjects highlighted our system’s usefulness for 3D
sketching and content creation, especially for 3D model design review. They
also highlighted that with the fast primitive creation, they could easily add
some volume detail to a model and sketch on it to add any necessary detail.

###  5.4 Observations

From the subject’s observations, we could gather some interesting
observations. Architects in our trials frequently mentioned the experience and
said the system’s potential was amazing. One of them, who had experience in
virtual reality systems, said that our system was the first real immersive
experience he had ever had. This same subject was especially impressed by the
lines’ volume. Subjects frequently got engaged with our prototype so that they
did more than they were asked to, as exemplified in Figure 14. In this
example, besides drawing windows, doors, and roofs to the cube, a user added a
fence using the plane tool several times. Another example is Figure 15, where
the subject sketched some high buildings, representing a neighborhood, for our
third task.

Figure 14: Example of a sketch made by one of the participants on the floating
cube scenario. Figure 15: scenario created by a subject during our evaluation
in task 3.

The majority of the subjects had some depth perception difficulties when
sketching. Usually, they were static while drawing in the intended space, and
when they rotated or moved, they perceived that the line was not exactly in
the desired place. This symptom was reduced after participants used the system
for a while.

In general, subjects easily adapted to the auxiliary plane tool and frequently
used it to aid in the desired tasks. One architect also said that it was the
perfect sketching aid tool, and the plane’s positioning snapping was useful
because it allows one to sketch in parallel and perpendicular planes to
existent sketches or surfaces. Another architect subject stated that the plane
tool was more natural and easy to use than his CAD applications. However, only
four subjects used the plane tool when sketching the door and windows in the
house’s yellow wall. The others preferred the laser tool far from the house,
except for one subject who started using it and then decided to resort to the
plane tool since it was more accurate.

We also noticed that, although participants could hide the menu easily, some
tended to forget that they could do it; this was seen in our evaluation, where
we noticed that this was the least liked gesture (Figure 13. Subjects also
tend to forget that they could use their body to move around the virtual world
after we explain how they can use the ability to manipulate the virtual world
position and scale. Two subjects even asked during the experiment how to
rotate the world so they were facing the intended model surface instead of
rotating their own body. This artifact might happen because we are used to
controlling virtual environments while seated and looking at a static monitor.

Some users gave us suggestions on how to improve our system. One suggested
that boolean operations between objects could be interesting and useful in
opening more possibilities for content creation. Another suggestion was to
have gestures to deform the primitives created. They also suggested
implementing more bi-manual gestures. One example was to face the hand palm
forward while the user was creating a primitive object. This gesture would
snap the primitive creation to the closest object in front of the user,
similar to the facing-down gesture that snaps one’s face to the ground plane.
Participants also suggested using the laser tool to select two or more points
and then draw straight lines or curves between them, mimicking the pen’s
behavior when it is snapped to the auxiliary plane grid.

Other subjects suggested that it would be interesting to have a rubber tool to
erase just some small spots of a drawn sketch instead of history. The same
subjects stated the possibility of having a gesture to change the drawing
color while sketching without relying on the menu to change the color. One
user in our evaluation also suggested using a shake gesture to delete objects
instead of our approach of releasing the objects inside the garbage bin.

##  6 Conclusion and Future Work

Sketching is an important part of several creative processes. In this work, we
presented an immersive system for 3D air sketching. In our system, users can
promptly materialize new ideas or review existing virtual models, sketching
and creating primitives on and around them. We implemented several features to
aid in this process, such as basic functionality to change stroke width and
color, or more advanced ones, such as a proxy geometry plane tool for
restricting sketches to two dimensions, distant lase-like sketching, primitive
creation, and a navigate and scale mode to enable a vast virtual world. All
these features in our prototype were developed using bi-manual gestures to
make them easier and more natural for the users.

A preliminary evaluation of our system with six architects and five engineers
showed that users enjoyed and found our immersive solution very useful. Users
also thought of it as a very promising design review tool. The proxy geometry
plane, primitive creation, and the ability to manipulate and scale the
environment were very helpful. The subjects praised using bi-manual gestures
to enhance the interactions, especially the ones used to create primitives
differently.

We plan to add further capabilities to our prototype and perform more
iterations on existing features. To increase its functionality and fulfill our
vision to get closer to a world builder application, we intend to explore
another type of geometrical content creation, such as planar or volumetric
shapes, using 2D form recognition from the freehand sketches and combine this
with object surface extrusion, similar to what has been done in Mockup Builder
[De Araùjo et al. 2012]. Also, adding a 3D object retrieval system will allow
creating richer virtual environments. We feel that the possibility of using
bi-manual gestures to deform existing primitives or to implement boolean
operations between primitives could also be an interesting addition to our
prototype.

Furthermore, we plan to extend the concepts of proxy geometry and simple
sketch-based construction rules to explore richer interaction and modeling
scenarios. For example, while using the geometry plane proxy, explore other
bi-manual gestures to allow curve definitions and not only lines. Still,
regarding the auxiliary plane, we also think it would be useful to provide
some gestures to allow the simultaneous placement of several planes to aid in
more complex spatial drawings. We also want to explore the concept of object
groups and develop bi-manual gestures to allow fast replication and
dynamically change group copies.

We want to extend the physical interaction space to fully take advantage of
our wireless VR setup. Combining these with augmented reality can also yield
interesting results. We also think that we can get rid of the virtual menu and
develop an interface relying only on bi-manual gestures. It would also be
interesting to evaluate both interaction techniques.

## References

  * [Bakker et al. 1998] Bakker, N., Werkhoven, P., and Passenier, P. 1998\.  Aiding orientation performance in virtual environments with proprioceptive feedback.  In Virtual Reality Annual International Symposium, 1998. Proceedings., IEEE 1998, IEEE, 28–33.
  * [Bowman and Hodges 1997] Bowman, D. A., and Hodges, L. F. 1997\.  An evaluation of techniques for grabbing and manipulating remote objects in immersive virtual environments.  In Proceedings of the 1997 Symposium on Interactive 3D Graphics, ACM, New York, NY, USA, I3D ’97, ACM, 35–ff.
  * [Bowman et al. 2004] Bowman, D. A., Kruijff, E., LaViola, J. J., and Poupyrev, I. 2004\.  3D User Interfaces: Theory and Practice.  Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA.
  * [Cabral et al. 2011] Cabral, M., Vangorp, P., Chaurasia, G., Chapoulie, E., Hachet, M., and Drettakis, G. 2011\.  A multimode immersive conceptual design system for architectural modeling and lighting.  In 3D User Interfaces (3DUI), 2011 IEEE Symposium on, ACM, 15–18.
  * [De Araùjo et al. 2012] De Araùjo, B. R., Casiez, G., and Jorge, J. A. 2012\.  Mockup builder: Direct 3d modeling on and above the surface in a continuous interaction space.  In Proceedings of Graphics Interface 2012, GI ’12, Canadian Information Processing Society, 173–180.
  * [Deisinger et al. 2000] Deisinger, J., Blach, R., Wesche, G., Breining, R., and Simon, A. 2000\.  Towards immersive modeling - challenges and recommendations: A workshop analyzing the needs of designers.  In In Proc. of the 6th Eurographics Workshop on Virtual Environments, Eurographics, 145–156.
  * [Forsberg et al. 1996] Forsberg, A., Herndon, K., and Zeleznik, R. 1996\.  Aperture based selection for immersive virtual environments.  In Proceedings of the 9th Annual ACM Symposium on User Interface Software and Technology, ACM, New York, NY, USA, UIST ’96, ACM, 95–96.
  * [Israel et al. 2009] Israel, J. H., Wiese, E., Mateescu, M., Zöllner, C., and Stark, R. 2009\.  Sketch-based interfaces and modeling (sbim): Investigating three-dimensional sketching for early conceptual design-results from expert discussions and user studies.  Comput. Graph. 33, 4 (Aug.), 462–473.
  * [Israel et al. 2013] Israel, J. H., Mauderli, L., and Greslin, L. 2013\.  Mastering digital materiality in immersive modelling.  In Proceedings of the International Symposium on Sketch-Based Interfaces and Modeling, SBIM ’13, ACM, 15–22.
  * [Kallio 2005] Kallio, K. 2005\.  3d6b editor: Projective 3d sketching with line-based rendering.  In Eurographics Workshop on Sketch-Based Interfaces and Modeling, The Eurographics Association, 73–79.
  * [Keefe et al. 2001] Keefe, D. F., Feliz, D. A., Moscovich, T., Laidlaw, D. H., and LaViola, Jr., J. J. 2001\.  Cavepainting: A fully immersive 3d artistic medium and interactive experience.  In Proceedings of the 2001 Symposium on Interactive 3D Graphics, I3D ’01, ACM, 85–93.
  * [Keefe et al. 2008] Keefe, D. F., Acevedo, D., Miles, J., Drury, F., Swartz, S. M., and Laidlaw, D. H. 2008\.  Scientific sketching for collaborative vr visualization design.  IEEE Transactions on Visualization and Computer Graphics 14, 4 (July), 835–847.
  * [kheng Lim 2003] kheng Lim, C. 2003\.  An insight into the freedom of using a pen: Pen-based system and pen-and-paper.  In In Proc. 6th Asian Design International Conference.
  * [Mäkelä et al. 2004] Mäkelä, W., Reunanen, M., and Takala, T. 2004\.  Possibilities and limitations of immersive free-hand expression: A case study with professional artists.  In Proceedings of the 12th Annual ACM International Conference on Multimedia, MULTIMEDIA ’04, ACM, 504–507.
  * [Mäkelä 2004] Mäkelä, W. 2004\.  Drawing, painting, and sculpting in the air: Development studies about an immersive free-hand interface for artists. worksop paper.  In in IEEE VR 2004, IEEE.
  * [Olsen et al. 2009] Olsen, L., Samavati, F. F., Sousa, M. C., and Jorge, J. A. 2009\.  Sketch-based modeling: A survey.  Computers & Graphics 33, 1, 85–103.
  * [Perkunder et al. 2010] Perkunder, H., Israel, J. H., and Alexa, M. 2010\.  Shape modeling with sketched feature lines in immersive 3d environments.  In Proceedings of the Seventh Sketch-Based Interfaces and Modeling Symposium, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SBIM ’10, 127–134.
  * [Pierce et al. 1997] Pierce, J. S., Forsberg, A. S., Conway, M. J., Hong, S., Zeleznik, R. C., and Mine, M. R. 1997\.  Image plane interaction techniques in 3d immersive environments.  In Proceedings of the 1997 Symposium on Interactive 3D Graphics, ACM, New York, NY, USA, I3D ’97, ACM, 39–ff.
  * [Poupyrev et al. 1996] Poupyrev, I., Billinghurst, M., Weghorst, S., and Ichikawa, T. 1996\.  The go-go interaction technique: Non-linear mapping for direct manipulation in vr.  In Proceedings of the 9th Annual ACM Symposium on User Interface Software and Technology, ACM, New York, NY, USA, UIST ’96, 79–80.
  * [Santos et al. 2007] Santos, P., Stork, A., Gierlinger, T., Pagani, A., Araújo, B., Jota, R., Bruno, L., Jorge, J., Madeiras Pereira, J., Witzel, M., Conti, G., Amicis, R., Barandarian, I., Paloc, C., Machui, O., Jiménez, J., Bodammer, G., and McIntyre, D. 2007\.  Improve: Collaborative design review in mobile mixed reality.  In Virtual Reality, R. Shumaker, Ed., vol. 4563 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 543–553.
  * [Stoakley et al. 1995] Stoakley, R., Conway, M. J., and Pausch, R. 1995\.  Virtual reality on a wim: Interactive worlds in miniature.  In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, CHI ’95, 265–272.
  * [Wiese et al. 2010] Wiese, E., Israel, J. H., Meyer, A., and Bongartz, S. 2010\.  Investigating the learnability of immersive free-hand sketching.  In Proceedings of the Seventh Sketch-Based Interfaces and Modeling Symposium, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SBIM ’10, 135–142.
  * [Yee et al. 2009] Yee, B., Ning, Y., and Lipson, H. 2009\.  Augmented reality in-situ 3d sketching of physical objects.  In Intelligent UI Workshop on Sketch Recognition, ACM.