# Designing Human-Robot Coexistence Space

Jixuan Zhi, Lap-Fai Yu and Jyh-Ming Lien1 1 Zhi, Yu and Lien are with the
Department of Computer Science, George Mason University, 4400, University
Drive MSN 4A5, Fairfax, VA 22030 USA<EMAIL_ADDRESS>
###### Abstract

When the human-robot interactions become ubiquitous, the environment
surrounding these interactions will have significant impact on the safety and
comfort of the human and the effectiveness and efficiency of the robot.
Although most robots are designed to work in the spaces created for humans,
many environments, such as living rooms and offices, can be and should be
redesigned to enhance and improve human-robot collaboration and interactions.
This work uses autonomous wheelchair as an example and investigates the
computational design in the human-robot coexistence spaces. Given the room
size and the objects $O$ in the room, the proposed framework computes the
optimal layouts of $O$ that satisfy both human preferences and navigation
constraints of the wheelchair. The key enabling technique is a motion planner
that can efficiently evaluate hundreds of similar motion planning problems.
Our implementation shows that the proposed framework can produce a design
around three to five minutes on average comparing to 10 to 20 minutes without
the proposed motion planner. Our results also show that the proposed method
produces reasonable designs even for tight spaces and for users with different
preferences.

##  I Introduction

More than ever, robots are designed and developed to work with and around
humans. Inevitably, humans and robots in their day-to-day life are going to
share a common space. While most robots, in particular humanoid robots, are
designed to work in the existing environments designed for human activities,
we envision that the shared space are likely to evolve in the near future to
better accommodate and enhance the ever increasing human-robot interaction and
collaboration. During the decades after personal vehicles were invented, we
redesigned the roads and streets to adjust to the vehicle size, speed, traffic
volume and, more importantly, the behaviors of the drivers in these cars.
Similarly, as robots are moved from industrial and laboratory settings into
our personal spaces, the spaces must also adopt to the robots to increase the
humans’ safety and comfort and the robot’s efficiency.

This paper pioneers the computational design of human-robot coexistence space.
We propose to formulate the design problem as an optimization problem subject
to constraints from both human’s preferences and robot’s motion limitations.
This simple but flexible framework allows us to create multiple design
recommendations within a few minutes. The key technical challenge is to
overcome the bottleneck resulted from the repeated calls to the motion planner
during the optimization process. From our study, motion planning takes more
than 95% of the computation time.

In this paper, we focus on designing spaces, such as living rooms and offices,
that maximize the accessibility of a wheelchair robot and a person with mobile
disability. Fig. 1 shows the designs with and without the consideration of
wheelchair motion. Although we will use self-driving wheelchair throughout
this paper, it should be noted that the proposed framework can be easily
adjusted and extended to consider different settings and scenarios.

Figure 1: The figure on the left is a bad layout design because the lamp is
blocked by the other furniture. The figure on the right is a better design
produced by the proposed framework because all the objects are accessible by
the wheelchair robot entering from the door.

Main contributions. This paper presents the first computational method
considering the optimization of the space shared by human and robot. The paper
also contributes the first nonholonomic motion planner that adopts the
solutions obtained from earlier motion planning problems to solve more
problems in similar but new workspaces. This new planner can efficiently plan
wheelchair motions in hundreds to thousands similar environments in just a few
minutes.

Figure 2: An overview of the proposed design method. Given the room size and
objects, with user-defined Action-Object relation graph, our approach
generates scenes and paths that satisfy the human preferences and wheelchair
motion constraints.

##  II Related work

While there has been extensive work on computational design for living spaces,
there is little effort on designing human-robot coexistence spaces. A major
technical challenge in designing a human-robot coexistence space is an ultra
fast planner that solves motion planning problems in many similar
environments. In this section, we will review prior works in both areas.

###  II-A Computational Design of Space Planning

Computational design of spaces is usually formulated as an optimization
problem. We group these works in rule-based and activity-based methods. In
this work, we use both rule-based and activity-based representations for human
preferences and robot motions, respectively.

####  II-A1 Rule-based methods

The first set of methods use user-defined rules to express the preferences of
the object placement; for example, the sofa must be against a particular wall
and the TV set must face the sofa. For example, Yu et al. [1] proposed to
iteratively change positions and orientations of objects to satisfy these
design rules. Based on [1], Li et al. [2] generated virtual indoor scenarios
used for wheelchair training. These rules can also be learned from a handful
of examples [3, 4]. More recently, various neural-network methods [5, 6] have
been proposed to encode these rules in the latent space from a vast number of
examples and have shown to create more complex scenes.

####  II-A2 Activity-based methods

These methods synthesize indoor scenes with human-centric inference based on
the fact that human activities have a strong effect on arrangement of objects.
For example, Fisher et al.[7] learned an activity model from a database of 3D
models and scenes and, based on the activity model, new scenes are generated.
Several activity models have been proposed, such as activity map [8], action
graph [9], activity-associated object relation graphs [10] or probabilistic
grammar model [11]. In this paper, an activity model is used to infer the how
the wheelchair robot may move around a room.

###  II-B Motion Planning in Similar Environments

Motion planning methods that utilize previous experiences to solve new
problems can be categorized into space-based methods and trajectory-based
methods.

####  II-B1 Space based methods

Space-based methods learn to plan in similar environments from a
representation of the workspace. For example, Lien and Lu [12] proposed to
construct and store local roadmaps around obstacles, then retrieve and merge
those local roadmaps into a global roadmap when given a similar new
environment. Similarly, Experience Graph [13, 14, 15] represents the
connectivity of a workspace. Chamzas et al. [16] used local experiences to
global motion planning. They sample and store local maps by local primitives,
and then synthesize a global map based on the local maps.

Beyond graph representations, Ogay and Kim [17] proposed to represent a motion
planning algorithm as a random process that is controlled by a heuristic as a
distribution of random variables. A machine learning method then learns to
relate the obstacle distribution and the heuristics to better control the
motion planner. Gaussian Mixture Models have been used to represent collision
possibility in high dimensional configuration space [18]. Ichter et al. [19]
proposed to sample configurations from the learned latent space conditioned on
the new planning problem. Kim et al. [20] developed a novel representation of
planning problem instance called score-space, based on similarity in score
space, they can transfer knowledge from previous problems to solve new task.

####  II-B2 Trajectory based methods

Trajectory based methods learn to plan in similar environments from recorded
trajectories. For example, Berenson et al. [21] introduced a framework that
consists of two parts: one for planning-from-scratch, and the other for
retrieving and repairing paths stored in the database. Saha et al. [22, 23,
24, 25] introduced new machine learning-based algorithms to record a sequence
of robot action around obstacles that are reused in more complex environments.
Similar to the space-based methods, Gaussian Mixture Models have also been
used to estimate the likelihood of reusing existing trajectories and generate
new trajectories in the new environments [26].

When optimality of the trajectory is considered, Hauser [27] proposed the
Learning Global Optima (LGO) framework to approximate global optimization that
the planner could retrieve and adapt from a library of optimal solutions.

Although it is developed with a different objective in mind, trajectory
prediction [28, 29] often reuses and generalizes computations obtained from
the previous situations.

##  III Optimization Framework of HR-Space Design

This section introduces the building blocks used in the proposed design
framework. Fig. 2 illustrates the proposed framework that uses a motion
planner and human preferences to evaluate the space layouts. The framework
also uses an action-object relation graph [9, 10] that encodes the
interactions between the human in the wheelchair and the objects in the room.
These interactions will determine the importance of a given trajectory and how
much the trajectory should influence the design of the room layout. To
simplify our discussion, we will use wheelchair to refer to the human in the
wheelchair robot for the rest of this paper when the context is clear.

###  III-A Action-Object Relation Graph

Figure 3: The action object relation graph. Edge thickness represents the
transition probability between two objects.

In a given room, objects inside the room play an important role in defining
the activities of humans and robots. These activities in turn define how
humans and robots may move around the room. Therefore it is natural to produce
design recommendations based these object-derived activities. To accomplish
this, we use action-object relation graph (AO graph) [10]. As shown Figure 3,
an AO graph is similar to the state diagram of Markov chain. More
specifically, an AO graph reveals the activity-associated objects relation.
This is a weighted directed graph $G=(V,E)$, the nodes $V$ represent the
objects. The edges point from one node to another node or a node to itself,
and the edge weight is the transition probability from one object to another
object or staying still at the current object. In this work, the weight
measures how likely a wheelchair may move from one object to another.
Realistic weights can be estimated from sensors observing human activities [9,
10].

Given an AO graph, we determine the likelihood of the a sequence of objects
that the wheelchair may visit. That is, from the AO graph, we can determine
$M$ most possible sequences that encode different visiting orders of objects
in a room. Throughout this paper, $M=10$ is used. Given a sequence
$s=\\{o_{i}\\}$ of objects in the room and their corresponding transition
probabilities $\\{p_{i}\\}$ from the AO graph, the likelihood of the path is
defined as $L(s)=\Pi_{i}p_{i}$. For each of these $M$ sequences, we use the
wheelchair motion planner (detailed in the next sections) to determine if a
path exists for visiting all objects in the sequence. In Section III-D, we
will describe how the information gathered by the motion planner combined with
the user-defined preferences can be used to evaluate a room layout.

###  III-B Baseline Wheelchair Motion Planning

We now sketch the baseline motion planner that models a wheelchair as a
nonholonomic car [30] and uses a variant of Rapidly-exploring Random Trees
(RRT) [31] that expands its search using the Reed-Shepp (RS) curves [32]. In
Section IV, this baseline planner will be replaced using a significantly more
efficient planner designed for solving many copies of similar problems.

The baseline motion planner works as follows: in every step, it first
generates a uniformly sampled configuration $(x,y,\theta)$ with a biased
sampling strategy which has 80% probability of selecting the goal
configuration and 20% probability of picking the random configuration. The
planner then finds the closest node in the search tree. Instead of Euclidean
distance, the travel distance defined over RS curves is used to determine the
closest node. For computational efficiency, it is not desirable to calculate
the RS curves from the sample to every node in the tree. Instead, the planner
approximates this by selecting $k$ closest nodes using the weighted Euclidean
distance metric and then finding the nearest node with the minimum RS-curve
distance among those $k$ nodes. The weighted Euclidean distance metric
linearly combines the translation in Cartesian space and the change of the
orientation between two configurations.

The planner then connects the sample to the closest node using the shortest RS
curve between them. In our implementation, if the target configuration is the
goal, the entire curve up to the first invalid configuration is added;
Otherwise, we add at most $n=5$ steps of the RS curve into the tree. Finally,
the planner checks whether the newly generated edge is in collision with
obstacles. Those obstacles include furniture and walls. Only collision-free
edges and vertices are added to the tree. The process repeats until the tree
reaches the goal.

###  III-C Touring the Room

Given a sequence of objects $\\{o_{i}\\}$ that the wheelchair should visit, we
now determine a tour that allows the robot to stop by each object. To this
end, we should determine a sequence of configurations, one for each object, so
the path connecting consecutive configurations in the sequence is collision
free. Therefore, these configurations should not be randomly created. In fact,
they should be sampled around the objects and should be oriented so that the
person sitting in the wheelchair is facing the object. To achieve this, we
uniformly sample $N$ configurations around each object, and each configuration
is oriented toward the reference point of the object. The value $N$ is
proportional to the perimeter of the object and the size of the wheelchair. An
example of the sampled configurations around the bed is shown in Fig. 4.

Figure 4: Left: The uniform sampled configurations shown as the red spheres
around the bed. The blue arrow represents the orientation of the sampled
configurations. Right: The uniform sampled points around the bed and TV. A
valid path in blue between bed and TV can be computed between the sampled
points.

Given the sampled configurations around the objects $\\{o_{i}\\}$ in a given
sequence, such as from the door to TV, dresser and bed in Fig. 4(left), we
wish to find a collision-free path that visits all objects in that sequence
and satisfies the nonholonomic constraint. We solve this problem using a
branch-and-bound approach. To connect objects $o_{i}$ and $o_{j}$, all pairs
of configurations, one from $o_{i}$ and one from $o_{j}$, are sorted based on
their RS-curve lengths. Starting from the closest pair, the pairs are
iteratively evaluated by the motion planner until a valid path is found. Fig.
4(right) shows an example of such a path between the bed and the TV. Once a
path $\pi_{ij}$ between $o_{i}$ and $o_{j}$ is determined, we move on to the
next pair in the sequence, e.g., $o_{j}$ and $o_{k}$. If we cannot find a path
connecting $o_{j}$ and $o_{k}$ by extending $\pi_{ij}$, we backtrack to
$o_{i}$ and $o_{j}$ and find another valid (but this time longer) path between
$o_{i}$ and $o_{j}$. This process repeats until a collision-free path visiting
$\\{o_{i}\\}$ in the given order is found.

Recall that, in each layout design optimization iteration, the method
described in this section must be applied to all $M=10$ sequences obtained
from the AO graph. As detailed in the next section, these $M$ tours will be
used to evaluate the accessibility of the design.

###  III-D Evaluating a Layout Design

The quality of a design is encoded as the weighted sum of two cost terms. One
cost term describes the accessibility of the room, and the other represents
how the placement of the objects reflects the human preferences. More
specifically, the quality of a layout design is expressed as $C_{total}$:

$C_{total}=(\sum_{P}L(s_{P})\mathbf{C_{P}})\mathbf{w_{p}^{T}}+\mathbf{C_{I}w_{I}^{T}}\
,$ (1)

where $P$ is a path, $\mathbf{C_{P}}$ and $\mathbf{C_{I}}$ are vectors of path
and object costs, respectively, and $\mathbf{w_{P}}$ and $\mathbf{w_{I}}$ are
vectors of weights. While $\mathbf{w_{P}}$ is partially derived from the
provided AO graph, $\mathbf{w_{I}}$ is defined based human preferences.
Because our optimization frame work considers multiple paths (tours) generated
from the object sequences in the AO graph, the accessibility cost is defined
as the sum of all path costs weighted by the likelihood $L(s_{P})$, where
$s_{P}$ is a sequence of objects visited by the path $P$. Lower $C_{total}$
indicates a better design. Details of the cost terms are described below.

####  III-D1 Path Cost

The path cost $\mathbf{C_{P}}=[C_{P}^{l},C_{P}^{r},C_{P}^{c}]$ evaluates the
length, accumulated rotation, and clearance of the path, respectively. A
shorter and wide path with fewer turns is considered to be better path than a
longer, narrower path with many turns. Note that if the path cannot be found,
the path cost is a large number based on the room size. Given a path with $N$
waypoints and the $i$-th waypoint has position $p_{i}$ and orientation
$r_{i}$, the path cost terms are defined as follows.

Path Length Cost $C_{P}^{l}$. The path length is the sum of the distances
between consecutive waypoints along the path. Suppose there is a forward path
with $M$ waypoints, then the path length is defined as:

$C_{P}^{l}=\sum_{i=1}^{N-1}{||p_{i+1}-p_{i}||}\ .$ (2)

Path Rotation Cost $C_{P}^{r}$. Each waypoint has its orientation information,
the path rotation could be computed as the sum of difference of orientation
between nearby waypoints. Since we have $N$ waypoints.

$C_{P}^{r}=\sum_{i=1}^{N-1}{||r_{i+1}-r_{i}||}\ .$ (3)

Path Clearance Cost $C_{P}^{c}$. The path clearance cost determines how narrow
or wide a path is. It is computed as the mean width of the waypoints.

$C_{P}^{c}=\frac{1}{N}\sum_{i=1}^{N}{(||p_{i}-q_{i}||+||p_{i}-w_{i}||)}\ .$
(4)

where $q_{i}$ and $w_{i}$ is the position of object which is closest to the
waypoint position $p_{i}$ on the left and right side.

Path Cost Weight $\mathbf{w_{P}}$. Generally speaking, the weights
$\mathbf{w_{P}}$ determine how the path costs can be combined. We define the
weights $\mathbf{w_{P}}=\alpha[w_{P}^{l},w_{P}^{r},w_{P}^{c}]$, where $\alpha$
is a scaling factor of the user defined parameters $w_{P}^{l}$, $w_{P}^{r}$,
$w_{P}^{c}$ that express the importance of the path length, rotation and
clearance in the optimization process. The value of $\alpha$ is determined
based on the Action-Object Relation Graph (AO graph). Recall that, from
Section III-A, we obtained multiple object sequences from the AO graph. To
define $\alpha$, let us first define the scale factor $\alpha_{i}$ of $o_{i}$,
which is determined by the likelihood of each sequence and the frequency of
$o_{i}$ appeared in the sequences containing $o_{i}$. More specifically, for
each object $o_{i}$ in a sequence $s$, we count the object occurrences as
follows: if $o_{i}$ is the start or end of $s$, $o_{i}$ is counted once,
otherwise $o_{i}$ is counted twice as $o_{i}$ will appear in two path segments
in $s$.

Then the frequency $freq_{s}(o_{i})$ of $o_{i}$ can be determined by the
counts divided by total counts in the sequence $s$. In addition, each sequence
$s$ also has a likelihood $L(s)$ defined from the AO Graph. Combined with the
likelihood $L(s)$ of all sequences containing $o_{i}$, the scaling factor
$\alpha_{i}$ of $o_{i}$ is $\sum_{s\in S}L(s)freq_{s}(o_{i})$, where $S$ is
all sequences containing $o_{i}$. Finally, we have
$\alpha=\sum_{i}\alpha_{i}$.

####  III-D2 Interior design cost

This cost estimates how the object placement reflects human preferences.
Therefore, we consider the spatial relationship between objects, including the
spatial relationship between each object and its nearest wall. Certain
objects, such as a TV and a couch, have a pairwise relationship including
their mutual distance and orientation. Suppose that there is a pairwise
relation set $S$ including all pairs of objects.

Pairwise Distance Cost $C_{I}^{d}$. Every object in the room has a determined
distance to its nearest wall and may also have a distance preference from
other objects. This distance cost determines the spatial relationships between
objects. The target distance can be set by user. The cost is defined as:

$C_{I}^{d}=\sum_{\forall{i,j}\in S}({||o_{i}-o_{j}||-d_{i,j}})^{2}\ ,$ (5)

where $o_{i}$ and $o_{j}$ are the positions of objects $i$ and $j$, and
$d_{i,j}$ is the user-defined target distance.

Pairwise Rotation Cost $C_{I}^{r}$. Another spatial relationship between
objects is pairwise orientation. Each object has a relative orientation to its
nearest wall and may have a desired relative orientation to other objects. For
example, one might require the TV and the couch to face each other. The
rotation cost is then defined as:

$C_{I}^{r}=\sum_{\forall{i,j}\in
S}({||\theta_{i}-\theta_{j}||-\theta_{i,j}})^{2}$ (6)

where $\theta_{i}$ and $\theta_{j}$ are the orientations of objects $i$ and
$j$, and $\theta_{i,j}$ is the user-defined target relative angle.

###  III-E Layout Optimization

We now are ready to describe how the proposed method creates a realistic
layout by minimizing the costs. To this end, we apply a simulated annealing
method [33] with a Metropolis-Hasting algorithm [34, 35]. Let us first define
a Boltzmann-like objective function for state $(P,I)$:

$f(P,I)=exp(-\frac{1}{t}C_{total}(P,I))\ ,$ (7)

where $P$ is the set of paths touring the room, $I$ is the object layout, $t$
is the temperature parameter, which decreases over the iterations.

In each iteration, our method chooses a move to change the present
configuration $(P,I)$ to a new configuration $(P^{\prime},I^{\prime})$. There
are two types of moves: (1) change the position of the object, and (2) change
the orientation of the object. Once the layout $I^{\prime}$ is updated, we
proceed to find new paths $P^{\prime}$. With annealing schedule, the optimizer
explores the solution space with large moves in the beginning, and tunes the
configuration with small moves in the end.

The new proposed configuration $(P^{\prime},I^{\prime})$ is accepted with a
probability based on Metropolis criterion:

$Prob(P^{\prime},I^{\prime}|P,I)=min(1,\frac{f(P^{\prime},I^{\prime})}{f(P,I)})\
.$ (8)

In the beginning of each iteration, the optimizer may aggressively accepts any
move, even a bad one, when the temperature is high. As the temperature
decreases, the optimizer is less likely to accept a bad move.

##  IV Planning Motion in Similar Environments

A major challenge in developing the computational framework proposed in the
previous section is the motion planning, which, as we will see in the
experimental section, takes more than 95% of the total computation. Although
there exist planners that exploit similarities among problems, they usually
focus on a handful, instead of hundreds, of similar problems, and do not
consider nonholonomic constraints. This section presents several new
techniques that maximize computation reuse, thus the overall motion planning
cost is significantly reduced.

###  IV-A Decompose C-Space using Reed-Shepp Words

Figure 5: Approximate partition the configuration space into different regions
by RS words. Samples with the same color are a region with the shared word.
There are in total of 48 regions.

We propose to decompose the configuration space based on the shortest Reed-
Shepp (RS) curves with the wheelchair starting at the center of the room. Each
region in the decomposition is a set of points that share the same RS words.
Similar decomposition has been studied using analytic methods [36, 37].
However, to the best of our knowledge, these methods remained in theory and
the only practical implementation is only available for Dubin’s car [38].

We propose to approximate the decomposition via adaptive sampling. We first
create $K=1000$ configurations sampled uniformly from the configuration space
of an empty room that has the size double that of the original room. For each
sample $s$, we compute the shortest RS-curve and its associated RS-word from
the center of the room. We then incrementally add more samples. For each
additional sample $s$ (also sampled uniformly from the C-space), we first find
the closest sample $s^{\prime}$. If $s$ and $s^{\prime}$ share identical RS
word, then $s$ is discarded. Otherwise, $s$ is added to the samples. This
process is repeated until 100 consecutive failures are encountered. Fig. 5
shows the resulting partition of the C-space into 48 regions with the
rotational radius of the wheelchair equals to three meters. We call this
partition RS-decomposition.

When a query configuration $q$ is given, the RS-curve of $q$ can then be
estimated using the RS-word of $q$’s nearest point in the RS-decomposition.
With a proper data structure, such as a KD tree, this can be done efficiently
by avoiding the evaluation of all 48 cases in determining the shortest RS
curve. However, because RS-decomposition is only an approximation, the RS-word
obtained via the closest sample might be incorrect or even invalid. To avoid
this, the baseline RRT planner is modified so that the random configurations
that pull the tree into unexplored regions are only sampled from the existing
configurations in the RS-decomposition. We see about 40% reduction in
computation time without noticeable differences in the found paths.

###  IV-B Path Reuse

While RS-decomposition allows us to precompute and reuse RS-curves, it is
agnostic to the changes of the designed layout. It is also important to know
that, the difficulty of the motion planning problems changes over time as the
optimization progresses. That is, when the optimization is just started, the
layout tends to be chaotic and changes dramatically, and the problem of
finding a tour visiting objects in the scene is difficult. As the optimization
converges, the layout design stabilizes, and finding a tour becomes easier. In
this section, we present ways to utilize this observation and further speed up
the motion planner both within an optimization iteration and between
iterations.

Reusing paths within the optimization iteration. In each iteration, multiple
sequences of objects are evaluated. These sequences share many common
trajectories. Therefore, we reuse these trajectories among the sequences
whenever it is possible. To achieve this, we maintain a database of
trajectories, each of which is indexed by the pair of objects and their
corresponding samples that the trajectory connects. Note that some
trajectories may become invalid due to the displacement of objects in the
scene which may result in collision or invalidate the associated RS curves.
Once detected, an invalid trajectory is removed from the database.

Reusing paths from the earlier optimization iterations. As the optimization
process converges, the similarity between consecutive optimization iterations
increases. This allows the opportunity of reusing paths obtained from the
earlier iterations. When the motion planner needs to find a path between these
objects, it looks up the database built from the earlier iterations and
extracts a potential path for the new layout. The path is then transformed to
the new location and orientation. If the transformed path is not feasible, the
planner finds a new path and updates the database.

###  IV-C RRT Reuse

Figure 6: Number of RRT iterations needed for finding a valid path.

Similar to the case of reusing the paths, as the optimization converges, the
changes to the layout decreases. Therefore, it is in fact possible that we can
reuse a large portion of the tree. In particular, if the position of RRT root
does not change much, we can reuse the tree from the previous optimization
iteration. From our study shown in Fig. 6, the number of RRT iterations needed
to find a path successfully is generally small. Consequently, we do not need
many nodes in the reused tree. Therefore, if the reused tree grows too large,
it may be more time consuming to expand the tree. In addition, objects can be
displaced in each iteration, and, if the tree is too large, nodes in the tree
can easily become invalid. Therefore, we rebuild a new tree when the total
number of tree node is larger than a user-defined number. In all of our
experiments, 30, as indicated in Fig. 6, is used.

##  V Experiments and Result

In this section, we report and compare the computation times needed to create
a design using the baseline and proposed motion planners. We further study the
effects of room size and the AO graph to the designs created by the proposed
method. We implemented our method on a MacBook Pro laptop with 2.2GHz Inter
Core i7 and 16 GB memory. The proposed optimization framework and the motion
planners are implemented in C# in Unity. We demonstrate how our method can be
applied in three different room types: bedroom, office, and living room. For
each environment, we extract 10 most possible sequences from a given AO graph.
The maximum number of optimization iterations in our simulated annealing is
700 for all experiments.

###  V-A Time Comparison

Motion planning takes on average 96.06% of the total computation time of the
optimization framework. Naturally, we first show that the the proposed motion
planning method based on the technique described in Sec. IV is significantly
faster than the baseline planner. Fig. 7 shows the average path planning time
(in minutes) in three different environments. The data is collected from 10
runs for each environment. As shown in the results, the proposed planner
significantly outperforms the baseline planner in all cases. The proposed
method reduces the planning time between 65% to 70%. Fig. 8 shows four
recommended layout designs for each room type. The trajectory shown for each
design represents the tour of an objects sequence that has the largest
probability according to the given AO graph.

Figure 7: Path planning time using the baseline planner and the proposed
planner. The planning time is 96.06% of the total running times.

###  V-B Optimal Design in a Small Room

To test the proposed method in a smaller room, we reduce the bedroom boundary
length by 20%, so the area of the new room is 36% smaller. Fig. 9 shows two
designs of the smaller bedroom. The layouts are similar to those of the larger
room. However, since the bedroom is more crowed, the motion planner takes much
more time. The average path finding time in the small room is 30% higher than
that of the original bedroom.

###  V-C Planner with different AO graphs

Because our method considers accessibility in the scene synthesis, different
user activities (encoded in the AO graphs) should affect the designs of the
human-robot shared space. Fig. 10 shows two layouts created from with two
different AO graphs. For path cost weight, we set
$\mathbf{w_{P}}=\alpha_{i}[1,1,1]$, where $\alpha_{i}$ is AO-graph dependent
and $[1,1,1]$ indicates that path length, rotation and clearance are equally
important. These two AO graphs differ in the transition probabilities of the
wheelchair moving (from other objects) to the office table and round table.
Because of these difference, recall the definition of the path cost weight in
Section III-D1, the scale factors $\alpha_{i}$ of the office table and round
table consequently become different in these two examples. The AO graph used
in the left figure of Fig. 10 results in a larger scaling factor thus a larger
path cost weight of the office table than the weight of the round table, and
the AO graph used in the right figure results in a smaller scaling factor. We
observe that the objects with larger weight are more likely to be placed in
the area of the room that is more accessible from the door.

Figure 8: Four layout designs and a path covering three objects in each of the
bedroom (top), office (mid), and living room (bottom). In all three examples,
the wheelchair starts from door.

Figure 9: Two different layout designs for a small bedroom.

Figure 10: Two layout designs for the office with different AO graphs. Left:
the office table has a larger weight than the round table. Right: the round
table has a larger path cost weight than the office table.

##  VI Conclusion

This paper presented the first known optimization framework for designing
human-robot shared spaces by considering human preferences and robot
constraints. We also proposed a novel nonholonomic motion planner that can
efficiently solve motion planning problems in many similar workspaces. The
experiments showed that our framework can generate reasonable layout designs,
and the proposed motion planner takes significantly less time than the
baseline planner. The experiments also showed that the method is consistent in
creating similar designs for more crowded spaces, and the differences in the
AO graphs can be reflected in the synthesized layouts.

One limitation of our work is that the number and type of objects in the room
are small. As the number of objects in the room increases, the number of
possible sequences and tours increases exponentially. Further research is
needed to overcome this. The second limitation is that only rectangular rooms
are considered. However, it should be straightforward to consider more complex
room boundaries.

## References

  * [1] L. F. Yu, S. K. Yeung, C. K. Tang, D. Terzopoulos, T. F. Chan, and S. J. Osher, “Make it home: automatic optimization of furniture arrangement,” _ACM Transactions on Graphics (TOG)-Proceedings of ACM SIGGRAPH 2011, v. 30,(4), July 2011, article no. 86_ , vol. 30, no. 4, 2011.
  * [2] W. Li, J. Talavera, A. G. Samayoa, J.-M. Lien, and L.-F. Yu, “Automatic synthesis of virtual wheelchair training scenarios,” in _2020 IEEE Conference on Virtual Reality and 3D User Interfaces (VR)_. IEEE, 2020, pp. 539–547.
  * [3] M. Fisher, D. Ritchie, M. Savva, T. Funkhouser, and P. Hanrahan, “Example-based synthesis of 3d object arrangements,” _ACM Transactions on Graphics (TOG)_ , vol. 31, no. 6, pp. 1–11, 2012.
  * [4] H. Xie, W. Xu, and B. Wang, “Reshuffle-based interior scene synthesis,” in _Proceedings of the 12th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and Its Applications in Industry_ , 2013, pp. 191–198.
  * [5] K. Wang, M. Savva, A. X. Chang, and D. Ritchie, “Deep convolutional priors for indoor scene synthesis,” _ACM Transactions on Graphics (TOG)_ , vol. 37, no. 4, pp. 1–14, 2018.
  * [6] M. Li, A. G. Patil, K. Xu, S. Chaudhuri, O. Khan, A. Shamir, C. Tu, B. Chen, D. Cohen-Or, and H. Zhang, “Grains: Generative recursive autoencoders for indoor scenes,” _ACM Transactions on Graphics (TOG)_ , vol. 38, no. 2, pp. 1–16, 2019.
  * [7] M. Fisher, M. Savva, Y. Li, P. Hanrahan, and M. Nießner, “Activity-centric scene synthesis for functional 3d scene modeling,” _ACM Transactions on Graphics (TOG)_ , vol. 34, no. 6, pp. 1–13, 2015.
  * [8] M. Savva, A. X. Chang, P. Hanrahan, M. Fisher, and M. Nießner, “Scenegrok: Inferring action maps in 3d environments,” _ACM transactions on graphics (TOG)_ , vol. 33, no. 6, pp. 1–10, 2014.
  * [9] R. Ma, H. Li, C. Zou, Z. Liao, X. Tong, and H. Zhang, “Action-driven 3d indoor scene evolution,” _ACM Transactions on Graphics (TOG)_ , vol. 35, no. 6, pp. 1–13, 2016.
  * [10] Q. Fu, X. Chen, X. Wang, S. Wen, B. Zhou, and H. Fu, “Adaptive synthesis of indoor scenes via activity-associated object relation graphs,” _ACM Transactions on Graphics (TOG)_ , vol. 36, no. 6, pp. 1–13, 2017.
  * [11] S. Qi, Y. Zhu, S. Huang, C. Jiang, and S.-C. Zhu, “Human-centric indoor scene synthesis using stochastic grammar,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 5899–5908.
  * [12] J.-M. Lien and Y. Lu, “Planning motion in environments with similar obstacles.” in _Robotics: Science and Systems_ , 2009.
  * [13] M. Phillips, B. J. Cohen, S. Chitta, and M. Likhachev, “E-graphs: Bootstrapping planning with experience graphs.” in _Robotics: Science and Systems_ , vol. 5, no. 1, 2012, p. 110.
  * [14] M. Phillips, A. Dornbush, S. Chitta, and M. Likhachev, “Anytime incremental planning with e-graphs,” in _2013 IEEE International Conference on Robotics and Automation_. IEEE, 2013, pp. 2444–2451.
  * [15] V. Hwang, M. Phillips, S. Srinivasa, and M. Likhachev, “Lazy validation of experience graphs,” in _2015 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2015, pp. 912–919.
  * [16] C. Chamzas, A. Shrivastava, and L. E. Kavraki, “Using local experiences for global motion planning,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 8606–8612.
  * [17] D. Ogay and E.-G. Kim, “Heuristics for motion planning based on learning in similar environments.” _J. Inform. and Commun. Convergence Engineering_ , vol. 12, no. 2, pp. 116–121, 2014.
  * [18] J. Huh, B. Lee, and D. D. Lee, “Adaptive motion planning with high-dimensional mixture models,” in _2017 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2017, pp. 3740–3747.
  * [19] B. Ichter, J. Harrison, and M. Pavone, “Learning sampling distributions for robot motion planning,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 7087–7094.
  * [20] B. Kim, Z. Wang, L. P. Kaelbling, and T. Lozano-Pérez, “Learning to guide task and motion planning using score-space representation,” _The International Journal of Robotics Research_ , vol. 38, no. 7, pp. 793–812, 2019\.
  * [21] D. Berenson, P. Abbeel, and K. Goldberg, “A robot path planning framework that learns from experience,” in _2012 IEEE International Conference on Robotics and Automation_. IEEE, 2012, pp. 3671–3678.
  * [22] O. Saha and P. Dasgupta, “Fast path planning using experience learning from obstacle patterns.” in _AAAI Spring Symposia_ , 2016.
  * [23] ——, “Real-time robot path planning around complex obstacle patterns through learning and transferring options,” in _2017 IEEE International Conference on Autonomous Robot Systems and Competitions (ICARSC)_. IEEE, 2017, pp. 278–283.
  * [24] ——, “Experience learning from basic patterns for efficient robot navigation in indoor environments,” _Journal of Intelligent & Robotic Systems_, vol. 92, no. 3-4, pp. 545–564, 2018.
  * [25] O. Saha, P. Dasgupta, and B. Woosley, “Real-time robot path planning from simple to complex obstacle patterns via transfer learning of options,” _Autonomous Robots_ , vol. 43, no. 8, pp. 2071–2093, 2019.
  * [26] T. Barbié, R. Kabutan, R. Tanaka, and T. Nishida, “Gaussian mixture spline trajectory: learning from a dataset, generating trajectories without one,” _Advanced Robotics_ , vol. 32, no. 10, pp. 547–558, 2018.
  * [27] K. Hauser, “Learning the problem-optimum map: Analysis and application to global optimization in robotics,” _IEEE Transactions on Robotics_ , vol. 33, no. 1, pp. 141–152, 2016.
  * [28] N. Jetchev and M. Toussaint, “Trajectory prediction in cluttered voxel environments,” in _2010 IEEE International Conference on Robotics and Automation_. IEEE, 2010, pp. 2523–2528.
  * [29] ——, “Fast motion planning from experience: trajectory prediction for speeding up movement generation,” _Autonomous Robots_ , vol. 34, no. 1-2, pp. 111–127, 2013.
  * [30] D. Dolgov, S. Thrun, M. Montemerlo, and J. Diebel, “Practical search techniques in path planning for autonomous driving,” _Ann Arbor_ , vol. 1001, no. 48105, pp. 18–80, 2008.
  * [31] S. M. LaValle, “Rapidly-exploring random trees: A new tool for path planning,” 1998.
  * [32] J. Reeds and L. Shepp, “Optimal paths for a car that goes both forwards and backwards,” _Pacific journal of mathematics_ , vol. 145, no. 2, pp. 367–393, 1990.
  * [33] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” _science_ , vol. 220, no. 4598, pp. 671–680, 1983.
  * [34] N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, “Equation of state calculations by fast computing machines,” _The journal of chemical physics_ , vol. 21, no. 6, pp. 1087–1092, 1953.
  * [35] W. K. Hastings, “Monte carlo sampling methods using markov chains and their applications,” 1970.
  * [36] P. Soueres and J.-P. Laumond, “Shortest paths synthesis for a car-like robot,” _IEEE Transactions on Automatic Control_ , vol. 41, no. 5, pp. 672–688, 1996.
  * [37] G. Desaulniers and F. Soumis, “An efficient algorithm to find a shortest path for a car-like robot,” _IEEE Transactions on Robotics and Automation_ , vol. 11, no. 6, pp. 819–828, 1995.
  * [38] A. M. Shkel and V. Lumelsky, “Classification of the dubins set,” _Robotics and Autonomous Systems_ , vol. 34, no. 4, pp. 179–202, 2001.


${\theta}(\hat{x},\hat{p})-$deformation of the harmonic oscillator in a
$2D-$phase space

M. N. Hounkonnou†,1 D. Ousmane Samary‡,1,2,
E. Baloïtcha∗,1 and , S. Arjika∗∗,1

$1$-International Chair in Mathematical Physics and Applications
(ICMPA-UNESCO Chair), University of Abomey-Calavi,
072B.P.50, Cotonou, Rep. of Benin

$2$-CNRS - Université Lyon 1, Institut Camille Jordan
(Bat. Jean Braconnier, bd du 11 novembre 1918),
F-69622 Villeurbanne Cedex, France

E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
[Ref-preprint] CIPMA-MPA/014/2012

This work addresses a ${\theta}(\hat{x},\hat{p})-$deformation of the harmonic
oscillator in a $2D-$phase space. Specifically, it concerns a quantum
mechanics of the harmonic oscillator based on a noncanonical commutation
relation depending on the phase space coordinates. A reformulation of this
deformation is considered in terms of a $q-$deformation allowing to easily
deduce the energy spectrum of the induced deformed harmonic oscillator. Then,
it is proved that the deformed position and momentum operators admit a one-
parameter family of self-adjoint extensions. These operators engender new
families of deformed Hermite polynomials generalizing usual $q-$ Hermite
polynomials. Relevant matrix elements are computed. Finally, a $su(2)-$algebra
representation of the considered deformation is investigated and discussed.

Pacs numbers:
Key words: Harmonic oscillator, energy spectrum, q-deformation, Hermite
polynomials, matrix
elements, $su(2)-$algebra

##  1 Introduction

Consider a $2D$ phase space $\mathcal{P}\subset\mathbb{R}^{2}.$ Coordinates of
position and momentum are denoted by $x$ and $p.$ Corresponding Hilbert space
quantum operators $\hat{x}$ and $\hat{p}$ satisfy the following commutation
relation

$\displaystyle[\hat{x},\hat{p}]=\hat{x}\hat{p}-\hat{p}\hat{x}=i\theta(\hat{x},\hat{p})$
(1)

where $\theta$ is the deformation parameter encoding the noncommutativity of
the phase space: $\theta(x,p)=1+\alpha x^{2}+\beta
p^{2},\,\,\alpha,\beta\in\mathbb{R}_{+}$ with the uncertainty relation:

$\displaystyle\Delta\hat{x}\Delta\hat{p}\geq\frac{1}{2}\Big{(}1+\alpha(\Delta\hat{x})^{2}+\beta(\Delta\hat{p})^{2}\Big{)}$
(2)

where the parameters $\alpha$ and $\beta$ are real positive numbers.

The motivations for this study derive from a series of works devoted to the
relation (1). Indeed, already in [11] Kempf et al investigated (1) for the
particular case $\alpha=0$ with

$\displaystyle\Delta\hat{x}\Delta\hat{p}\geq\frac{1}{2}(1+\beta(\Delta\hat{p})^{2})$
(3)

and led to the conclusion that the energy levels of a given system can deviate
significantly from the usual quantum mechanical case once energy scales become
comparable to the scale $\sqrt{\beta}.$ Although the onset of this scale is an
empirical question, it is presumably set by quantum gravitational effects. In
another work [8], Kempf, for the same model with $\alpha=0$, led to the
conclusion that the anomalies observed with fields over unsharp coordinates
might be testable if the onset of strong gravity effects is not too far above
the currently experimentally accessible scale about $10^{-18}m$, rather than
at the Planck scale of $10^{-35}m.$ More recently, in [10], it was shown that
similar relation can be applied to discrete models of matter or space-time,
including loop quantum cosmology. For more motivations, see [6], [1] and [5],
but also [7], [13], [12] and [14] and references therein.

In this work, we investigate how such a deformation may affect main
properties, e.g. energy spectrum, of a simple physical system like a harmonic
oscillator.

The paper is organized as follows. In section 2, we introduce a reformulation
of the $\theta(\hat{x},\hat{p})-$deformation in terms of a $q-$deformation
allowing to easily deduce the energy spectrum of the induced deformed harmonic
oscillator. Then it is proved that the deformed position and momentum
operators admit a one-parameter family of self-adjoint extensions. These
operators engender new families of deformed Hermite polynomials generalizing
usual $q-$ Hermite polynomials. Section 3 is devoted to the matrix element
computation. Finally, in section 4, we provide a $su(2)-$algebra
representation of the considered deformation. Section 5 deals with concluding
remarks.

##  2  $q$-like realization

It is worth noticing that such a $\theta(x,p)-$deformation (1) admits an
interesting $q-$like realization via the following re-parameterization of
deformed creation and annihilation operators:

$\displaystyle\hat{b}^{\dagger}=\frac{1}{2}(m_{\alpha}\hat{x}-im_{\beta}\hat{p}),\quad\hat{b}=\frac{1}{2}(m_{\alpha}\hat{x}+im_{\beta}\hat{p})$
(4)

satisfying the peculiar q-Heisenberg commutation relation:

$\displaystyle\hat{b}\hat{b}^{\dagger}-q\hat{b}^{\dagger}\hat{b}=1$ (5)

where the parameter $q$ is written in the form

$\displaystyle q=\frac{1+\sqrt{\alpha\beta}}{1-\sqrt{\alpha\beta}}\geq 1$ (6)

and the quantities $m_{\alpha}$ and $m_{\beta}$ are given by

$\displaystyle
m_{\alpha}=\sqrt{2\alpha\Big{(}\frac{1}{\sqrt{\alpha\beta}}-1\Big{)}},\quad
m_{\beta}=\sqrt{2\beta\Big{(}\frac{1}{\sqrt{\alpha\beta}}-1\Big{)}}.$ (7)

With this consideration, the spectrum of the induced harmonic oscillator
Hamiltonian $\hat{H}=\hat{b}\hat{b}^{\dagger}+\hat{b}^{\dagger}\hat{b}$ is
given by

$\displaystyle\mathcal{E}_{n}=\frac{1}{2}([n]_{q}+[n+1]_{q})$ (8)

where the $q-$number $[n]_{q}$ is defined by $[n]_{q}=\frac{1-q^{n}}{1-q}$.
Let $\mathcal{F}$ be a $q-$ deformed Fock space and
$\\{|n,q\rangle\;|\;n\in\mathbb{N}\bigcup\\{0\\}\\}$ be its orthonormal basis.
The actions of $\hat{b}$, $\hat{b}^{\dagger}$ on $\mathcal{F}$ are given by

$\displaystyle\hat{b}|n,q\rangle=\sqrt{[n]_{q}}|n-1,q\rangle,\;\mbox{ and
}\;\;\hat{b}^{\dagger}|n,q\rangle=\sqrt{[n+1]_{q}}|n+1,q\rangle,\;$ (9)

where $|0,q\rangle$ is a normalized vacuum:

$\displaystyle\hat{b}|0,q\rangle=0,\qquad\langle q,0|0,q\rangle=1.$ (10)

The Hamiltonian operator $\hat{H}$ acts on the states $|n,q\rangle$ to give:
$\hat{H}|n,q\rangle=\mathcal{E}_{n}|n,q\rangle.$

###### Theorem 2.1

The position operator $\hat{x}$ and momentum operator $\hat{p},$ defined on
the Fock space $\mathcal{F},$ are not essentially self-adjoint, but have a
one-parameter family of self-adjoint extensions.

Proof: Consider the following matrix elements of the position operator
$\hat{x}$ and momentum operator $\hat{p}$ :

$\displaystyle<m,q|\hat{x}|n,q>$ $\displaystyle:=$
$\displaystyle<m,q|\frac{1}{m_{\alpha}}(\hat{b}^{\dagger}+\hat{b})|n,q>$ (11)
$\displaystyle=$
$\displaystyle\frac{1}{m_{\alpha}}\sqrt{[n+1]_{q}}\delta_{m,n+1}+\frac{1}{m_{\alpha}}\sqrt{[n]_{q}}\delta_{m,n-1}$
(12) $\displaystyle<m,q|\hat{p}|n,q>$ $\displaystyle:=$
$\displaystyle<m,q|\frac{i}{m_{\beta}}(\hat{b}^{\dagger}-\hat{b})|n,q>$ (13)
$\displaystyle=$
$\displaystyle\frac{i}{m_{\beta}}\sqrt{[n+1]_{q}}\delta_{m,n+1}-\frac{i}{m_{\beta}}\sqrt{[n]_{q}}\delta_{m,n-1}.$
(14)

Setting $x_{n,\alpha}=\frac{1}{m_{\alpha}}\sqrt{[n]_{q}}$ and
$x_{n,\beta}=\frac{1}{m_{\beta}}\sqrt{[n]_{q}}$, then the position operator
$\hat{x}$ and momentum operator $\hat{p}$ can be represented by the two
following symmetric Jacobi matrices, respectively:

$\displaystyle
M_{\hat{x},q,\alpha}=\left(\begin{array}[]{cccccc}0&x_{1,\alpha}&0&0&0&\cdots\\\
x_{1,\alpha}&0&x_{2,\alpha}&0&0&\cdots\\\
0&x_{2,\alpha}&0&x_{3,\alpha}&0&\cdots\\\
\vdots&\ddots&\ddots&\ddots&\ddots&\ddots\end{array}\right)$ (19)

and

$\displaystyle
M_{\hat{p},q,\beta}=\left(\begin{array}[]{cccccc}0&-ix_{1,\beta}&0&0&0&\cdots\\\
ix_{1,\beta}&0&-ix_{2,\beta}&0&0&\cdots\\\
0&ix_{2,\beta}&0&-ix_{3,\beta}&0&\cdots\\\
\vdots&\ddots&\ddots&\ddots&\ddots&\ddots\end{array}\right).$ (24)

The quantity
$|x_{n,\alpha}|=\frac{1}{m_{\alpha}}\Big{|}\frac{1-q^{n}}{1-q}\Big{|}^{1/2}$
is not bounded since $q>1$ by definition, and
$\lim\limits_{n\rightarrow\infty}|x_{n,\alpha}|=\infty.$ Considering the
series $y_{\alpha}=\sum\limits_{n=0}^{\infty}1/x_{n,\alpha},$ we get

$\displaystyle\overline{\lim_{n\to\infty}}\left(\frac{1/x_{n+1}}{1/x_{n}}\right)=q^{-1/2}<1$

and, hence, the series $y_{\alpha}$ converges. Besides, as the quantity
$q^{-1}+q>2,$

$\displaystyle
0<x_{n+1,\alpha}x_{n-1,\alpha}=\frac{1}{m_{\alpha}^{2}(1-q)}\Big{[}1-q^{n}(q^{-1}+q)+q^{2n}\Big{]}^{1/2}<x_{n,\alpha}^{2}$
(25)

Hence, the Jacobi matrices in (19) and (24) are not self-adjoint (Theorem
1.5., Chapter VII in Ref. [2]). The deficiency indices of these operators are
equal to $(1,1)$. One concludes that the position operator $\hat{x}$ and the
momentum operator $\hat{p}$ are no longer essentially self-adjoint but have
each a one-parameter family of self-adjoint extensions instead. This means
that their deficiency subspaces are one-dimensional. $\square$

Besides, in this case, the deficiency subspaces $N_{z}$, $Imz\neq 0,$ are
defined by the generalized vectors
$|z\rangle=\sum\limits_{0}^{\infty}P_{n}(z)||n,q\rangle$ such that [2], [3]:

$\displaystyle\sqrt{[n]_{q}}P_{n-1}(z)+\sqrt{[n+1]_{q}}P_{n+1}(z)=zP_{n}(z)$
(26)

with the initial conditions $P_{-1}(z)=0,\;\;P_{0}(z)=1$.

  * •

In the position representation, the states $|x,q>$ such that

$\displaystyle\hat{x}|x,q>=x|x,q>,\mbox{
and}\,\,|x,q>=\sum_{n=0}^{\infty}P_{n,q}(x)|n,q>,$ (27)

transforms the relation (26) into

$\displaystyle m_{\alpha}xP_{n,q}(x)$ $\displaystyle=$
$\displaystyle\sqrt{[n+1]_{q}}P_{n+1,q}(x)+\sqrt{[n]_{q}}P_{n-1,q}(x)$ (28)
$\displaystyle n$ $\displaystyle=$ $\displaystyle
0,1,\ldots;\;P_{-1,q}(x)=0,\;P_{0,q}(x)=1$ (29)

giving

$\displaystyle
2\gamma(x,q)P_{n,q}\Big{(}\frac{2\gamma(x,q)}{(1-q)^{1/2}m_{\alpha}}\Big{)}$
$\displaystyle=$
$\displaystyle(1-q^{n+1})^{\frac{1}{2}}P_{n+1,q}\Big{(}\frac{2\gamma(x)}{(1-q)^{1/2}m_{\alpha}}\Big{)}$
(30) $\displaystyle+$
$\displaystyle(1-q^{n})^{\frac{1}{2}}P_{n-1,q}\Big{(}\frac{2\gamma(x,q)}{(1-q)^{1/2}m_{\alpha}}\Big{)}$
(31)

where $2\gamma(x,q)=(1-q)^{1/2}m_{\alpha}x.$

Setting
$\widetilde{P}_{n,q}(\gamma(x,q))=P_{n,q}\Big{(}\frac{2\gamma(x,q)}{(1-q)^{1/2}m_{\alpha}}\Big{)}$,
the equation (30) can be re-expressed as

$\displaystyle 2\gamma(x,q)\widetilde{P}_{n,q}(\gamma(x,q))$ $\displaystyle=$
$\displaystyle(1-q^{n+1})^{\frac{1}{2}}\widetilde{P}_{n+1,q}(\gamma(x,q))$
(32) $\displaystyle+$
$\displaystyle(1-q^{n})^{\frac{1}{2}}\widetilde{P}_{n-1,q}(\gamma(x,q)).$ (33)

Finally, putting $(q;q)_{n}^{1/2}\widetilde{P}_{n,q}(\gamma(x,q))=H_{n,q}(x),$
the formula (32) recalls the recurrence relation satisfied by $q-$Hermite
polynomials:

$\displaystyle 2xH_{n,q}(x)=H_{n+1,q}(x)+(1-q^{n})H_{n-1,q}(x)$ (34)

where $(q;q)_{n}=(1-q)(1-q^{2})\cdots(1-q^{n}).$

  * •

In the momentum representation, the state $|p,q>$ such that

$\displaystyle\hat{p}|p,q>=p|p,q>,\mbox{
and}\,\,|p,q>=\sum_{n=0}^{\infty}Q_{n,q}(p)|n,q>$ (35)

leads to the following reccurence relation between functions $Q_{n}(x,q):$

$\displaystyle im_{\beta}pQ_{n,q}(p)$ $\displaystyle=$
$\displaystyle\sqrt{[n+1]_{q}}Q_{n+1,q}(p)-\sqrt{[n]_{q}}Q_{n-1,q}(p)$ (36)
$\displaystyle n$ $\displaystyle=$ $\displaystyle
0,1,\ldots;\;Q_{-1,q}(p)=0,\;Q_{0,q}(p)=1.$ (37)

This equation can be also re-expressed as

$\displaystyle\tilde{\gamma}(\tilde{p},q)Q_{n,q}(p)=(1-q^{n+1})^{\frac{1}{2}}Q_{n+1,q}(p)-(1-q^{n})^{\frac{1}{2}}Q_{n-1,q}(p)$
(38)

where $\tilde{\gamma}(\tilde{p},q)=(1-q)^{1/2}m_{\beta}\tilde{p},$
$\tilde{p}=ip.$

Setting
$\widetilde{Q}_{n,q}(\tilde{\gamma}(\tilde{p},q))=Q_{n,q}\Big{(}\frac{2\tilde{\gamma}(\tilde{p},q)}{(1-q)^{1/2}m_{\alpha}}\Big{)}$,
then the equation (38) yields

$\displaystyle
2\tilde{\gamma}(\tilde{p},q)\widetilde{Q}_{n,q}(\tilde{\gamma}(\tilde{p},q))$
$\displaystyle=$
$\displaystyle(1-q^{n+1})^{\frac{1}{2}}\widetilde{Q}_{n+1,q}(\tilde{\gamma}(\tilde{p},q))$
(40)
$\displaystyle-(1-q^{n})^{\frac{1}{2}}\widetilde{Q}_{n-1,q}(\tilde{\gamma}(\tilde{p},q)).$

Letting
$(q;q)_{n}^{1/2}\widetilde{Q}_{n,q}(\tilde{\gamma}(\tilde{p},q))=H_{n,q}(ip),$
we arrive at the recurrence relation satisfied by the complex $q-$polynomials
$H_{n,q}(ip)$ given by

$\displaystyle 2ipH_{n,q}(ip)=H_{n+1,q}(ip)-(1-q^{n})H_{n-1,q}(ip).$ (41)

###### Remark 2.1

The following is worthy of attention:

  1. (i)

In the $x-$space where the momentum operator is defined by the relation

$\displaystyle\hat{p}:=-i\theta(\hat{x},\hat{p})\partial_{x},$ (42)

any function $\Psi_{q}(x)$ in $x-$representation can be expressed in terms of
its analog $\Psi_{q}(p)$ in $p-$representation by the relation

$\displaystyle\Psi_{q}(x)=\int_{-\infty}^{\infty}dp\,\exp\Big{(}\frac{ip}{\alpha\sigma(p)}\arctan\frac{x}{\sigma(p)}\Big{)}\Psi_{q}(p),$
(43)

where $\sigma(p)=\sqrt{p^{2}+\frac{1}{\alpha}}$. Defining the Hilbert space
inner product as

$\displaystyle<f,g>=\int\,\frac{dx}{\theta(\hat{x},\hat{p})}\bar{f}_{q}(x)g_{q}(x)$
(44)

one can readily prove that $\hat{p}$ reverts the property of a Hermitian
operator.

  2. (ii)

Analogously, in the $p-$space

$\displaystyle\hat{x}:=i\theta(\hat{x},\hat{p})\partial_{p}$ (45)

and

$\displaystyle\Psi_{q}(p)=\int_{-\infty}^{\infty}dx\,\exp\Big{(}\frac{-ix}{\alpha\sigma(x)}\arctan\frac{p}{\sigma(x)}\Big{)}\Psi_{q}(x).$
(46)

The appropriate inner product, in the momentum space, rendering the operator
$\hat{x}$ Hermitian is defined as

$\displaystyle<f,g>=\int\,\frac{dp}{\theta(\hat{x},\hat{p})}\bar{f}_{q}(p)g_{q}(p)$
(47)

with the condition
$\lim\limits_{x\rightarrow-\infty}\Psi_{q}(x)=\lim\limits_{x\rightarrow\infty}\Psi_{q}(x)=0.$

##  3 Matrix elements

From the natural actions of $q-$deformed position operator $\hat{x}$ and
momentum operator $\hat{p}$ on the basis vectors $|n,q>\in\mathcal{F}:$

$\displaystyle\hat{x}|n,q>=\frac{1}{m_{\alpha}}(\hat{b}+\hat{b}^{\dagger})|n,q>,\quad\hat{p}|n,q>=\frac{i}{m_{\beta}}(\hat{b}^{\dagger}-\hat{b})|n,q>$
(48)

we immediately deduce the matrix elements

$\displaystyle<m,q|\hat{b}^{{\dagger}l}\hat{b}^{r}|n,q>=\sqrt{\frac{\Gamma_{q}(n+1)\Gamma_{q}(n-r+l+1)}{\Gamma_{q}(n-r+1)\Gamma_{q}(n-r+1)}}\delta_{m,n-r+l}$
(49)
$\displaystyle<m,q|\hat{b}^{r}\hat{b}^{{\dagger}l}|n,q>=\sqrt{\frac{\Gamma_{q}(n+l+1)\Gamma_{q}(n+l+1)}{\Gamma_{q}(n+1)\Gamma_{q}(n-r+l+1)}}\delta_{m,n-r+l}$
(50)

where $\Gamma_{q}(.)$ is the $q$-Gamma function. Denoting by $:\,:$ the normal
ordering, then the expectation value of normal ordering product of
$\hat{x}^{l}\hat{p}^{r}$ can be computed by the following relation:

$\displaystyle<m,q|:\hat{x}^{l}\hat{p}^{r}:|n,q>=\frac{i^{r}}{m_{\alpha}^{l}m_{\beta}^{r}}\sum_{s=0}^{l}\sum_{t=0}^{r}C_{l}^{s}C_{r}^{t}<m,q|\hat{b}^{{\dagger}l-s+t}\hat{b}^{s+r-t}|n,q>$
(51)

which can be given explicitly by using relation (49). Then it becomes a matter
of computation to determine the basis operators in terms of $\hat{b}$ and
$\hat{b}^{\dagger}$ as follows:

$\displaystyle|m,q><n,q|=:\frac{\hat{b}^{{\dagger}m}}{\sqrt{[m]_{q}!}}e^{-\hat{b}^{\dagger}\hat{b}}\frac{\hat{b}^{n}}{\sqrt{[n]_{q}!}}:.$
(53)

##  4 $su(2)-$algebra representation

Turning back to the standard expression of the harmonic oscillator Hamiltonian
operator, i.e. $\hat{H}=\hat{a}^{\dagger}\hat{a},$ such that

$\displaystyle\hat{a}=\frac{1}{\sqrt{2}}(\hat{x}+i\hat{p}),\,\,\,\hat{a}^{\dagger}=\frac{1}{\sqrt{2}}(\hat{x}-i\hat{p}),$
(54)

we get explicitly

$\displaystyle\hat{H}=\frac{1}{2}\Big{[}(1+\alpha)\hat{x}^{2}+(1+\beta)\hat{p}^{2}+1\Big{]}$
(55)

giving the simpler form $\hat{H}=\frac{1}{2}$ when $\alpha=-1$ and $\beta=-1.$

From (42) and (45), the Hamiltonian $H$ can be considered as non-local and we
can define

$\displaystyle\hat{H}^{\mbox{loc}}:=\hat{H}(\theta,\partial_{x}\theta,\partial_{x}^{2}\theta\cdots,x,\partial_{x},\partial_{x}^{2},\cdots,\alpha,\beta)$
(56)

with

$\displaystyle\theta,\partial_{x}\theta,\cdots=f(\theta,\partial_{x}\theta,\partial_{x}^{2}\theta\cdots,x,\partial_{x},\partial_{x}^{2},\cdots,\alpha,\beta).$
(57)

adding some nonlinearity to the Hamiltonian operator nonlocality.

Assume the parameters $\alpha$ and $\beta$ satisfy the condition:
$|\alpha|<<1,|\beta|<<1$ and put $\tilde{\alpha}=\alpha$ and
$\tilde{\beta}=-\beta.$ Then $\hat{x},\,\hat{p},\,\theta$ can be viewed as the
elements of $su(2)-$algebra, i.e.

$\displaystyle[\hat{x},\hat{p}]=i\theta,\,\,\,[\hat{p},\theta]=i\alpha\\{\hat{x},\theta\\}=i\tilde{\alpha}\hat{x},\,\,\,[\theta,\hat{x}]=-i\beta\\{\hat{p},\theta\\}=i\tilde{\beta}\hat{p}.$
(58)

Let $\hat{\overrightarrow{J}}:=(\hat{x},\hat{p},\theta)$ be the angular
momentum such that there exist states $|j,m>\in\mathcal{F}$ satisfying the
condition $<j,m|j,m^{\prime}>=\delta_{mm^{\prime}}$. Define the operators
$\hat{J}_{+}$ and $\hat{J}_{-}$ by

$\displaystyle\hat{J}_{+}:=\frac{1}{\beta}\hat{x}+\frac{i}{\alpha}\hat{p},\,\,\,\,\hat{J}_{-}:=\frac{1}{\beta}\hat{x}-\frac{i}{\alpha}\hat{p}.$
(59)

###### Proposition 4.1

There exists an arbitrary number $\nu$ such that

$\displaystyle\hat{J}_{-}|j,m>=C_{-}(m,j)|j,m-\nu>,\,\,\,\,\hat{J}_{+}|j,m>=C_{+}(m,j)|j,m+\nu>,$
(60) $\displaystyle\theta|j,m>=f(m,j)|j,m>$ (61)

where $C_{-}(m,j),$ $C_{+}(m,j)$ and $f(m,j)$ are three constants depending on
$j$ and $m$.

The parameters $j$ and $m$ depend on $\alpha$ and $\beta.$ The unitary
representation of $su(2)-$ algebra, $\\{|j,m>,\,\,j\in\mathbb{N},\,\,-j\leq
m\leq j\\},$ is infinite dimensional. The operators
$\\{\hat{x},\hat{p},\theta\\}$ act on the Fock space
$\mathcal{H}=\\{|j,m>/m\in\mathbb{N}\cup\\{0\\}\\}$ following (60). Note that
$\theta$ and
$\hat{\overrightarrow{J}^{2}}=(1+2\alpha)\hat{x}^{2}+(1+2\beta)\hat{p}^{2}+1$
commute. Therefore, $\hat{\overrightarrow{J}^{2}}$ and $\hat{H}$ commute too.
Besides, the following commutation relations are in order:

$\displaystyle[\theta,\hat{J}_{+}]=\hat{x}+i\hat{p},\,\,\,\,[\theta,\hat{J}_{-},]=-(\hat{x}-i\hat{p}).$
(62)

In the interesting particular case where $\alpha=\beta$, the relations (62)
are reduced to

$\displaystyle[\theta,\hat{J}_{+}]=\alpha\hat{J}_{+},\,\,\,\,[\theta,\hat{J}_{-},]=-\alpha\hat{J}_{-},\,\,\,\,[\hat{J}_{+},\hat{J}_{-}]=2\alpha^{-2}\theta.$
(63)

Taking $f(m,j)=m$ yields the condition

$\displaystyle\theta\hat{J}_{+}|j,m>=(m+\alpha)\hat{J}_{+}|j,m>,\,\,\,\theta\hat{J}_{-}|j,m>=(m-\alpha)\hat{J}_{+}|j,m>.$
(64)

Besides, we have

$\displaystyle\hat{J}_{+}|j,m>=C_{+}|j,m+\alpha>,\,\,\,\hat{J}_{-}|j,m>=C_{-}|j,m-\alpha>$
(65)

where

$\displaystyle C_{+}=\sqrt{(j-m)(j+m+\alpha)},\quad
C_{-}=\sqrt{(j+m)(j-m+\alpha)}.$ (66)

The eigenfunctions of the Hamiltonian $\hat{H}$ in the position and momentum
representations are given, respectively, by

$\displaystyle\Psi_{j,m}(x)=<x|j,m>,\,\,\,\,\Psi_{j,m}(p)=<p|j,m>$ (67)

solution of the equation

$\displaystyle\hat{H}\Psi_{j,m}(x)=\frac{\alpha^{2}}{2}\sqrt{(j+m)(j-m)(j+m+\alpha)(j-m+\alpha)}\Psi_{j,m}(x)$
(68)

easily obtainable by solving the eigenvalue problem for the Casimir operator
$\hat{J}_{+}\hat{J}_{-}$. Furthermore, we get

$\displaystyle\hat{J}^{2}\Psi_{j,m}(x)=2\alpha^{2}\sqrt{(j+m)(j-m)(j+m+2\alpha)(j-m+2\alpha)}\Psi_{j,m}(x).$
(69)

##  5 Concluding remarks

In work, we have introduced a reformulation of the
${\theta}(\hat{x},\hat{p})-$deformation in terms of a $q-$deformation allowing
to easily deduce the energy spectrum of the induced deformed harmonic
oscillator. Then we have proved that the deformed position and momentum
operators admit a one-parameter family of self-adjoint extensions. These
operators have engendered new families of deformed Hermite polynomials
generalizing usual $q-$ Hermite polynomials. We have also computed relevant
matrix elements. Finally, a $su(2)-$algebra representation of the considered
deformation has been investigated and discussed.

### Acknowledgment

This work is partially supported by the ICTP through the OEA-ICMPA-Prj-15. The
ICMPA is in partnership with the Daniel Iagolnitzer Foundation (DIF), France.
MNH expresses his gratefulness to Professor A. Odzijewicz and all his staff
for their hospitality and the good organization of the Workshops in Geometric
Methods in Physics.

## References

  * [1] D. Amati, M. Ciafaloni, G. Veneziano.: (1989), Can spacetime be probed below the string size Phys. lett. B 216 41.
  * [2] Ju. M. Berezanskií, Expansions in Eigenfunctions of Selfadjoint Operators, (Amer. Math. Soc., Providence, Rhode Island, 1968).
  * [3] Burban I. M.: Generalized $q-$deformed oscillators, $q-$Hermite polynomials, generalized coherent states.
  * [4] Doplicher, S. Fredenhagen, K. and E. Roberts, J.: (1995), The Quantum Structure of Spacetime at the Planck Scale and Quantum Fields, Comm. Math. Phys. 172, pp. 187-220.
  * [5] L. J. Garay.: (1995) Models of neutrino masses and mixings,  Int. J. Mod. Phys. A10, 145
  * [6] D. J. Gross, P. F. Mende.: (1988)The Minimal Length in String Theory, Nucl. Phys. B303, 407.
  * [7] Hirshfeld, A.C. and Henselder, P.: (2002), Deformation quantization in the teaching of quantum mechanics, American Journal of Physics, 70 (5) pp. 537–547, May.
  * [8] Kempf, A.: (2000), A Generalized Shannon Sampling Theorem, Fields at the Planck Scale as Bandlimited Signals, Phys. Rev. Lett. 85, pp. 2873 [e-print hep-th/9905114].
  * [9] Kempf, A.: (1998), On the Structure of Space-Time at the Planck Scale , [e-print hep-th/9810215].
  * [10] Kempf, A.: (2011), Generalized uncertainty principles and localization in discrete space, [e-print hep-th/1112.0994].
  * [11] Kempf, A. Mangano, G. and Mann, R.B.: (1995), Hilbert Space Representation of the Minimal Length Uncertainty Relation, J. Phys. D. 52, pp. 1108.
  * [12] Lay Nam Chang, Dlordje Minic, Naotoshi Okamura and Tatsu Takeuchi : Exact solutions of the harmonic oscillator in arbitrary dimensions with minimal length uncertainty relations, [arXiv:hep-th/0111181].
  * [13] Quesne C. and Tkachuk V. M.: Lorentz-covariant deformed algebra with minimal length, [arXiv:hep-th/0612093].
  * [14] Sketesko M. M and Tkachuk V. M.: Perturbative hydrogen-atom spectrum in deformed space with minimal length, [arXiv:hep-th/0603042].


XX XX 8 May/June

Preprint

# A Blockchain Architecture for Industrial Applications

Lodovica Marchesi  Michele Marchesi  Roberto Tonelli  DMI, University of
Cagliari

(2020)

###### Abstract

The Blockchain and the programs running on it, called Smart Contracts, are
more and more applied in all fields requiring trust and strong certifications.
In this work we compare public and permissioned blockchains for industrial
applications. We propose a complete, original solution based on Ethereum to
implement a decentralized application. This solution is characterized by a set
of validator nodes running the blockchain using Proof-of-Authority consensus,
and including an Explorer enabling users to check blockchain state, and the
source code of the Smart Contracts running on it. From time to time, the hash
digest of the last mined block is written into a public blockchain to
guarantee immutability. The right to send transactions is granted by validator
nodes to users by endowing them with the local Ethers mined. Overall, the
proposed approach has the same transparency and immutability of a public
blockchain, without its drawbacks.

††journal: Preprint

Introduction The blockchain technology is a smart mix of known technologies,
first introduced in 2008 with the famous paper by Satoshi Nakamoto, as the
enabler of the digital currency known as Bitcoin [2]. The main requirement of
Bitcoin, as of every currency, was trust. In fact, to put your saving and the
efforts of your work into a currency, you need to trust that the money will be
still expendable for a reasonable number of years, secure against
counterfeiting, theft, confiscation, double-spending and inflation, and easily
transferable. Another requirement, that diversified Bitcoin from any other
currency, was the absence of a central authority managing it.

In Bitcoin, these features were obtained by using a distributed peer-to-peer
network, based on open source software running in every node, each holding a
copy of the transaction database, known as blockchain. The high number of
nodes, and the economic incentives given to miners (who validate transactions
and pack them into blocks), guarantees the survival of the network and its
robustness; the equality and openness of all nodes makes the network
decentralized; the transparency and immutability of the blockchain enables
trust; the consensus mechanism used to add new transactions to the blockchain
(proof of work) guarantee against massive Sybil attacks; the limited number of
Bitcoins mined guarantees against inflation. The success of Bitcoin, whose
market value changed from zero to several thousands of USD in less than ten
years, witnesses the success of the Bitcoin vision.

In this paper, however, we are not interested in cryptocurrencies, but in
other applications of the blockchain. In fact, a few years after the
introduction of Bitcoin in 2009, managers and developers realized that a
blockchain can be also used to run a decentralized computer. The first
successful network able to run Turing-complete programs, called "Smart
Contracts" (SCs) following an idea of Nick Szabo [5], was the Ethereum
blockchain, started in 2015 [6].

Table 1: The features needed by a dApp system. # |  Feature |  Description
---|---|---
1 |  No central authority |  If a central authority can run the application, there is no point to use a blockchain!
2 |  Persistency |  The system repositories and apps, blockchain included, must be kept runnng for a suitable amount of time – typically in the range of years or decades – with negligible risk of being interrupted or terminated before the time.
3 |  Immutability |  A blockchain is an append-only system – once written, the information cannot be changed or deleted. The data and programs running on the blockchain must be verifiably immutable and counterfeit proof.
4 |  Transparency |  The data and the activities performed on the blockchain must be entirely traceable. Anyone, possibly with suitable access rights, should be able to easily explore the blockchain, to verify this.
5 |  Parties identification |  All writing activities performed on the blockchain must come from certified identities.
6 |  Privacy |  The permission to access the blockchain, in particular to change its state, must be granted only to known users, possibly at various access levels.
7 |  Low, predictable cost |  The blockchain system should be open source, easily deployed, and requiring limited hardware and network bandwith resources, compatibly with the size of the dApp, and the number of transactions per second. The cost should not be volatile.
8 |  Efficiency |  The system should be able to bear the required throughput, with proper response times, even in the case of many users and many transactions per unit of time.
9 |  Scalability |  The system should be able to scale, if needed.

## Uses of dApps and kinds of blockchains

The software programs using a blockchain are called "decentralized
applications", or "dApps", and are one of main new trends of software
development. They include the SCs actually running on a blockchain, but also
the software managing data outside the blockchain and the user interface to
interact with it.

Initially, the primary use of SCs – typically running on Ethereum blockchain –
was to manage second-level digital currencies, called "tokens", mainly used to
finance the Initial Coin Offers – crowfunding operations gathering money in
the form of cryptocurrency to finance startups [1].

Besides tokens, dApps are being used for many applications, in the fields of
data notarization, finance and insurance contracts, supply chain management,
document and workflow management, gambling, gaming, voting, and many others
[7]. dApps and SCs can be used for automated enforcement of contractual
obligations, without having to trust a central authority, and without space
and time constraints.

Table 2: Comparison of public and permissioned blockchains. Feature |  Public blockchain |  Permissioned blockchain
---|---|---
No central authority |  Totally achieved |  Achieved, but with much fewer nodes.
Persistency |  Very high |  High, depending on the willingness and convenience of the validators.
Immutability |  Very high |  High, can be very high.
Transparency |  Very high |  Depending on the system; can be very high.
Parties identification |  Very strong, based on private key ownership, if the owner wishes to be identified. |  Strong if based on username and password, very strong if based on private key ownership.
Privacy |  Non-existent. |  Can be enforced.
Low, predictable cost |  Only software development and execution costs. The latter costs can be very volatile and unpredictable. |  Infrastructural costs are typically low. Execution costs are low and predictable.
Efficiency |  The number of transactions per second is quite low. |  The number of transactions per second can be high.
Scalability |  Poor scalability if the number of dApps and users increases. |  High, by deploying further blockchains on the same node, and/or by splitting the nodes.

The features a dApp system must exhibit are reported in Table 1. The main one
is the fact that a central authority running the system is missed. The reasons
for this may be various. For instance, no single organization might be willing
to run the system for cost, or legal liability reasons; or the organizations
involved might not wish to let just one of them run the system; or having
many, independent nodes could be a guarantee of persistence and immutability
of the system.

Features 2-6 are basically aimed to gain user trust without having to trust
all blockchain nodes. Features 7-9 are desirable for all software systems, but
are especially difficult to obtain in public blockchains.

Developing a dApp system, the first issue to address is whether to use a
public or a permissioned blockchain. Public blockchains are open to everyone,
and have no central authority. The most used blockchains for implementing
dApps is Ethereum, but others are available, such as EOS, NEO, Qtum and
others.

Permissioned blockchains, often called also "distributed ledgers". are managed
by a consortium of organizations, which run the validator nodes and perform
the consensus mechanism. Further validator nodes can be added only by
obtaining the permission of existing ones. Validators may allow including
nodes holding a copy of the blockchain, but unable to validate transactions.
The right to send transactions, and thus to change the state of the
blockchain, can be given to users who are not validators. Also, often everyone
can access the blockchain to verify its correctness. In other cases, also the
read-only access is granted only to users with the permission to do so.

To run a permissioned blockchain, there are many software systems available.
Most public blockchain software is open source, and suitable also to be used
to manage a permissioned one. A prominent permissioned blockchain, aimed
mainly to banking applications, is Ripple, developed by a private company and
presently run by about 150 invited validators. There are also projects aimed
to build permissioned blockchain software. The most popular among these is
Hyperledger, an open source collaborative effort hosted by the Linux
Foundation, aimed to build cross-industry blockchain technologies.

Table 2 shows a comparison of public and permissioned blockchains with regard
to the properties shown in Table 1.

Public blockchains look the most stable, and easiest to start with, but lack
performances and scalability. Their cost is not predictable, due to the high
volatility in cryptocurrencies values and in transaction validation fees.
Moreover, they do not support privacy of data, and are thus non-compliant with
respect to the strict guidelines of modern privacy laws, such as European
GDPR.

For these reasons, public blockchains are mainly used for applications
managing digital money, such as the above cited tokens, and for the
notarization of information. In our proposal, we will focus on non-monetary,
industrial applications, and thus on a permissioned blockchain. However, the
proposed solution includes the use of a public blockchain.

Figure 1: The proposed architecture of a dApp application.

## The proposed dApp architecture

We define as dApp a software system that uses distributed ledger technology
(DLT), typically a blockchain, as a central hub to store and exchange
information, through Smart Contracts (SCs).

A dApp is composed of SCs running on a blockchain, and of applications able to
create and send transactions to SCs. This application typically provides a
human interaction interface, running on a PC or on a mobile device. Additional
information could be stored on a server, and a business logic could be
executed on this.

In our proposal, we will use Ethereum as a reference blokchain, being
presently the most used system to develop SCs. As of December 2019, 2717 dApps
were running on Ethereum public blockchain, out of a total of 3236 surveyed
dApps [4]. Another feature of Ethereum is that, to be able to send
transactions, users must spend GAS, that is a fraction of Ethers (Ethereum
currency) proportional to the resources used.

The proposed dApp architecture is shown in Fig. 1. The main component are the
P2P validator nodes hosting the blockchain, shown on the left. These should be
managed by independent organizations, to avoid that a single organization
might try to falsify the blockchain, or simply decide to stop supporting the
dApp. We suggest a minimum number of seven independent nodes.

The software running in the nodes is Ethereum, with Proof-of-Authority (PoA)
consensus for block validation [3]. PoA is quicker and more suitable to a
permissioned blockchain than PoW. The validators also create Ethers expendable
in the permissioned blockchain, which we call "Local Ethers" (LOCETH).

A node, beside the blockchain itself, holds its enabling software, which
includes the Ethereum Virtual Machine able to run the SCs. On top of it there
is the SC bytecode, endowed with its permanent data (Storage), which are read
from the blockchain for their execution. All the nodes execute the SCs, and
the execution result must be the same for all nodes. Hence the impossibility
for the SCs to access the external world. They can access only their data and
other SCs stored in the blockchain, which are the same in all nodes.

The other dApp component is a software system running on mobile devices and/or
on servers, possibly on the Cloud, exchanging information with users and
external systems and devices, which we call "App System". Its User Interface
(UI) typically runs on a Web browser. The server component stores data and
documents that cannot be stored in the blockchain, and performs business
computations.

The proposed architecture has three kinds of actors:

  * •

Validators, that is the nodes running the system and shown in Fig. 1. They
validate transactions and group them in blocks. They also mint LOCETH.

  * •

Operators, who are enabled to send transactions which change the blockchain
state.

  * •

External users, who can access the system nodes in read-only mode.

Other key ideas of the proposed architecture are the following:

  * •

One or more blockchain nodes provide an explorer, a software that allows all
users to access the blockchain transactions and related addresses, and to
inspect the source code of SCs. In this way, the transparency of the
permissioned blockchain equals that of a public one.

  * •

Every 24 hours, or so, the hash digest of the last block validated in the
permissioned blockchain is written into a public blockchain, thus making the
former as immutable as the latter.

  * •

All users can send "view" queries, which return information from the SCs,
without changing the blockchain, and which cost no GAS.

  * •

The access control is obtained by validators endowing operators with LOCETH,
that is the GAS enabling sending transactions. Further access control can be
performed inside SCs, based on the specific address sending a transaction.

  * •

The operators generate their own private keys and corresponding addresses, and
declare them to the system. In this way, they have strong digital
identification. One can trust that transactions coming from an address
actually are sent by the associated identity.

  * •

If the dApp must hold large amounts of information, such as documents and
images, these documents are stored off-chain, by App System. The hash digest
of the document and a link to retrieve it is stored in the blockchain,
guaranteeing the date of the document, and its integrity.

Together with our spinoff FlossLab ltd we already implemented a prototype of
the system, aimed to track the provenance and events of a food supply chain.
In this system, external users are the buyers of a product. Through a QR code
in the label, and an app, they can access the dApp and verify all the
transformations and relevant events related to the product, and registered by
identified actors of the supply chain. The actors are the firms which produced
or transformed the product, and the independent certifiers of its quality. An
advanced user can also independently access the permissioned blockchain, and
verify the data.

## Conclusion and Future Work

The key reason to use a blockchain is trust. The described approach guarantees
the same level of trust and transparency of the public blockchain it is
anchored to, allowing much better performances and scalability, and at low,
predictable cost.

Presently, we are working with a set of Sardinian institutions to start a
permissioned blockchain as described above, with the aim to certify the
provenance and quality of local products.

## References

  * [1] Gianni Fenu, Lodovica Marchesi, Michele Marchesi, and Roberto Tonelli.  The ico phenomenon and its relationships with ethereum smart contract environment.  In Blockchain Oriented Software Engineering (IWBOSE), 2018 International Workshop on, pages 26–32. IEEE, 2018.
  * [2] S. Nakamoto.  Bitcoin: A peer-to-peer electronic cash system, 2008.  url="https://bitcoin.org/bitcoin.pdf", last accessed: April 30, 2020.
  * [3] Proof of Authority.  Github website, 2020.  url="https://github.com/paritytech/parity/wiki/Proof-of-Authority-Chains", last accessed: April 30, 2020.
  * [4] State of the DApps.  Website, 2019.  url="https://www.stateofthedapps.com/stats", last accessed: April 30, 2020\.
  * [5] N. Szabo.  Smart contracts: Formalizing and securing relationships on public networks.  First Monday, 2, 1997.  url="https://ojphi.org/ojs/index.php/fm/article/view/548".
  * [6] G. Wood.  Ethereum: A secure decentralised generalised transaction ledger, 2014\.  url="https://ethereum.github.io/yellowpaper/paper.pdf", last accessed (updated version): April 30, 2020.
  * [7] X. Xu, I. Weber, and M. Staples.  Architecture for Blockchain Applications.  Springer, 2019.