# Grasping Trajectory Optimization with Point Clouds

Yu Xiang, Sai Haneesh Allu, Rohith Peddi, Tyler Summers, Vibhav Gogate Yu
Xiang, Sai Haneesh Allu, Rohith Peddi and Vibhav Gogate are with the
Department of Computer Science, and Tyler Summers is with the Department of
Mechanical Engineering, University of Texas at Dallas, Richardson, TX 75080,
USA {yu.xiang, saiHaneesh.allu, rohith.peddi, tyler.summers,
<EMAIL_ADDRESS>
###### Abstract

We introduce a new trajectory optimization method for robotic grasping based
on a point-cloud representation of robots and task spaces. In our method,
robots are represented by 3D points on their link surfaces. The task space of
a robot is represented by a point cloud that can be obtained from depth
sensors. Using the point-cloud representation, goal reaching in grasping can
be formulated as point matching, while collision avoidance can be efficiently
achieved by querying the signed distance values of the robot points in the
signed distance field of the scene points. Consequently, a constrained non-
linear optimization problem is formulated to solve the joint motion and grasp
planning problem. The advantage of our method is that the point-cloud
representation is general to be used with any robot in any environment. We
demonstrate the effectiveness of our method by conducting experiments on a
tabletop scene and a shelf scene for grasping with a Fetch mobile manipulator
and a Franka Panda arm. 111Code and videos for the project are available at
https://irvlutd.github.io/GraspTrajOpt

##  I Introduction

In robot manipulation, planning a robot trajectory to grasp an object is a
fundamental research problem. The problem is challenging since it requires
motion planning to avoid obstacles in the task space and grasp planning to
decide how to grasp a target object. Traditionally, the motion planning
problem and the grasp planning problem are tackled separately. Motion planning
approaches focus on finding a collision-free path to reach a given end-
effector goal. For example, sampling-based motion planning methods such as
Rapidly exploring Random Trees (RRTs) [1, 2, 3] and Fast Marching Tree (FMT)
[4] find robot trajectories by incrementally building configuration space
filling trees through directed sampling. Optimization-based motion planning
methods [5, 6, 7, 8] solve optimization problems to find robot trajectories
that minimize some loss functions and obey certain constraints, such as joint
limits.

Since these motion planning algorithms need to have a given goal, they cannot
be applied directly to robot grasping unless a grasping goal is given. On the
other hand, grasp planning methods such as GraspIt! [9], 6D GraspNet [10] and
SE(3)-DiffusionFields [11] aim to synthesize grasps of robot grippers given 3D
models or 3D point clouds of objects. These methods focus on planning the
poses of robot grippers to grasp various objects. However, they do not
consider the motion of the robotic arm to reach the planned grasps.

Combining grasp planning and motion planning can address the robot grasping
problem. A straightforward approach is first to utilize a grasp planning
method to generate grasps of a target object and employ a motion planning
method to plan a robot trajectory to reach one of the grasps. A naive way is
to loop over all the planned grasps until the motion planner finds a
collision-free path to reach one of the grasps. This naive approach is
complete, that is, as long as there is one plausible grasp from the grasp
planner, the method can find a path to reach it. However, it is very slow,
especially when the number of planned grasps is large. Therefore, a number of
approaches are proposed to tackle the problem of joint motion and grasp
planning.

Figure 1: We represent robots and the task space with point clouds, and solve
a trajectory optimization problem for joint motion and grasp planning.

Similarly to motion planning methods, these joint motion and grasp planning
methods can be categorized into sampling-based and optimization-based ones.
Sampling-based methods [12, 13, 14] bias a motion planner to sample nodes that
are closer to better grasps, and the grasps are synthesized online. The main
limitation of these approaches is that the online synthesized grasps may not
be accurate enough for precise grasping, especially for objects with
complicated shapes. To overcome this limitation, several goal-set-based
trajectory optimization methods are proposed [15, 16]. These methods first
utilize an offline grasp planner to generate grasps of objects, where well-
designed grasp planners can be used, such as grasps synthesized from physics
simulation [9, 17]. These generated grasps are treated as goals in a goal set.
Then the joint motion and grasp planner optimizes a collision-free trajectory
that can reach one of the goals in the goal set. The goal set introduces a
constraint on the last configuration of the robot trajectory. Using high-
quality grasps as goals, these approaches can handle various objects in
grasping.

In this work, motivated by the goal-set-based trajectory optimization
framework for joint motion and grasp planning, we introduce a new trajectory
optimization method for robotic grasping. Compared to previous methods [15,
16], our method has the following advantages. First, we introduce a point-
cloud representation of robots and task spaces for goal reaching and obstacle
avoidance. Point clouds of robots are generated using the 3D meshes of the
robot links, whereas point clouds of the task space can be obtained from depth
sensors such as RGB-D cameras. Figure 1 shows the point cloud representation
with the planned trajectories of a Fetch robot and a Franka Panda arm. This
representation is general and can be used with any robot and any task space.
Second, we formulate a constrained trajectory optimization problem using the
point-cloud representation for joint motion and grasp planning. Given a set of
grasping goals, solving the optimization problem generates a trajectory to
reach one of the goals that minimizes the objective function subject to
certain constraints, such as joint limits. Instead of converting the
constrained optimization problem into an unconstrained one and solving with
first-order gradient descent-based techniques as in [15, 16], we utilize the
Interior Point OPTimizer (Ipopt) [18] to solve the large-scale nonlinear
optimization problem for trajectory planning, which can find better solutions
compared to first-order solvers. Finally, we empirically verify our method on
two robot grasping environments in the PyBullet simulator [19], i.e., a
tabletop scene and a shelf scene, and demonstrate a significant improvement
over the OMG-Planner [16] in terms of metrics on grasping success and
collision avoidance. In addition, we conducted real-world grasping experiments
according to the SceneReplica benchmark [20]. Our method improves over a
sampling-based baseline in real-world experiments.

##  II Related Work

###  II-A Manipulation Trajectory Optimization

Trajectory optimization techniques have been successfully applied to robot
manipulation. Early work such as CHOMP [5] and related methods [15, 21]
optimize a cost functional using covariant gradient descent. STOMP [22] uses
stochastic sampling of noisy trajectories to optimize non-differentiable
costs. TrajOpt [6] solves a sequential quadratic program, while GPMP2 [7]
formulates the problem as inference on a factor graph and finds the maximum a
posteriori trajectory by solving a nonlinear least-squares problem. More
recently, various trajectory optimization methods have been proposed to solve
specific manipulation problems. For example, TORM [23] is introduced to follow
given end-effector paths. [24] solves a trajectory optimization problem for
the manipulation of deformable objects. [25] solves a whole-body trajectory
optimization for mobile manipulation. The advantage of trajectory optimization
lies in its flexibility in introducing different cost functions and
constraints for various problems. In this work, we solve a trajectory
optimization problem for joint motion and grasp planning in robotic grasping.

###  II-B Joint Motion and Grasp Planning

Traditionally, arm motion planning and grasp planning are tackled separately,
which can result in sub-optimal grasping trajectories. Since jointly
optimizing trajectories and grasps is challenging, several approaches are
proposed to solve a goal-constrained trajectory optimization problem for joint
motion and grasp planning [15, 16, 26], where grasps from a grasp planner such
as GraspIt! [9] are used as goals. For example, [15] projects the robot
configuration of the last time step in the goal set during trajectory
optimization. OMG-Planner [16] iterates between goal selection and trajectory
optimization based on CHOMP. Recently, SE(3)-DiffusionFields [11] learns a
cost function for grasp planning based on a diffusion model, and then solves a
joint optimization problem for grasp and motion planning. Unlike these
methods, we introduce a cost function for goal reaching using our point-cloud
representation and solve a constrained optimization problem for joint motion
and grasp planning.

##  III Method

###  III-A A Point-Cloud Representation for Robots and Task Spaces

In robot motion planning, the goal is to generate a robot trajectory to reach
a goal location while avoiding obstacles in the task space. The geometric
representation of robots and the task space is a critical component of robot
motion generation. A natural choice is to use 3D meshes of robots and objects
in the task space. However, the limitation of using 3D meshes is that we
cannot always obtain 3D meshes of objects and collision checking between
meshes is expensive. Another choice is to approximate the robot links and
obstacles in the task space with 3D shape primitives such as spheres, boxes,
or cylinders [5, 27]. Using 3D shape primitives simplifies collision checking,
but results in inaccurate collision checking, where motion plans can be
conservative. Furthermore, these geometric representations are mainly used for
collision checking. They cannot be easily utilized in robot trajectory
generation or control. In this work, we utilize a simple geometric
representation of objects and the task space, i.e., point clouds, for robot
motion planning based on trajectory optimization.

Figure 2: Surface points (red points in the figure) are sampled as a
representation for robots. Figure 3: (a) A tabletop scene for grasping with a
Fetch robot. (b) A 3D point cloud of the scene computed using a depth image
from the camera on the robot. (c) Reaching a grasping goal can be formulated
as matching 3D points on the robot gripper. (d) Visualization of the signed
distance field of the task space. Cyan points are with negative distances, and
yellow points are with positive distances.

Given a robot description using the Unified Robotics Description Format
(URDF), each robot link has an associated 3D mesh model. To obtain a point-
cloud representation of the robot, we simply sample 3D points from the
vertices of the 3D meshes of the links. Figure 2 shows two examples of a Fetch
mobile manipulator and a Franka Panda arm with their 3D points sampled,
respectively. The number of points for each link is a parameter to set. Using
more points requires more computation in goal reaching and obstacle avoidance,
but it can achieve more accurate collision checking. We simply sample 100
points for each link in our experiments.

For objects in the robot task space, we cannot obtain 3D models of them if we
want the robot to work in arbitrary environments. Therefore, we rely on depth
sensing to obtain a point-cloud representation of the task space. By equipping
a RGB-D camera with a robot, the robot can capture a depth image of the scene.
Depth pixels can be back-projected to the camera frame using the intrinsic
parameters of the camera. Then we can obtain a point cloud of the scene. Given
the camera extrinsic parameters, i.e., 3D rotation and 3D translation of the
camera in the robot base frame, the point cloud can be transformed into the
robot base frame. Figure 3(a) shows a tabletop scene and a Fetch robot in the
PyBullet simulator, and Figure 3(b) illustrates the computed point cloud using
a depth image captured by the robot camera. Since RGB-D cameras are commonly
used in robotic applications, using 3D scene points makes our approach
generalizable to various scenarios. Next, we describe how to use the point-
cloud representation in our grasping trajectory optimization method.

###  III-B Point Cloud-based Cost Function for Goal Reaching

In grasping trajectory optimization, we need to generate a trajectory for a
robot from its current joint configuration to a goal configuration for
grasping a target object. The task-space goal is defined as an end-effector
configuration to grasp the target object. For two-finger grippers, a goal can
be simplified to be a homogeneous transformation
$\mathbf{T}_{g}=(\mathbf{R}_{g},\mathbf{t}_{g})\in\mathbb{SE}(3)$, where
$\mathbf{R}_{g}$ and $\mathbf{t}_{g}$ are the 3D rotation and the 3D
translation of the gripper link with respect to the robot base frame,
respectively.

In our method, we optimize for a trajectory that is discretized into $T$ time
steps. The trajectory is parameterized by $T$ joint positions
$\mathcal{Q}=(\mathbf{q}_{1},\ldots,\mathbf{q}_{T})$, where
$\mathbf{q}_{i},\in\mathbb{R}^{n}$ for $i=1,\ldots,T$, and $n$ is the degree
of freedom of the robot. The last configuration of the trajectory
$\mathbf{q}_{T}$ must reach the goal $\mathbf{T}_{g}$ in the task space. We
can use forward kinematics to compute the end-effector pose of the robot at
time step $T$: $\mathbf{T}_{T}(\mathbf{q}_{T})\in\mathbb{SE}(3)$. We wish to
define a cost function $c_{\text{goal}}(\mathbf{T}_{T},\mathbf{T}_{g})$ to
measure the distance between the gripper pose of the robot at the time step
$T$ and the grasping goal. Consequently, minimizing this cost function can
find a robot configuration to reach the goal.

Usually, the cost function is defined based on the distance between the two 3D
rotations $(\mathbf{R}_{T},\mathbf{R}_{g})$ and the distance between the two
3D translations $(\mathbf{t}_{T},\mathbf{t}_{g})$. However, a weight must be
adjusted to balance the two distances. Motivated by work on 6D object pose
estimation [28], we utilize the point matching loss function as our cost
function for goal reaching. Let $\mathcal{E}=\\{\mathbf{x}_{i}\\}_{i=1}^{m}$
be a set of $m$ 3D points on the end-effector of the robot (see Figure 3(c)).
Our cost function for goal reaching is defined as

$c_{\text{goal}}(\mathbf{T}_{T},\mathbf{T}_{g})=\sum_{i=1}^{m}\|(\mathbf{R}_{T}\mathbf{x}_{i}+\mathbf{t}_{T})-(\mathbf{R}_{g}\mathbf{x}_{i}+\mathbf{t}_{g})\|^{2},$
(1)

which minimizes the distance between two sets of point clouds undergone two
homogeneous transformations. The advantage of using this cost function is that
it eliminates the need to use a hyperparameter to balance rotation and
translation. This cost function can also be generalized to grippers with high
degrees of freedom, such as multi-finger grippers. Note that $\mathbf{T}_{T}$
is a function of $\mathbf{q}_{T}$ in the loss function according to forward
kinematics.

###  III-C Point Cloud-based Cost Function for Collision Avoidance

In addition to reach the grasping goal, another requirement in robotic
grasping is to avoid obstacles in the task space. We hope that the robot will
not hit any object before grasping the target. For the example in Figure 3,
the robot should avoid hitting the table and objects on the table during
grasping. Instead of using 3D meshes or 3D shape primitives to represent
obstacles, our method only has access to a point cloud of the scene.
Therefore, we propose to compute a Signed Distance Field (SDF) of the robot
task space using the point cloud for collision avoidance.

First, the extent of the task space is determined by the extent of the point
cloud in the task space, where we add some margin to the point cloud space.
Second, the SDF is constructed by densely sampling a 3D grid within the extent
of the task space. The resolution of the grid is a parameter that can be tuned
as a trade-off between computational efficiency and accuracy of collision
checking. Third, we compute the signed distance value for each vertex of the
3D grid, which is approximated by the distance between the vertex and the
closest point in the point cloud of the scene. The sign of the distance is
determined by checking if the vertex is behind the point cloud or not.
Specifically, we project the vertex to the depth image using the camera
parameters and compare the depth values of the vertex and the projected pixel
to obtain the distance sign. Figure 3(d) illustrates the SDF of the task
space, where the cyan vertices have negative distances. Finally, using the
computed SDF, we can check the collision between the robot and the scene by
checking the signed distance values of the 3D points on the surface of the
robot (Figure 2) in the task space.

In addition, we can define a cost function for collision avoidance using the
SDF. For each joint configuration in the robot trajectory
$\mathbf{q}_{t}\in\mathbb{R}^{n},t=1,\ldots,T$, let
$\mathbf{x}(\mathbf{q}_{t})\in\mathbb{R}^{3}$ be a surface point on the robot
transformed to the task space according to the joint configuration
$\mathbf{q}_{t}$ using forward kinematics. Then we can define a cost function
for the 3D point $\mathbf{x}(\mathbf{q}_{t})$ as in CHOMP [5]:

$c_{\text{collision}}(\mathbf{x})=\begin{cases}-d(\mathbf{x})+\frac{1}{2}\varepsilon&\text{if
}d(\mathbf{x})<0\\\
\frac{1}{2\varepsilon}(d(\mathbf{x})-\varepsilon)^{2}&\text{if }0\leq
d(\mathbf{x})\leq\varepsilon\\\ 0&\text{otherwise}\end{cases},$ (2)

where $\varepsilon$ is a margin parameter and $d(\mathbf{x})$ is the signed
distance of the 3D point. When the signed distance $d(\mathbf{x})$ is greater
than $\varepsilon$, there is no cost in collision. Note that in our
implementation, the SDF is pre-computed for vertices of the 3D grid to speed
up computation. Therefore, we simply find the closest vertex to the 3D point
$\mathbf{x}$ and query the signed distance value of the closest vertex as
$d(\mathbf{x})$.

###  III-D Constrained Trajectory Optimization for Joint Motion and Grasp
Planning

With the designed cost functions for goal reaching and collision avoidance, we
describe our trajectory optimization framework for joint motion and grasp
planning. The task of a robot is to grasp a target object in a cluttered
scene. We assume that there exists a grasp planner that can be used to
synthesize grasps of the target. For example, in model-based grasping,
GraspIt! [9] can be used to synthesize grasps given the 3D model of the target
object. In model-free grasping, learning-based approaches such as 6DGraspNet
[10] or Contact-GraspNet [29] can be used to synthesize grasps of the target
object given the segmented point cloud of the target. We denote the set of
synthesized grasps as a goal set $\mathcal{G}=\\{\mathbf{T}_{i}\\}_{i=1}^{K}$,
where $\mathbf{T}_{i}\in\mathbb{SE}(3)$ is a homogeneous transformation of the
robot gripper and $K$ is the number of planned grasps. Our goal is to find a
collision-free trajectory for the robot to reach one of the grasps.

We optimize for a trajectory that is discretized into $T$ time steps. The
trajectory is parameterized by $T$ joint positions
$\mathcal{Q}=(\mathbf{q}_{1},\ldots,\mathbf{q}_{T})$ and $T$ joint velocities
$\dot{\mathcal{Q}}=(\dot{\mathbf{q}}_{1},\ldots,\dot{\mathbf{q}}_{T})$, where
$\mathbf{q}_{i},\dot{\mathbf{q}}_{i}\in\mathbb{R}^{n}$ for $i=1,\ldots,T$.
Therefore, we optimize both the joint positions and the joint velocities in
our method. Intuitively, we want to have the last joint position
$\mathbf{q}_{T}$ reach one of the grasps in the goal set $\mathcal{G}$.
Meanwhile, the trajectory should be collision-free and subject to constraints
of the robot dynamics and joint limits. Formally, we solve the following
constrained optimization problem to find the trajectory:

$\displaystyle\arg\min_{\mathcal{Q},\dot{\mathcal{Q}}}$
$\displaystyle\Big{(}\min_{i=1}^{K}\big{(}c_{\text{goal}}(\mathbf{T}(\mathbf{q}_{T}),\mathbf{T}_{i})+c_{\text{standoff}}(\mathbf{T}(\mathbf{q}_{T-\delta}),\mathbf{T}_{i}\mathbf{T}_{\Delta})\big{)}$
$\displaystyle+\lambda_{1}\sum_{t=1}^{T}c_{\text{collision}}(\mathbf{q}_{t})+\lambda_{2}\sum_{t=1}^{T}\|\dot{\mathbf{q}_{t}}\|^{2}\Big{)}$
(3) s.t., $\displaystyle\mathbf{q}_{1}=\mathbf{q}_{0}$ (4)
$\displaystyle\dot{\mathbf{q}}_{1}=\mathbf{0},\dot{\mathbf{q}}_{T}=\mathbf{0}$
(5)
$\displaystyle\mathbf{q}_{t+1}=\mathbf{q}_{t}+\dot{\mathbf{q}}_{t}dt,t=1,\ldots,T-1$
(6)
$\displaystyle\mathbf{q}_{l}\leq\mathbf{q}_{t}\leq\mathbf{q}_{u},t=1,\ldots,T$
(7)
$\displaystyle\dot{\mathbf{q}}_{l}\leq\dot{\mathbf{q}}_{t}\leq\dot{\mathbf{q}}_{u},t=1,\ldots,T,$
(8)

where we minimize an objective function of $\mathcal{Q}$ and
$\dot{\mathcal{Q}}$ subject to a set of constraints. Note that the objective
function computes the minimum cost among all the grasping goals in the goal
set $\mathcal{G}$. Consequently, solving the optimization problem will select
the best goal from the goal set.

Figure 4: Illustration of the grasping pose and the standoff pose for
grasping. Figure 5: Examples of (a) tabletop scenes and (b) shelf scenes for
grasping in PyBullet.

First, the term $c_{\text{goal}}(\mathbf{T}(\mathbf{q}_{T}),\mathbf{T}_{i})$
is the goal reaching cost described in Eq. (1) for the $i$th goal
$\mathbf{T}_{i}$ in the goal set, where forward kinematics is used to compute
the gripper pose given the robot configuration at the last time step
$\mathbf{q}_{T}$. Second, in addition to reaching the goal in the last step,
we introduce a cost term
$c_{\text{standoff}}(\mathbf{T}(\mathbf{q}_{T-\delta}),\mathbf{T}_{i}\mathbf{T}_{\Delta})$
to ensure that the robot reaches a standoff pose for grasping before the goal.
The standoff pose $\mathbf{T}_{i}\mathbf{T}_{\Delta}$ is computed by a
displacement $\mathbf{T}_{\Delta}\in\mathbb{SE}(3)$ of the grasping pose
$\mathbf{T}_{i}$ along the forward axis of the gripper as illustrated in
Figure 4. The main reason of introducing the standoff pose is because
optimizing the trajectory directly to reach the grasping pose may result in a
collision between the robot and the target object. In these cases, the robot
will knock down the target object and cannot grasp it. In our objective
function, we require that the robot gripper pose
$\mathbf{T}(\mathbf{q}_{T-\delta})$ at time step $T-\delta$ to reach the
standoff pose, where $\delta$ is a parameter to set. Finally, the objective
function contains a cost term for collision avoidance and a cost term to
penalize large velocities, where $\lambda_{1}$ and $\lambda_{2}$ are two
weights to balance the costs. The collision cost for time step $t$ is defined
as

$c_{\text{collision}}(\mathbf{q}_{t})=\sum_{i=1}^{M}c_{\text{collision}}(\mathbf{x}_{i}(\mathbf{q}_{t})),$
(9)

where $\mathbf{x}_{i}(\mathbf{q}_{t})\in\mathbb{R}^{3}$ is a 3D point on the
robot at the robot configuration $\mathbf{q}_{t}$ and $M$ is the total number
of points on the robot. The collision cost is computed according to Eq. (2)
using our SDF representation.

Next, we describe the constraints in the optimization problem. 1)
$\mathbf{q}_{1}=\mathbf{q}_{0}$, where $\mathbf{q}_{0}$ denotes the current
configuration of the robot. This constraint ensures that the trajectory starts
from the current configuration of the robot. 2)
$\dot{\mathbf{q}}_{1}=\mathbf{0},\dot{\mathbf{q}}_{T}=\mathbf{0}$ ensure that
the starting velocity and the ending velocity of the robot are zeros. 3)
$\mathbf{q}_{t+1}=\mathbf{q}_{t}+\dot{\mathbf{q}}_{t}dt$ ensures that the
robot state follows the kinematics of the robot, where $dt$ is the time
interval between two time steps. 4) The last two constraints in Eqs. (7) and
(8) ensure that the joint positions and the joint velocities are within the
lower bounds $(\mathbf{q}_{l},\dot{\mathbf{q}}_{l})$ and upper bounds
$(\mathbf{q}_{u},\dot{\mathbf{q}}_{u})$.

###  III-E Initialization for Grasping Trajectory Optimization

The optimization problem in Eq. (3) is a large-scale constrained nonlinear
programming problem. For example, a Franka panda arm has $n=7$ DOFs. If we set
the number of time steps of the trajectory $T=50$, the optimization problem
has $7\times 2\times 50=700$ variables. We utilize the Interior Point
OPTimizer (Ipopt) [18] interfaced with the CasADi framework [30] to solve it.
Ipopt can only find local solutions that are sensitive to the initialization
of the variables. To obtain a good local solution and speed up the
optimization, we use the following strategy to initiate the optimization. 1)
Given a set of grasping poses $\mathcal{G}=\\{\mathbf{T}_{i}\\}_{i=1}^{K}$ of
a target, we first filter out grasps that are in-collision with other objects
in the scene. This collision checking can be achieved by checking the signed
distance values of the 3D points on the robot gripper of a given pose as
described in Section III-C. 2) For the remaining grasps, we check if an
inverse kinematics (IK) solution exists. We solve a simplified optimization
problem to find an IK solution of a grasping goal $\mathbf{T}_{\text{g}}$:

$\displaystyle\arg\min_{\mathbf{q}_{T}}\text{ }$ $\displaystyle
c_{\text{goal}}(\mathbf{T}(\mathbf{q}_{T}),\mathbf{T}_{\text{g}})$ (10) s.t.,
$\displaystyle\mathbf{q}_{l}\leq\mathbf{q}_{T}\leq\mathbf{q}_{u},$ (11)

where we use $\mathbf{q}_{T}$ to denote the variable in IK, and the objective
function is the point matching cost function defined in Eq. (1). After finding
a local solution $\mathbf{q}_{T}^{*}$, we compute the pose error between
$\mathbf{T}(\mathbf{q}_{T}^{*})$ and the goal $\mathbf{T}_{g}$ using a
rotation error and a translation error. If both errors are smaller than some
pre-defined thresholds, we claim that an IK solution is found. Otherwise,
there is no IK solution for $\mathbf{T}_{g}$. In this way, we can filter out
grasps without IK solutions. 3) For each remaining grasp with an IK solution,
we interpolate a trajectory of the robot from the current configuration of the
robot to the IK configuration. We then compute the collision cost of the
trajectory $\sum_{t=1}^{T}c_{\text{collision}}(\mathbf{q}_{t})$ to rank these
trajectories. 4) Finally, we initialize the optimization with the trajectory
that has the minimum collision cost. In the case of tie-breaking, e.g.,
multiple non-collision trajectories, we use the trajectory whose last
configuration is closer to the current configuration of the robot. We
empirically found that the above initialization process can speed up the
convergence of the optimization to find a good local solution.

##  IV Experiments

We conduct experiments on 6DoF robotic grasping to evaluate our method in both
simulation and in the real world. Two types of scenes are used for evaluation:
a tabletop scene and a shelf scene as illustrated in Figure 5 in the Pybullet
simulator [19]. In these scenes, 16 YCB objects [31] are used for grasping.
The objects in the tabletop scenes are arranged according to the SceneReplica
benchmark [20], and we sample object locations for the shelf scenes with 6
objects in each scene. Two robots, i.e., a Fetch mobile manipulator and a
Franka Panda arm, are used for evaluation. The main evaluation metric is the
success rate of grasping. If an object is successfully lifted by the robot, we
count it as a success. In addition, we evaluate collisions during grasping.

###  IV-A Implementation Details

First, grasps of the 16 YCB objects are generated using GraspIt! [9], with 100
grasps for each object. Therefore, the size of the goal set is 100. Second,
the trajectory optimization is implemented based on the OpTaS library [32],
which provides an interface to Ipopt solver using the CasADi framework [30].
Third, the hyper-parameters in the method are set as follows. For each robot
link, we sample 100 surface points. The margin $\varepsilon=0.02$ in computing
the collision cost (Eq. (2)). The grid resolution of the signed distance field
is 5cm. In the optimization problem Eq. (3), $\lambda_{1}=10$,
$\lambda_{2}=0.01$ and $\delta=10$. The standoff pose for grasping is set as
10cm and 20cm from the grasping pose for the tabletop scenes and the shelf
scenes, respectively. The number of time steps is $T=50$, and the time span of
a trajectory is set to 10 seconds. Therefore, $dt=0.2$ in Eq. (6).

TABLE I: Comparison between different loss functions for IK. Count is the
total number of grasps tested for IK. The numbers of found IK solutions are
presented for three loss functions.

| Tabletop (success $\uparrow$) | Shelf (success $\uparrow$)
---|---|---
| Tabletop (success $\uparrow$ / collision $\downarrow$) | Shelf (success $\uparrow$ / collision $\downarrow$)
Robot | Count | Point | Quater- | Enler | Count | Point | Quater- | Euler
matching | nion | angle | matching | nion | angle
Fetch | 18,758 | 9,665 | 9,600 | 8,288 | 10,917 | 2,911 | 2,824 | 2,364
Panda | 20,000 | 16,397 | 15,905 | 10,596 | 12,000 | 3,925 | 3,867 | 3,172

TABLE II: Statistics of grasping experiments in the PyBullet simulator

| Tabletop (success $\uparrow$ / collision $\downarrow$) | Shelf (success $\uparrow$ / collision $\downarrow$)
---|---|---
Object | Count | Ours | Ours | OMG [16] | Count | Ours | Ours | OMG [16]
Fetch | Panda | Panda | Fetch | Panda | Panda
cracker box | 12 | 7 / 0 | 7 / 0 | 5 / 2 | 6 | 3 / 0 | 2 / 0 | 4 / 0
sugar box | 10 | 10 / 0 | 10 / 0 | 10 / 0 | 5 | 4 / 0 | 5 / 0 | 4 / 0
tomato soup can | 14 | 13 / 2 | 14 / 0 | 12 / 2 | 7 | 7 / 1 | 2 / 1 | 2 / 4
mustard bottle | 14 | 12 / 0 | 11 / 0 | 11 / 0 | 5 | 3 / 0 | 4 / 0 | 4 / 0
tuna fish can | 12 | 0 / 5 | 0 / 3 | 0 / 12 | 6 | 5 / 5 | 0 / 0 | 0 / 6
pudding box | 10 | 7 / 0 | 6 / 0 | 6 / 2 | 7 | 5 / 1 | 4 / 0 | 2 / 3
gelatin box | 14 | 11 / 0 | 10 / 0 | 4 / 2 | 7 | 6 / 1 | 1 / 1 | 2 / 3
potted meat can | 14 | 10 / 0 | 14 / 0 | 12 / 0 | 10 | 8 / 0 | 10 / 0 | 6 / 1
banana | 14 | 12 / 6 | 11 / 4 | 9 / 4 | 7 | 3 / 4 | 1 / 2 | 1 / 7
bleach cleanser | 10 | 9 / 0 | 5 / 0 | 8 / 0 | 7 | 5 / 0 | 6 / 0 | 4 / 4
bowl | 14 | 11 / 2 | 9 / 0 | 8 / 1 | 11 | 8 / 3 | 8 / 2 | 2 / 7
mug | 10 | 8 / 1 | 4 / 1 | 6 / 0 | 10 | 3 / 4 | 6 / 2 | 5 / 4
power drill | 14 | 14 / 2 | 12 / 0 | 12 / 0 | 7 | 4 / 0 | 2 / 1 | 1 / 4
scissors | 14 | 2 / 0 | 1 / 6 | 1 / 13 | 11 | 5 / 7 | 1 / 5 | 0 / 10
large marker | 12 | 1 / 3 | 4 / 5 | 4 / 9 | 5 | 3 / 2 | 0 / 3 | 0 / 5
extra large clamp | 12 | 5 / 6 | 2 / 5 | 4 / 11 | 9 | 6 / 2 | 1 / 2 | 1 / 9
ALL | 200 |  132 / 27 | 120 / 24 | 112 / 58 | 120 |  78 / 30 | 53 / 19 | 38 / 67

Figure 6: Illustration of the model-free grasping in the real world. TABLE
III: Comparison between our grasping trajectory optimization (GTO) and the
OMPL planning in [20] for model-free grasping.

Method # | Perception | Grasp Planning | Motion Planning | Control | Ordering | Pick-and-Place Success | Grasping Success
---|---|---|---|---|---|---|---
Model-free Grasping
1 | MSMFormer [33] | Contact-graspnet [29] \+ Top-down | OMPL [34] | MoveIt | Near-to-far | 57 / 100 | 65 / 100
2 | MSMFormer [33] | Contact-graspnet [29] \+ Top-down | GTO (Ours) | MoveIt | Near-to-far | 65 / 100 | 71 / 100

TABLE IV: Statistics of our grasping experiments for each YCB object. S:
#pick-and-place success, PEF: #perception failure, PLF: #planning failure, EF:
#execution failure

Object | Count | Method 1 (OMPL-based) | Method 2 (GTO-based Ours)
---|---|---|---
S | PEF | PLF | EF | S | PEF | PLF | EF
Order: Near-to-Far
cracker box | 6 | 4 | 1 | - | 1 | 4 | - | - | 2
sugar box | 5 | 5 | - | - | - | 5 | - | - | -
tomato soup can | 7 | 2 | 2 | 3 | - | 4 | 1 | 1 | 1
mustard bottle | 7 | 6 | - | 1 | - | 2 | 1 | 3 | 1
tuna fish can | 6 | 5 | 1 | - | - | 6 | - | - | -
pudding box | 5 | 4 | 1 | - | - | 5 | - | - | -
gelatin box | 7 | 6 | - | 1 | - | 7 | - | - | -
potted meat can | 7 | 5 | 2 | - | - | 2 | 1 | 4 | -
banana | 7 | 6 | - | - | 1 | 7 | - | - | -
bleach cleanser | 5 | - | 1 | 2 | 2 | 2 | 1 | - | 2
bowl | 7 | 6 | - | - | 1 | 7 | - | - | -
mug | 5 | 2 | - | 2 | 1 | 2 | - | 3 | -
scissors | 7 | - | 2 | 2 | 3 | 3 | 3 | - | 1
power drill | 7 | 3 | 3 | - | 1 | 2 | 3 | 1 | 1
large marker | 6 | 1 | 2 | 2 | 1 | 3 | 1 | 2 | -
extra large clamp | 6 | 2 | 1 | 2 | 1 | 4 | - | 2 | -
ALL | 100 | 57 | 16 | 15 | 12 | 65 | 11 | 16 | 8

###  IV-B The Effect of Point Matching for Goal Reaching

We evaluate the effectiveness of our point cloud-based representation for goal
reaching. Here, we solve the inverse kinematics optimization problem in Eq.
(10) with three different cost functions and compare their performance. The
first one is the point-matching cost function in Eq. (1) to measure the
difference between two transformations $\mathbf{T}_{T}$ and $\mathbf{T}_{g}$.
For the other two cost functions, we use quaternions
$(\tilde{\mathbf{q}}_{T},\tilde{\mathbf{q}}_{g})$ and Euler angles
$(\mathbf{e}_{T},\mathbf{e}_{g})$ to represent the 3D rotations, and compute
costs for rotation and translation separately:

$\displaystyle c_{\text{goal}}^{\text{quat}}(\mathbf{T}_{T},\mathbf{T}_{g})$
$\displaystyle=\|\mathbf{t}_{T}-\mathbf{t}_{g}\|^{2}+1-(\tilde{\mathbf{q}}_{T}\cdot\tilde{\mathbf{q}}_{g})^{2},$
(12) $\displaystyle
c_{\text{goal}}^{\text{euler}}(\mathbf{T}_{T},\mathbf{T}_{g})$
$\displaystyle=\|\mathbf{t}_{T}-\mathbf{t}_{g}\|^{2}+\|\mathbf{e}_{T}-\mathbf{e}_{g}\|^{2},$
(13)

where the distance between two quaternions measures the angular distance
between the two rotations.

Using the three cost functions, we solve IK for each grasp of each object in
the tabletop scenes and the shelf scenes. Table I presents the statistics of
this experiment, where we count the number of successful IK solutions among
all the trials. We consider an IK solution to be found after optimization if
the translation error is less than 1 cm and the rotation error is less than 5
degrees. From the table, we can see that using the point matching cost
function finds the maximum number of IK solutions, which validates the
effectiveness our point-cloud based representation. Using distances between
Euler angles is not a good choice due to the discontinuity between $-\pi$ and
$\pi$.

Figure 7: Examples of real-world grasping: (a) tabletop scenes and (b) shelf
scenes

###  IV-C Simulation Results

The results of our grasping experiments in PyBullet are presented in Table II,
where we compare our approach to the OMG-Planner [16]. The OMG-Planner is a
trajectory optimization method based on first-order gradient descent for joint
motion and grasp planning. It alternates between goal selection and fixed-goal
trajectory optimization. Grasps of the 16 YCB objects are generated using
GraspIt! [9]. In the simulation, we query the object poses directly and then
transform the grasps according to the object poses. We evaluate the number of
successful grasps and the number of collisions during grasping. Using our
point-cloud representation, we treat a grasping trajectory as in collision if
there are 5 surface points of the robot with negative signed distances.

For the table, we can see that 1) our method improves over the OMG-Planner in
both the tabletop scenes and the shelf scenes. Our method achieves higher
grasping success rates and lower collision rates. The main advantage of our
method is that we solve a constrained nonlinear optimization problem with an
advanced solver (Ipopt) compared to a gradient descent-based optimization. In
addition, our point-cloud representation enables more accurate goal reaching
and collision avoidance. 2) The Fetch robot achieves higher success rates
compared to the Panda robot, largely due to its greater reachability and wider
gripper. We cannot run the OMG-Planner for the Fetch robot since its
implementation is tightly coupled with the Panda robot. In contrast, our
implementation can be easily applied to different robots, where it only
requires an URDF of a robot as input. 3) Some objects are more difficult to
grasp. These are small or flat objects such as the tuna fish can, the
scissors, the large marker, and the extra large clamp. Nonprehensile grasping
strategies might be needed to grasp these objects successfully, which can be
explored in future work.

###  IV-D Model-free Grasping in the Real World

Lastly, we conduct grasping experiments in the real world to evaluate our
trajectory optimization method. We consider the task of model-free grasping,
where we do not have 3D models of objects for perception and motion planning.
Model-free grasping is applicable to diverse environments, and our approach
does not rely on 3D object models. Figure 6 illustrates the perception,
planning, and control pipeline for model-free grasping.

We utilized the MSMFormer [33] to segment unseen objects in an input RGB-D
image for tabletop scenes. For shelf scenes, we found that MSMFormer cannot
successfully segment objects in the shelf since it is not trained with similar
scenes. Therefore, we used Grounding DINO [35] with text prompt “objects” to
detect generic objects, and then used SAM [36] to segment objects inside the
bounding boxes from Grounding DINO. To synthesize grasps for a target object,
we used Contact-GraspNet [29], which takes a segmented point cloud of an
object as input and generates grasping poses of a parallel jaw gripper. These
planned grasps are treated as goals in the goal set for joint motion and grasp
planning. To execute a planned trajectory on a real robot, we also need to
generate accelerations of the robot joints on the trajectory. Since our method
does not solve for joint accelerations, we apply the path parameterization
method [37] to reparameterize the planned trajectory.

We compare our method with an OMPL [34]-based planning baseline in the
SceneReplica benchmark [20]. This baseline algorithm simply loops over all
goals in the goal set and checks if there is a collision-free motion plan to
reach a goal. The comparison results are presented in Table III. Our method
achieves a better grasping success rate and a better pick-and-place success
rate. Detailed evaluation statistics for each YCB object are presented in
Table IV, where we classify pick-and-place failures into perception failures,
planning failures, and execution failures. A detailed description of these
failure types can be found in [20]. Most failures are due to errors in object
segmentation, grasp planning, and grasping goal selection. Because stable
grasp is critical for pick-and-place success. By solving the trajectory
optimization problem, our method benefits from better goal selection compared
to the baseline algorithm. Figure 7 shows some examples of successful grasping
in the real world. Grasping videos can be found on the project page and in the
supplementary material.

###  IV-E Planning Time

Our approach has demonstrated a significant improvement in planning efficiency
over the OMPL-based baseline in the experiments conducted using the
SceneReplica Benchmark [20]. On average, our method achieves a planning time
of 15.4 seconds, which includes the computation time for the grasp collision
checking, the IK checking, and the trajectory optimization. However, the OMPL-
based baseline takes 45.6 seconds to find a grasp trajectory for a target
object. In contrast, the OMG-Planner achieves 3.2 seconds planning time by
solving parallel IKs and using GPUs for acceleration. We consider speeding up
our method for future work.

##  V Conclusion and Discussion

We introduce a new trajectory optimization method for joint motion and grasp
planning. The core component of our method is a point cloud-based
representation for robots and task spaces. This representation is
generalizable to different robots and different environments. We formulate
goal reaching and collision avoidance in the trajectory optimization using the
point-cloud representation. By solving a constrained nonlinear optimization
problem using the Ipopt solver, our method can generate robot trajectories for
grasping. Experiments are conducted in simulation and in the real world to
demonstrate the effectiveness of our method.

One limitation of our method is that the trajectory optimization is slow when
relying on an external solver. Future work includes speeding up the
optimization. One direction is to explore using GPUs for parallel computing.
Another direction is to explore model predictive control with our point-cloud
representation for robotic grasping. To further improve the grasping success
rate, a grasp planner that considers force closure or grasp stability will be
helpful.

Acknowledgement. This work was supported in part by the DARPA Perceptually-
enabled Task Guidance (PTG) Program under contract number HR00112220005 and
the Sony Research Award Program.

## References

  * [1] S. LaValle, “Rapidly-exploring random trees: A new tool for path planning,” _Technical Report. Computer Science Department, Iowa State University_ , 1998.
  * [2] J. Kuffner and S. LaValle, “RRT-connect: An efficient approach to single-query path planning,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , vol. 2, 2000, pp. 995–1001.
  * [3] S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” _The International Journal of Robotics Research (IJRR)_ , vol. 30, no. 7, pp. 846–894, 2011.
  * [4] L. Janson, E. Schmerling, A. Clark, and M. Pavone, “Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions,” _The International Journal of Robotics Research (IJRR)_ , vol. 34, no. 7, pp. 883–921, 2015.
  * [5] N. Ratliff, M. Zucker, A. Bagnell, and S. Srinivasa, “CHOMP: Gradient optimization techniques for efficient motion planning,” _IEEE International Conference on Robotics and Automation (ICRA)_ , 2009.
  * [6] J. Schulman, Y. Duan, J. Ho, A. Lee, I. Awwal, H. Bradlow, J. Pan, S. Patil, K. Goldberg, and P. Abbeel, “Motion planning with sequential convex optimization and convex collision checking,” _The International Journal of Robotics Research (IJRR)_ , vol. 33, no. 9, pp. 1251–1270, 2014.
  * [7] M. Mukadam, J. Dong, X. Yan, F. Dellaert, and B. Boots, “Continuous-time gaussian process motion planning via probabilistic inference,” _The International Journal of Robotics Research (IJRR)_ , vol. 37, no. 11, pp. 1319–1340, 2018.
  * [8] T. Stouraitis, L. Yan, J. Moura, M. Gienger, and S. Vijayakumar, “Multi-mode trajectory optimization for impact-aware manipulation,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 9425–9432.
  * [9] A. Miller and P. Allen, “Graspit! A versatile simulator for robotic grasping,” _IEEE Robotics & Automation Magazine_, vol. 11, no. 4, pp. 110–122, 2004.
  * [10] A. Mousavian, C. Eppner, and D. Fox, “6-DOF GraspNet: Variational grasp generation for object manipulation,” in _International Conference on Computer Vision (ICCV)_ , 2019, pp. 2901–2910.
  * [11] J. Urain, N. Funk, J. Peters, and G. Chalvatzaki, “Se (3)-diffusionfields: Learning smooth cost functions for joint grasp and motion optimization through diffusion,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 5923–5930.
  * [12] N. Vahrenkamp, M. Do, T. Asfour, and R. Dillmann, “Integrated grasp and motion planning,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , 2010, pp. 2883–2888.
  * [13] J. Fontanals, B.-A. Dang-Vu, O. Porges, J. Rosell, and M. Roa, “Integrated grasp and motion planning using independent contact regions,” in _IEEE-RAS International Conference on Humanoid Robots_ , 2014, pp. 887–893.
  * [14] J. Haustein, K. Hang, and D. Kragic, “Integrating motion and hierarchical fingertip grasp planning,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , 2017, pp. 3439–3446.
  * [15] A. Dragan, N. Ratliff, and S. Srinivasa, “Manipulation planning with goal sets using constrained trajectory optimization,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , 2011, pp. 4582–4588.
  * [16] L. Wang, Y. Xiang, and D. Fox, “Manipulation trajectory optimization with online grasp synthesis and selection,” _arXiv preprint arXiv:1911.10280_ , 2019.
  * [17] C. Eppner, A. Mousavian, and D. Fox, “A billion ways to grasp: An evaluation of grasp sampling schemes on a dense, physics-based grasp data set,” in _International Symposium on Robotics Research (ISRR)_ , 2019.
  * [18] A. Wächter and L. T. Biegler, “On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming,” _Mathematical programming_ , vol. 106, pp. 25–57, 2006.
  * [19] “PyBullet,” https://pybullet.org/wordpress/.
  * [20] N. Khargonkar, S. H. Allu, Y. Lu, B. Prabhakaran, Y. Xiang, _et al._ , “Scenereplica: Benchmarking real-world robot manipulation by creating reproducible scenes,” _arXiv preprint arXiv:2306.15620_ , 2023.
  * [21] A. Dragan, G. Gordon, and S. Srinivasa, “Learning from experience in manipulation planning: Setting the right goals,” in _International Symposium on Robotics Research (ISRR)_ , 2011.
  * [22] M. Kalakrishnan, S. Chitta, E. Theodorou, P. Pastor, and S. Schaal, “STOMP: Stochastic trajectory optimization for motion planning,” in _IEEE International Conference on Robotics and Automation (ICRA)_ , 2011, pp. 4569–4574.
  * [23] M. Kang, H. Shin, D. Kim, and S.-E. Yoon, “Torm: Fast and accurate trajectory optimization of redundant manipulator given an end-effector path,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 9417–9424.
  * [24] S. Jin, D. Romeres, A. Ragunathan, D. K. Jha, and M. Tomizuka, “Trajectory optimization for manipulation of deformable objects: Assembly of belt drive units,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 10 002–10 008.
  * [25] M. Spahn, B. Brito, and J. Alonso-Mora, “Coupled mobile manipulation via trajectory optimization with free space decomposition,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 12 759–12 765.
  * [26] J. Ichnowski, M. Danielczuk, J. Xu, V. Satish, and K. Goldberg, “Gomp: Grasp-optimized motion planning for bin picking,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 5270–5277.
  * [27] B. Sundaralingam, S. K. S. Hari, A. Fishman, C. Garrett, K. Van Wyk, V. Blukis, A. Millane, H. Oleynikova, A. Handa, F. Ramos, _et al._ , “Curobo: Parallelized collision-free robot motion generation,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 8112–8119.
  * [28] Y. Xiang, T. Schmidt, V. Narayanan, and D. Fox, “Posecnn: A convolutional neural network for 6d object pose estimation in cluttered scenes,” _arXiv preprint arXiv:1711.00199_ , 2017.
  * [29] M. Sundermeyer, A. Mousavian, R. Triebel, and D. Fox, “Contact-graspnet: Efficient 6-dof grasp generation in cluttered scenes,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 13 438–13 444.
  * [30] J. A. E. Andersson, J. Gillis, G. Horn, J. B. Rawlings, and M. Diehl, “CasADi – A software framework for nonlinear optimization and optimal control,” _Mathematical Programming Computation_ , vol. 11, no. 1, pp. 1–36, 2019.
  * [31] B. Calli, A. Walsman, A. Singh, S. Srinivasa, P. Abbeel, and A. Dollar, “Benchmarking in manipulation research: The YCB object and model set and benchmarking protocols,” _IEEE Robotics and Automation Magazine_ , vol. 22, no. 3, pp. 36–52, 2015.
  * [32] C. E. Mower, J. Moura, N. Z. Behabadi, S. Vijayakumar, T. Vercauteren, and C. Bergeles, “Optas: An optimization-based task specification library for trajectory optimization and model predictive control,” _arXiv preprint arXiv:2301.13512_ , 2023.
  * [33] Y. Lu, Y. Chen, N. Ruozzi, and Y. Xiang, “Mean shift mask transformer for unseen object instance segmentation,” _arXiv preprint arXiv:2211.11679_ , 2022.
  * [34] I. A. Sucan, M. Moll, and L. E. Kavraki, “The open motion planning library,” _IEEE Robotics & Automation Magazine_, vol. 19, no. 4, pp. 72–82, 2012.
  * [35] S. Liu, Z. Zeng, T. Ren, F. Li, H. Zhang, J. Yang, C. Li, J. Yang, H. Su, J. Zhu, _et al._ , “Grounding dino: Marrying dino with grounded pre-training for open-set object detection,” _arXiv preprint arXiv:2303.05499_ , 2023.
  * [36] A. Kirillov, E. Mintun, N. Ravi, H. Mao, C. Rolland, L. Gustafson, T. Xiao, S. Whitehead, A. C. Berg, W.-Y. Lo, _et al._ , “Segment anything,” _arXiv preprint arXiv:2304.02643_ , 2023.
  * [37] H. Pham and Q.-C. Pham, “A new approach to time-optimal path parameterization based on reachability analysis,” _IEEE Transactions on Robotics_ , vol. 34, no. 3, pp. 645–659, 2018.


# An Incentive Mechanism for Crowd Sensing with Colluding Agents

Susu Xu, Weiguang Mao, Yue Cao, Hae Young Noh, Nihar B. Shah
Carnegie Mellon University
{susux, weiguanm<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Vehicular mobile crowd sensing is a fast-emerging paradigm to collect data
about the environment by mounting sensors on vehicles such as taxis. An
important problem in vehicular crowd sensing is to design payment mechanisms
to incentivize drivers (agents) to collect data, with the overall goal of
obtaining the maximum amount of data (across multiple vehicles) for a given
budget. Past works on this problem consider a setting where each agent
operates in isolation—an assumption which is frequently violated in practice.
In this paper, we design an incentive mechanism to incentivize agents who can
engage in arbitrary collusions. We then show that in a “homogeneous” setting,
our mechanism is optimal, and can do as well as any mechanism which knows the
agents’ preferences a priori. Moreover, if the agents are non-colluding, then
our mechanism automatically does as well as any other non-colluding mechanism.
We also show that our proposed mechanism has strong (and asymptotically
optimal) guarantees for a more general “heterogeneous” setting. Experiments
based on synthesized data and real-world data reveal gains of over 30%
attained by our mechanism compared to past literature.

##  1 Introduction

Mobile Crowd Sensing (MCS) is a new and fast-rising community sensing paradigm
to fulfill the increasing demand of diverse urban sensing data. The recent
proliferation of mobile smart devices (e.g., smart phones, smart watches,
etc.) provides increasingly capable sources of sensors (e.g., GPS, gyroscope,
accelerometer, camera, etc.) to MCS applications. In MCS, crowdsoucer engages
a crowd of participants (called agents) to collect sensory data using existing
pervasive mobile devices (Ganti et al.,, 2011; Lane et al.,, 2010), allowing
for collection of diverse data at scale. In an MCS system, after obtaining
data from agents, the crowdsoucer cleans and analyzes the data for various
applications such as smart city management (Thiagarajan et al.,, 2009; Dutta
et al.,, 2009) and social applications (Eisenman et al.,, 2009; Zheng et al.,,
2013). Vehicular MCS is a type of MCS that employs vehicles such as taxis as
agents. It is gaining increasing popularity in recent times particularly for
applications such as air/noise pollution monitoring (Zheng et al.,, 2013;
Devarakonda et al.,, 2013), transportation monitoring (Thiagarajan et al.,,
2009; Wan et al.,, 2016), and infrastructure monitoring (Hull et al.,, 2006).
In vehicular MCS, a crowdsoucer employs monetary incentives to motivate agents
(drivers) to share spatial-temporal information collected along with their
trajectories. Here, agents first “bid” the amount of monetary remunerations
they wish to receive from the crowdsourcer for the task of collecting and
reporting data. The bid by an agent is supposed to reflect the “threshold” of
remuneration beyond which they will accept to do the task and below which they
will not. The crowdsourcer then makes a monetary offer to each agent, which
the agent may accept and perform the task. The overall goal of the
crowdsourcer is to get the maximum possible number of tasks done (that is,
obtain the maximum amount of data) for a given budget, and the goal of the
agents is to maximize the monetary remunerations they receive.

Various past works have studied and developed incentive mechanisms to motivate
agents to bid truthfully in crowdsensing applications; see (Duan et al.,,
2012; Yang et al.,, 2012; Zhao et al.,, 2014; Jin et al.,, 2017) and
references therein. The methods proposed in past literature, however, operate
under the assumption that the agents (drivers) never communicate or collude
with each other. This assumption of non-collusion is known to be frequently
violated in practice. For example, taxi drivers can discuss and collaborate
via their radio systems or in person. Such collusions present significant
challenges to the design of crowd sensing systems and the collection of
quality data with an efficient utilization of the crowdsourcer’s budget. For
instance, the recent paper (Ji and Chen,, 2017) warns that collusions among
agents may result in “serious problems for the platform, such as losing
system-wide utility and deteriorating other users’ enthusiasm to participate.”
A number of other research studies (Wang et al.,, 2013, 2014) have shown that
with the increasing of colluding agents, it becomes more difficult to
eliminate the effects of collusion attacks on the crowd sensing system. A
second approach to combat collusions – at least in crowdsourcing applications
– is to assume knowledge of some “gold standard” ground truth (Gneiting and
Raftery,, 2007; Lambert and Shoham,, 2009; Shah and Zhou, 2016a, ; Shah et
al.,, 2015; Shah and Zhou, 2016b, ) and design proper scoring rules. However,
this is a very strong assumption in our crowdsensing setting, and we will not
make any such assumption in this paper.

In this paper, we propose a novel incentive mechanism – termed “In _sense_
tive Mechanism”111The name captures the fact that it is an _in_ cen _tive_
mechanism to crowd _sense_ , and also highlights its primary feature that it
is insensitive to collusions among agents. – for the crowd sensing problem
with colluding agents. We prove that in a setting where the thresholds of
agents are “homogeneous”, our In _sense_ tive Mechanism is optimal in that
truth-telling is optimal for the agents, and the number of tasks is maximized
for the crowdsourcer when agents report truthfully. We then move on to a more
general “heterogeneous” threshold setting where we first prove the
impossibility of any mechanism that can ensure truth-telling; we then show
that our proposed In _sense_ tive Mechanism continues to fare quite well even
in this setting. In numerical evaluations, we find that our proposed mechanism
consistently outperforms the state-of-the-art and can lead to gains of 30% or
higher in the amount of data collected under a given budget.

The rest of the paper is organized as follows. We formally introduce the
problem in Section 2. We then present our main results including our
mechanism, theoretical guarantees, and numerical evaluations, in Section 3. We
conclude the paper with a discussion in Section 4. This paper also includes
proofs of our main theoretical results in appendix.

##  2 Problem formulation

The system consists of a crowdsourcer with budget $B>0$, and $M\geq 2$ agents,
whom we index as $1,\ldots,M$. Each agent has some private threshold
$T_{m}^{*}\geq 0$ such that the agent is incentivized to collect data in that
round if and only if the remuneration provided by the crowdsourcer is at least
$T_{m}^{*}$. This threshold captures the willingness of the agent to carry out
the data collection task, and is assumed to be constant across the $N$ rounds.
This assumption is reasonable as the duration of each round and the entire
game are usually short (few hours), and consequently the thresholds of drivers
vary little across the rounds (Devarakonda et al.,, 2013; Hasenfratz et al.,,
2015). The threshold is known to that agent, but unknown to the crowdsourcer.
The entire process comprises $N\geq 1$ rounds of data collection. At the
beginning of each round (say, round $n\in\\{1,\ldots,N\\}$), the agents may
communicate with each other, and then each agent (say agent $m$) bids a number
$T_{m,n}$ to the crowdsourcer. This bid is supposed to represent the true
threshold of that agent; however, the agents may be strategic and report a
larger number on purpose. We allow for every agent to be cognizant of each
others’ true thresholds as well as bids. The crowdsourcer then offers each
agent (say, agent $m$) a reward $R_{m,n}$ if the agent agrees to collect data
in the current round $n$. Each agent may then accept or reject the reward. If
an agent accepts, then the agent collects and reports data to the crowdourcer
in that round and obtains the reward $R_{m,n}$; otherwise the agent does not
collect data or receive the reward. We term the data obtained by the
crowdsourcer from each agent for each round as one data point.

The overall goal of the crowdsourcer is to maximize the number of data points
obtained across $N$ rounds, subject to the budget constraint. As we assume
that the entire incentive mechanism employed is publically known, it is
possible for the agents to collude and exploit the mechanism to maximize their
own utility. We formulate the objective of the crowdsourcer and the agents in
the sections below.

###  2.1 Objective of the crowdsourcer

The objective of the crowdsourcer is to design an appropriate incentive
mechanism to ensure that after $N$ rounds, the budget is best utilized to
collect as much data as possible. The objective function refers to the amount
of accepted tasks, which equals to the final amount of collected data. We
formulate the optimization problem for crowdsourcer in Equation (1) below:

$\displaystyle\max_{\\{R_{m,n}\\}_{m=1\ldots M,n=1\ldots N}}$
$\displaystyle~{}~{}\sum_{n=1}^{N}\sum_{m=1}^{M}I(R_{m,n}\geq T_{m}^{*})$ (1a)
such that $\displaystyle\sum_{n=1}^{N}\sum_{m=1}^{M}R_{m,n}\leq B$ (1b)

Here $I$ denotes the indicator function. The objective of the crowdsourcer is
to maximize the total number of data points collected (1a), or in other words,
the total number of tasks accepted by the agents. Note that any agent $m$
during round $n$ will agree to perform the task if and only if $R_{m,n}\geq
T^{*}_{m}$. The threshold $T_{n}^{*}$ represents the minimum monetary
incentive required for the agent motivate herself/himself to accept a task
(Angelopoulos et al.,, 2014). We also note that the crowdsourcer cannot simply
solve the problem (1) as a standard optimization problem because it does not
know the true thresholds $\\{T^{*}_{m}\\}_{m=1}^{M}$ of the agents.

In this paper, we will measure the efficiency of any mechanism in terms of its
_regret_ defined as follows. We let $\alpha^{*}$ denote the optimal value of
the objective (1) that the crowdsourcer can achieve in the hypothetical
situation that all agents always report their thresholds truthfully. In this
case, the values of thresholds $\\{T^{*}_{m}\\}_{m=1}^{M}$ become known to the
crowdsourcer, and the problem (1) then turns out to be a simple packing
problem. Then for any proposed mechanism to elicit the thresholds as bids from
the agents, we denote the (expected) value of the objective (1a) achieved by
the mechanism as $\widetilde{\alpha}$. We then define the regret $\beta$ of
this mechanism as

$\displaystyle\beta:=\alpha^{*}-\widetilde{\alpha}.$

_The goal is to design incentive mechanisms that have the smallest regret
$\beta$ possible._

###  2.2 Objective of agents

The objective of an agent is to maximize the total remuneration they earn
across the $N$ rounds. Specifically, any agent $m$ will report thresholds
$\\{T_{m,n}\\}_{n=1}^{N}$ that maximize the objective

$\displaystyle\sum_{n=1}^{N}R_{m,n}~{}I(R_{m,n}\geq T_{m}^{*}).$ (2)

Here, $\\{R_{m,n}\\}_{n=1}^{N}$ is the set of remunerations provided by the
crowdsourcer’s mechanism for the reported bids of the agents.222One may
additionally want to subtract out any costs incurred by the agents from their
objective. However, in the practical setting of crowd sensing from taxi
drivers, the agents suffer only a negligible cost (Zhang et al.,, 2016) as
they only need to perform a few operations on their phone. Finally, if there
exist multiple strategies to obtain the maximum profit, the agent will follow
the strategy that requires accepting the smallest number of tasks.

###  2.3 Equilibrium of colluding agents

In this section we discuss the idea of equilibrium among agents that might
collude in price rigging. We begin by noting that because of the possible
collusion, the widely used Nash equilibrium is inappropriate in our context.
Hence we instead employ the notion of perfect cooperative equilibrium (PCE)
(Rong and Halpern,, 2014) that is better suited to model colluding agents.

In order to formally define PCE, we first introduce the concepts of best
response and best utility. Consider an $M$-agent game $G$ with a set of agents
denoted as $[M]$. Let $S_{i}$ be the set of strategies for any agent
$i\in[M]$, and $s_{i}\in S_{i}$ the strategy that agent $i$ will take,
$s_{-i}$ the (vector of) strategies that agents in $[M]\backslash\\{i\\}$ take
in game $G_{s_{i}}$. The utility obtained by agent $i$ taking strategy $s_{i}$
and others taking $s_{-i}$ is denoted as $U_{i}(s_{i},s_{-i})$.

The notion of best response in the game $G$ is then defined as such: Let
$G_{s_{i}}$ be the ($M$-$1$)-agent game among agents in the set
$[M]\backslash\\{i\\}$ when agent $i$ takes strategy $s_{i}$. The strategy
$s_{i}$ is called a best response in game $G$ if $s_{i}$ maximizes agent $i$’s
expected utility $U_{i}(s_{i},s_{-i})$ given that the other agents are playing
a Nash Equilibrium $s_{-i}\in$ $NE^{G}(s_{i})$ in $G_{s_{i}}$. Given the fixed
budget $B$, $U^{*}_{i}$ is the upper bound of utility agent $i$ can obtain for
any possible strategy $s_{i}$ when other agents reach a Nash Equilibrium
$NE^{G}(s_{i})$ in $G_{s_{i}}$ correspondingly. We define this upper bound,
$U^{*}_{i}$ as the best utility.

$\displaystyle U^{*}_{i}:=\sup_{s_{i}\in S_{i},s_{-i}\in
NE^{G}(s_{i})}U_{i}(s_{i},s_{-i}).$

With these preliminaries, we are now ready to define PCE.

######  Definition 1 (Perfect cooperative equilibrium, PCE).

A strategy profile $s$ is a perfect cooperative equilibrium (PCE) in an
$M$-agent game if for every agent $i\in[M]$, we have

$\displaystyle U_{i}(s_{i},s_{-i})\geq U^{*}_{i}.$

The definition of PCE coincides with the intuition if a strategy generates
greater or equal utility for an agent than the utility obtained by her/him
acting selfishly, then it is stable and will be favored by all agents.

##  3 Main results

In this section, we present our proposed In _sense_ tive Mechanism and provide
associated guarantees.

###  3.1 In _sense_ tive Mechanism

Input : Total budget $B$, Number of rounds $N$, Number of agents $M$, Set of
agents $[M]=\\{m\\}_{m=1}^{M}$

Output : incentives collected $\\{R_{m,n}|m\in[M],n\in N\\}$

1 initialize $R_{m,n}\leftarrow 0$ for each agent $m$, round $n$

2 initialize thresholds $T_{m,0}\leftarrow\infty$ for each agent $m$

3 initialize allocated budget $B_{used}\leftarrow 0$

4 broadcast $B,N,M$

5 for  _$n\leftarrow 1$ to $N$_ do

6 for  _$m\leftarrow 1$ to $M$_ do

// Thresholds update

7 collect submitted bid of agent $m$ as $T_{m,n}$

8 $T_{m,n}\leftarrow min(T_{m,n},T_{m,n-1})$

9

10 end for

// Calculate incentive

11
$R\leftarrow\min\Big{(}T_{1,n},\cdots,T_{M,n},\dfrac{B-B_{used}}{N-n+1}\Big{)}$

// Select agents

12 $K\leftarrow\Big{\lfloor}\dfrac{B-B_{used}}{R\times(N-n+1)}\Big{\rfloor}$

13

14 stable sort the list of agents $\\{m\\}_{m=1}^{M}$ in ascending order
according to their thresholds $\\{T_{m,n}\\}_{m=1}^{M}$, choose top $K$ agents
as $selected$

// Task allocation

15 for  _$m\in selected$_ do

16 assign task to $m$ with incentive $R$

17 if  _$m$ accepts task_ then

$R_{m,n}\leftarrow R$ // Assign incentive

$T_{m,n}\leftarrow R_{m,n}$ // Calibrate threshold

18 $B_{used}\leftarrow B_{used}+R_{m,n}$

19

20 end if

21

22 end for

23

24 end for

Algorithm 1 In _sense_ tive Mechanism

We begin with an intuition of our proposed In _sense_ tive Mechanism. To
achieve the objective of the crowdsourcer, we need an incentive mechanism that
prevents agents from bid rigging. The key idea here is to differentiate the
agents so that for any potential collusion, there exist some disadvantaged
agents who are incentivized to betray and compete. Compared to conventional
incentive mechanisms (Prelec,, 2004; Kamble et al.,, 2015; Jin et al.,, 2017;
Zheng et al.,, 2017) which treat players symmetrically, In _sense_ tive
Mechanism is asymmetric, in the sense that it selects and pays the agents
depending on their (arbitrary yet fixed) indices. As a simple example to
illustrate this point, consider two agents with indices $i<j$, who agree to
always bid at the same price. If we can only afford to choose one agent for
each round, then our In _sense_ tive Mechanism always selects agent $i$. A
second key idea in the construction of In _sense_ tive Mechanism is to
identify and address two extremal strategies that could be excuted by the
colluding agents, and suitably smooth out the resulting mechanism to handle
all non-extremal strategies as well. The first extremal strategy we identify
is when every agent bids very high initially hoping that the mechanism will be
fooled into believing that their true thresholds are very high and thereby
paying a large amount of budget for fewer tasks. In order to circumvent this
attack, our algorithm imposes a carefully chosen upper bound on the reward
paid in each round, and this upper bound depends on the budget and the number
of rounds that remains. The second extremal strategy we identify is when every
agent bids low initially and rejects the rewards from initial rounds so that
the mechanism may pay a higher amount (per task) for later tasks due to a
large leftover budget. We foil this attack by ensuring that the budget is
distributed across different rounds in a relatively uniform manner.

With these intuitions, we are now ready to formally present the In _sense_
tive Mechanism in Algorithm 1. We parse through the details of the mechanism
in the remainder of this subsection. The mechanism first calibrates current
estimation of each agent’s threshold based on their bids in the current round
and the estimated thresholds from the previous round. After updating the
thresholds of all the agents, $R$, the amount of incentive given for
completing one task in the current round, is calculated by taking the minimum
among $T_{1,n},\cdots,T_{M,n}$. Notice that $R$ is upper bounded by
$(B-B_{used})/(N-n+1)$, which helps even out the amount of budget spent in
each round. This also implies that if
$\min(\\{T_{m,n}\\}_{m=1}^{M})>\dfrac{B-B_{used}}{N-n+1}$, then we still try
to pay one agent $(B-B_{used})/(N-n+1)$ instead of not paying anyone, as a
strategy to elicit a potentially lower threshold from some dishonest agents.
Based on the amount of reward $R$ for a single task, we decide $K$, the number
of agents we select in this round.

The selection process is done by stable sorting the list of all agents based
on their bids. The original list is ordered by agent’s index, so that 1)
agents with smaller bids are prioritized over those with larger bids, and 2)
agents with smaller indices are always preferred over those with larger
indices. This stable sort step is known to all agents, and intentionally
creates a differentiation among agents. Thus in any potential collusion, there
exists a most disadvantaged agent who is always the last to be selected and
can only collect the leftover compared to other group members. Under our In
_sense_ tive Mechanism, this disadvantaged agent knows that she/he can only
gain more if 1) she/he is prioritized in the selection step, which means
she/he has to bid lower than others, or 2) there is more budget left when
she/he gets selected, which means that agents with smaller indices must get
fewer payment per round. In any case, this agent is incentivized to defect and
bring down the bids.

Finally, if every agent bids higher than the upper bound for each round in
order to save budget for later rounds, we will try to pay $R$ to see if some
of the agents will accept it. If the task is accepted with $R$, we will update
$B_{used}$ and our estimation of agent’s threshold $T_{m,n}$.

###  3.2 Optimality with homogeneous thresholds

In this section, we present the optimality guarantee for our proposed In
_sense_ tive Mechanism for a setting with “homogeneous” thresholds. In this
homogeneous-threshold setting, we assume that all agents have the same
threshold, that is, $T_{1}^{*}=\cdots=T_{M}^{*}=T^{*}$. The following results
show that our mechanism is optimal in this homogeneous setting.

######  Theorem 1.

In the homogeneous threshold setting, under the In _sense_ tive Mechanism, the
honest strategy is a perfect cooperative equilibrium (PCE) for all agents, and
the In _sense_ tive Mechanism achieves a zero regret.

This result shows that when the thresholds are homogeneous, the In _sense_
tive Mechanism can surprisingly achieve the same performance as if the
thresholds were known exactly to the algorithm. Consequently, even if the
agents did not collude, the In _sense_ tive Mechanism performs at least as
well as any algorithm designed specifically to exploit the non-colluding
assumptions. The proof of Theorem 1 is provided in Appendix A.

###  3.3 Bounded regret with heterogeneous thresholds

In this section, we consider a more general situation where different agents
can have different thresholds. We present both negative and positive results
for this setting.

####  3.3.1 Suboptimality of any mechanism

Recall that in the homogeneous threshold setting, our In _sense_ tive
Mechanism achieves a zero regret. Given this result, a natural question that
arises is whether there exists an algorithm that can provide a zero regret
guarantee for the heterogeneous setting as well. In this section we show that
unfortunately no mechanism can provide such a strong guarantee in this general
setting.

######  Theorem 2.

In the heterogeneous threshold setting, no mechanism can ensure that honest
strategy is a perfect cooperative equilibrium (PCE).

The proof of this result is provided in Appendix B.

####  3.3.2 In _sense_ tive Mechanism in heterogeneous situation

We now provide an upper bound on the regret of our In _sense_ tive Mechanism
in the general heterogeneous threshold setting.

######  Theorem 3.

The regret $\beta$ attained by In _sense_ tive Mechanism in the heterogeneous
setting is upper bounded as

$\displaystyle\beta\leq$ $\displaystyle\begin{cases}\alpha^{*}-iN&\emph{if
}iT_{i}^{*}<B/N\leq iT_{i+1}^{*}\\\
\alpha^{*}-\Big{(}iN+\Big{\lfloor}\frac{B-iNT_{i+1}^{*}}{T_{i+1}^{*}}\Big{\rfloor}\Big{)}&\emph{if
}iT_{i+1}^{*}<B/N\leq(i+1)T_{i+1}^{*}\\\
\alpha^{*}-\Big{\lceil}\frac{B}{T_{2}^{*}}\Big{\rceil}&\emph{if }B/N\leq
T_{2}^{*}\\\ \alpha^{*}-MN&\emph{if }B/N>MT_{M}^{*},\end{cases}$

where

$\displaystyle\alpha^{*}=\sum_{i=0}^{M}\min\Big{(}\Big{\lfloor}\frac{B-N\sum_{k=1}^{i}T_{k}^{\star}}{T_{i+1}^{\star}}\Big{\rfloor},N\Big{)}.$

Moreover, for every value of $N$, $M$ and heterogeneous thresholds, the
algorithm attains $\beta=0$ when $B$ is large enough.

The proof of this result is presented in Appendix C.

####  3.3.3 Numerical experiments

Figure 1: A heterogeneous threshold scenario where the game has $5$ rounds and
$5$ vehicles with real thresholds of $20,40,50,70$ and $100$. The regret
$\beta$ of our In _sense_ tive Mechanism (solid blue line) is consistently and
significantly smaller as compared to the prior state-of-the-art _BEACON_
(dotted brown line).

We now present some numerical simulations that compare the performance of our
In _sense_ tive Mechanism with the state of the art. As discussed earlier,
past literature focuses on a non-colluding setting, and here we compare with
_BEACON_ (Zheng et al.,, 2017) which is the well-known mechanism for the non-
colluding setting.

Figure 1 compares the regret $\beta$ of our In _sense_ tive Mechanism with
_BEACON_ for a 5-round 5-agent game in the heterogeneous setting where agents
have true thresholds as $20,40,50,70,100$. The budget ranges from $20$ to
$3,000$. Overall, our mechanism collects $82.94\%$ of the total number of data
points compared to $\alpha^{*}$, whereas BEACON attains only $46.63\%$ of
$\alpha^{*}$ on average. Compared to _BEACON_ , our In _sense_ tive Mechanism
achieves an improvement of $36.31\%$.

####  3.3.4 Experiments on real-world data

Figure 2: A real-world scenario where the game has $6$ rounds and $50$
vehicles with real heterogeneous thresholds. With different amounts of budget,
the regret $\beta$ of our In _sense_ tive Mechanism (solid blue line) is
significantly smaller than the baseline method _BEACON_ (dotted brown line).

We collected the real-time surge rates, which reflect how many times of the
base fare drivers expect to get after riding passengers, from the real-world
ride-sharing companies. We used these heterogeneous surge rates to represent
the real heterogeneous thresholds of different cars. Therefore, the real
threshold of each car was estimated by combining the base fare during a fixed
length of time, which was a constant for all cars, and its individual surge
rate. We collected the data of around 5,000 cars during 11 days. The data
showed that the surge rates of most cars slightly vary with time and location.

Figure 2 compares the regret $\beta$ of our In _sense_ tive Mechanism with
_BEACON_ for a 6-round 50-agent game with different budgets. The budget ranges
from 1,500 to 6,000. Compared to $\alpha^{*}$, our In _sense_ tive Mechanism
manages to collect $96.21\%$ of the total data points , while BEACON only
acquires $63.08\%$ of $\alpha^{*}$ on average. Our mechanism improves the
performance of $33.13\%$ compared to _BEACON_.

Figure 3: A real-world scenario where the game has $6$ rounds and a fixed
budget of $3,000$. As the number of vehicles varies, the regret $\beta$ of our
In _sense_ tive Mechanism (solid blue line) consistently outperforms the
baseline method _BEACON_ (dotted brown line).

Figure 3 compares the regret $\beta$ of our In _sense_ tive Mechanism with
_BEACON_ for a 6-round game with a fixed budget of $3,000$ and the number of
cars ranges from $20$ to $80$. As the number of cars increases, the regret of
_BEACON_ increases accordingly. However, the regret of our In _sense_ tive
Mechanism first achieves the peak with $50$ cars and then decreases, which
demonstrates the robustness of our mechanisms. Given a fixed budget, our
mechanism can collect $95.86\%$ of the total number of points, which achieves
an improvement of $33.52\%$ on average compared to _BEACON_.

##  4 Discussion

Vehicular crowd sensing is a fast emerging paradigm to collect data for
various modern applications. In this paper, we design the In _sense_ tive
Mechanism to incentivize agents to collect and report data, with a focus on
addressing the challenge of collusion among agents. We show that if the
setting is homogeneous in nature, our mechanism performs as well as the best
algorithm when the agents’ preferences are known (that is, achieves a zero
regret). We also provide negative and positive results for the heterogeneous
setting: no mechanism can ensure a zero regret, while our mechanism performs
reasonably well.

A key idea behind our In _sense_ tive Mechanism that helps to combat collusion
is the introduction of a bias in the choice of the agents. Interestingly,
while biases are often undesirable in applications such as statistical
learning (Nie et al.,, 2017; Wang and Shah,, 2018), we find that a deliberate
introduction of bias is beneficial in this game-theoretic setting.

In future work, we wish to incorporate the learning of the spatial-temporal
distribution of thresholds of agents from their history. The goal is to design
incentive mechanisms that can exploit this “prior” knowledge in order to
achieve a lower regret in the heterogeneous setting.

Acknowledgments. This work was supported in part by Carnegie Mellon
University’s Mobility21 National University Transportation Center (grant
number 69A3551747111), which is sponsored by the US Department of
Transportation, the Dowd Fellowship from the College of Engineering at
Carnegie Mellon University, Intel, Google, and NSF grants CRII: CIF: 1755656
and CCF: 1763734.

##  Appendix A Proof of Theorem 1

In our proposed mechanism, given $B\leq MNT^{*}$, the honest strategy produces
a deterministic reward for each agent:

$\displaystyle U_{1}(s)$
$\displaystyle=\min\Big{(}N,\Big{\lfloor}\frac{B}{T^{*}}\Big{\rfloor}\Big{)}T^{*}$
(3a) $\displaystyle U_{2}(s)$
$\displaystyle=\min\Big{(}N,\Big{\lfloor}\frac{B-U_{1}}{T^{*}}\Big{\rfloor}\Big{)}T^{*}$
(3b) $\displaystyle\ldots$ $\displaystyle U_{M}(s)$
$\displaystyle=\Big{\lfloor}\frac{B-U_{1}(s)-\ldots-
U_{M-1}(s)}{T^{*}}\Big{\rfloor}T^{*}$ (3c)

The Equation (3a), (3b) and (3c) naturally follow the mechanism that when all
agents bid the same, agents with smaller indices always have a higher
priority.

######  Lemma 1.

In our incentive mechanism, for any round $n\in\\{1,2,3,\ldots,N-1\\}$, the
number of selected agents in the round $n$ is not larger than the number of
selected agents in the round $n+1$.

###### Proof.

If this theorem does not hold, then there must exists a
$n^{\prime}\in\\{1,2,\ldots,N\\}$, where the number of selected agents at
round $n^{\prime}$, $K_{n^{\prime}}$, is larger than the number of selected
agents at round $n+1$, denoted as $K_{n^{\prime}+1}$. That means there must be
at least one agent who is selected in round $n^{\prime}$ but not selected in
round $n^{\prime}+1$. Because in each round $n^{\prime}$ we select
$K_{n^{\prime}}=\frac{B-B_{used}}{N-n^{\prime}+1}$ agents. If we denote the
budget left in round $n^{\prime}$ as $B_{n^{\prime}}$, and the reward for each
selected agents in round $n^{\prime}$ and $n^{\prime}+1$ as
$T_{n^{\prime}},T_{n^{\prime}+1}$, this situation can be described as

$\displaystyle\dfrac{B_{n^{\prime}}}{N-n^{\prime}+1}\geq
K_{n^{\prime}}T_{n^{\prime}},$
$\displaystyle\dfrac{B_{n^{\prime}}-K_{n^{\prime}}T_{n^{\prime}}}{N-(n^{\prime}+1)+1}<K_{n^{\prime}+1}T_{n^{\prime}+1}$
$\displaystyle K_{n^{\prime}}>K_{n^{\prime}+1},$ $\displaystyle
T_{n^{\prime}}\geq T_{n^{\prime}+1}$

Expand the inequalities we have

$B_{n^{\prime}}\geq
K_{n^{\prime}}(N-n^{\prime}+1)T_{n^{\prime}},B_{n^{\prime}}<K_{n^{\prime}}(N-n^{\prime}+1)T_{n^{\prime}}$

which leads to a contradiction. Therefore the lemma holds. ∎

With this lemma, we prove that the honest strategy $s$ is a PCE by splitting
the problem into 3 cases.

Case 1. $B\leq NT^{*}$: For the first agent, if she/he bids honestly
throughout the game, then the best response of other agents will have no
effect on the her/his total reward $\lfloor B/T^{*}\rfloor T^{*}$. Otherwise,
if she/he bids $T_{1,1}>T^{*}$ in the first round, then the Nash Equilibrium
for the remaining $m-1$ agents is that all agents bid honestly as $T^{*}$. If
the first agent bids $T^{*}$, but increase her/his bid in the round $n>1$,
then the mechanism will use her/his previous bid $T^{*}$ as her/his reward and
she/he would accept the reward to finish the task according to our assumption.
In this case, the total reward is still $\lfloor B/T^{*}\rfloor T^{*}$.
Therefore, we have $U^{*}_{1}=\max(0,\lfloor B/T^{*}\rfloor T^{*})=\lfloor
B/T^{*}\rfloor T^{*}$ . The reward of agent 1 is upper bounded by the reward
gained adopting the honest strategy $U_{1}(s)=\lfloor B/T^{*}\rfloor T^{*}$.
Therefore, we have $U_{1}(s)=U^{*}_{1}$. For the other agents
$i\in[M]\backslash\\{1\\}$ and any strategy $s_{2}$, the Nash Equilibrium is
still that all these agents bid honestly as $T^{*}$. In this case, the first
agent receives $\lfloor B/T^{*}\rfloor T^{*}$ and other agents receive $0$. As
$B\leq NT^{*}$, we know that $U_{i}(s)=U^{*}_{i}=0$. Since for any $i$, we
have $U_{i}(s)\geq U^{*}_{i}$, the honest strategy $s$ is a PCE when $B\leq
NT^{*}$.

Case 2. $B\geq MNT^{*}$: In this case, the "truth-telling" strategy for
crowdsoucer is that at least one agent bids in the range of
$T\in[T^{*},B/MN]$. It is obvious that for any agent $i$, her/his total reward
is maximized when she/he bids $B/MT^{*}$ in each round, and collecting a
reward of $B/M$. If she/he ever attempts to bid higher, the Nash Equilibrium
of the other agents will make her/him no gain in this round, and thus in the
whole game. Adopting the honest strategy $s$ where each agent bids $B/MT^{*}$,
we have $U_{i}(s)=U^{*}_{i}=B/M$ for any $i$. Hence, $s$ is a PCE when $B\geq
MNT^{*}$.

Case 3. $iNT^{*}<B<(i+1)NT^{*}~{}~{}\forall i\in\\{1,\cdots,M-1\\}$: This is
the scenario where the budget is enough to select $i$ agents during all $N$
rounds, but not enough to pick up $i+1$ agents during all $N$ rounds.
According to Eq. 3, there is

$\displaystyle U_{1}(s)$ $\displaystyle=\cdots=U_{i}(s)=NT^{*}$ $\displaystyle
U_{i+1}(s)$
$\displaystyle=\Big{\lfloor}\frac{B-\sum_{j=1}^{i}U_{j}(s)}{T^{*}}\Big{\rfloor}T^{*}=\Big{\lfloor}\frac{B-iNT^{*}}{T^{*}}\Big{\rfloor}T^{*}$
$\displaystyle U_{i+2}(s)$ $\displaystyle=\cdots=U_{M}(s)=0$

According to the Lemma 1, there exists a transition round $1\leq n\leq N$ and
we also know that the $i+1$ agent is selected from the
$N-\lfloor\frac{B-iNT^{*}}{T^{*}}\rfloor+1$ round.

For any agent $j<i+1$, if she/he sticks to the honest strategy $s_{j}=s$, then
$U_{j}(s_{j})=NT^{*}$ no matter what other agents bid. If any of agent $j<i+1$
chooses to give a higher bid, we denote $n$ as the first round where she/he
does so. If $n>1$ then the outcome does not change. But if $n=1$, i.e., she/he
bids $T_{j,1}>T^{*}$ from the first round, then the agent $i+1$’s best
response is to bid $T_{i+1,1}=T^{*}$. When agent $i+1$ takes the best response
to bid $T^{*}$, according to the Lemma 1, she/he will receive an extra reward
of $T^{*}$. Therefore the upper bound of the reward for agent $j$ is $NT^{*}$.
Hence $U_{j}(s)=U^{*}_{j}=NT^{*}$.

For agent $i+1$, similarly, if she/he bids higher than $T^{*}$ from the round
$N-\lfloor\frac{B-iNT^{*}}{T^{*}}\rfloor+1$, then the best response of any
agent $j>i+1$, is to bid $T^{*}$ to get extra reward. Therefore we have
$U_{i}(s)=U^{*}_{i}=\lfloor\frac{B-iNT^{*}}{T^{*}}\rfloor T^{*}$.

For any agent $j>i+1$, the best strategy of any agent $j^{\prime}\leq i+1$ is
to bid honestly as $T^{*}$. Therefore, $U^{*}_{j}=0$. Then we have

$\displaystyle\begin{cases}U_{j}(s)\geq U^{*}_{j}=NT^{*}~{}~{}~{}&\text{if
}j<i+1\\\ U_{j}(s)\geq
U^{*}_{j}=\Big{\lfloor}\frac{B-iNT^{*}}{T^{*}}\Big{\rfloor}T^{*}~{}~{}~{}&\text{if
}j=i+1\\\ U_{j}(s)\geq U^{*}_{j}=0~{}~{}~{}&\text{if }j>i+1\end{cases}$

In summary, the honest strategy is a PCE in all three cases.

If the real threshold $T^{*}$ satisfies $T^{*}\geq B/NM$, at most $\lfloor
B/T^{*}\rfloor$ agents can be actuated in the game. If each agent bids $T^{*}$
honestly, based on the mechanism, the payment for each agent in each round
will stay at $T^{*}$. By the end of the game, according to the mechanism all
budget would have been spent to actuate as many agents as possible. Therefore
the objective for the crowdsourcer is achieved. If the real threshold
$T^{*}<B/NM$, the budget is large enough to pay each agent in every round, as
long as all agents bid the same value between $T^{*}$ and $B/NM$ inclusively.
The number of agents selected in one round, denoted as $K$, is equal to $M$,
and the total number of agents actuated is $NM$.

##  Appendix B Proof of Theorem 2

Given two selected agents $i,j\in[M]$ and an $1$-round game, without the loss
of generality, we assume $T_{i}^{*}<T_{j}^{*}$ holds. Suppose that there
exists an optimal incentive mechanism: the mechanism should optimize the
utilization of the budget to ensure $\beta=0$ in any setup of $B$ and real
thresholds. that is, the mechanism should always pay real threshold to each
agent when budget is not enough to support all agents in all rounds.

We divide all incentive mechanisms into two categories: 1) fair incentive
mechanism and 2) unfair incentive mechanism. A mechanism is fair if any agents
$i,j\in[M]$ bid the same $T_{i}=T_{j}$, agents $i$ and $j$ will be selected
with equal probability, which doesn’t hold for the unfair case.

If the above optimal mechanism is fair, then the utility of agent $i$ by
taking strategy $s^{\prime}$ of bidding as $T_{j}^{*}$ will be

$\displaystyle U_{i}(s^{\prime})=U_{j}(s)=T_{j}^{*}>T_{i}^{*}.$

If the above optimal mechanism is unfair, since the real threshold is unknown,
without the loss of generality, if agent $i$ has a higher priority than agent
$j$, then the utility of agent $i$ by bidding $T_{j}$ is

$\displaystyle U_{i}(s^{\prime})=T_{j}^{*}>T_{i}^{*}.$

However, according to PCE condition, we have $U_{i}(s)=T_{i}^{*}\geq
U_{i}(s^{\prime})=T_{j}^{*}$ which leads to a contradiction.

##  Appendix C Proof of Theorem 3

Case 1. $B/N\leq T_{2}^{*}$: In this case, since the budget can afford at most
$2$ agents. The budget can afford agent $1$ for all rounds, or agent $2$ for
several rounds. We assume $T_{1}^{*}<T_{2}^{*}$ and agent $1$ comes with a
higher priority $P_{1}>P_{2}$. Since $B/N\leq T_{2}^{*}$, there must exist a
strategy for agent $1$ to obtain full reward $B$, which is also the best
strategy for agent $1$.

######  Lemma 2.

When $B/T_{2}^{*}>\lfloor B/T_{2}^{*}\rfloor$, the agent $1$ needs to take at
least $\lceil B/T_{2}^{*}\rceil$ tasks to get the full reward $B$.

###### Proof.

Assume agent $1$ can get reward $B$ by taking number of tasks $k_{1}<\lceil
B/T_{2}^{*}\rceil$, equivalently $k_{1}\leq\lfloor B/T_{2}^{*}\rfloor$, the
average reward for each round would be $B/k_{1}\geq B/\lfloor
B/T_{2}^{*}\rfloor>T_{2}^{*}$ according to $B/T_{2}^{*}>\lfloor
B/T_{2}^{*}\rfloor$. This means that the average reward exceeds $T_{2}^{*}$,
then there must exist some rounds that agent $2$ can bid $T_{2}^{*}$ to get
some reward such that agent $1$ can not get the full reward $B$, which leads
to a contradiction. ∎

When $B/T_{2}^{*}=\lfloor B/T_{2}^{*}\rfloor=\lceil B/T_{2}^{*}\rceil$, the
best strategy for agent $1$ would be to bid $T_{2}^{*}$ every time to get full
reward $B$, which needs to take $\lceil B/T_{2}^{*}\rceil$ tasks. Therefore,
given the Lemma 2 and above statement, we know that for the upper bound for
regret is $\alpha^{*}-\lceil B/T_{2}^{*}\rceil$.

Case 2. $iT_{i+1}^{*}<B/N\leq(i+1)T_{i+1}^{*}$: In this case, budget $B$ can
support the first $i$ agents for $N$ rounds with bidding $T_{i+1}^{*}$ but not
enough to support the first $i+1$ agents. For the first $i$ agents, this
scenario is the same as the homogeneous threshold case 3:
$iNT^{*}<B<(i+1)NT^{*}$. Therefore, at least $iN$ accepted tasks can be
obtained. Meanwhile, since we have $B/N>iT_{i+1}^{*}$, there are budget left
for the agent $i+1$ in some rounds. Based on our mechanism, the best strategy
for agent $i+1$ would be to bid $T_{i+1}^{*}$. Therefore, in this cases, we
can finally achieve the upper bound for regret
$\alpha^{*}-iN-\Big{\lfloor}\frac{B-iNT_{i+1}^{*}}{T_{i+1}^{*}}\Big{\rfloor}$.

Case 3. $iT_{i}^{*}<B/N\leq iT_{i+1}^{*}$: In this case, the budget can
support the first $i$ agents for $N$ rounds with bids $T_{i}^{*}$, but not
enough to support all agents for bidding $T_{i+1}^{*}$. Therefore, in this
case, there is no chance for agent $i+1$ to get any reward if the first $i$
agents achieve a PCE. This case is equivalent to the homogeneous threshold
case 2: $B>iNT^{*}$ where $T=T_{i}^{*}$. Based on the proof in Appendix A, the
PCE would be that all of first $i$ agents bid $B/iN$. Thus, each one will
obtain the reward of $B/i$ and finish $N$ tasks. The upper bound for regret
would be $\alpha^{*}-iN$.

Case 4. $B/N>MT_{M}^{*}$: This case is the same as the homogeneous threshold
case: $B>MNT^{*}$ where $T^{*}=T_{M}^{*}$. Based on the proof shown in
Appendix A, the upper bound for regret would be $\alpha^{*}-MN$.

## References

  * Angelopoulos et al., (2014) Angelopoulos, C. M., Nikoletseas, S., Raptis, T. P., and Rolim, J. D. (2014).  Characteristic utilities, join policies and efficient incentives in mobile crowdsensing systems.  In Wireless Days (WD), pages 1–6. IEEE.
  * Devarakonda et al., (2013) Devarakonda, S., Sevusu, P., Liu, H., Liu, R., Iftode, L., and Nath, B. (2013).  Real-time air quality monitoring through mobile sensing in metropolitan areas.  In Proceedings of the 2nd ACM SIGKDD international workshop on urban computing, page 15. ACM.
  * Duan et al., (2012) Duan, L., Kubo, T., Sugiyama, K., Huang, J., Hasegawa, T., and Walrand, J. (2012).  Incentive mechanisms for smartphone collaboration in data acquisition and distributed computing.  In INFOCOM, pages 1701–1709. IEEE.
  * Dutta et al., (2009) Dutta, P., Aoki, P. M., Kumar, N., Mainwaring, A., Myers, C., Willett, W., and Woodruff, A. (2009).  Common sense: participatory urban sensing using a network of handheld air quality monitors.  In Proceedings of the 7th ACM conference on embedded networked sensor systems, pages 349–350. ACM.
  * Eisenman et al., (2009) Eisenman, S. B., Miluzzo, E., Lane, N. D., Peterson, R. A., Ahn, G.-S., and Campbell, A. T. (2009).  Bikenet: A mobile sensing system for cyclist experience mapping.  ACM Transactions on Sensor Networks (TOSN), 6(1):6.
  * Ganti et al., (2011) Ganti, R. K., Ye, F., and Lei, H. (2011).  Mobile crowdsensing: current state and future challenges.  IEEE Communications Magazine, 49(11).
  * Gneiting and Raftery, (2007) Gneiting, T. and Raftery, A. E. (2007).  Strictly proper scoring rules, prediction, and estimation.  Journal of the American Statistical Association, 102(477):359–378.
  * Hasenfratz et al., (2015) Hasenfratz, D., Saukh, O., Walser, C., Hueglin, C., Fierz, M., Arn, T., Beutel, J., and Thiele, L. (2015).  Deriving high-resolution urban air pollution maps using mobile sensor nodes.  Pervasive and Mobile Computing, 16:268–285.
  * Hull et al., (2006) Hull, B., Bychkovsky, V., Zhang, Y., Chen, K., Goraczko, M., Miu, A., Shih, E., Balakrishnan, H., and Madden, S. (2006).  Cartel: a distributed mobile sensor computing system.  In Proceedings of the 4th international conference on Embedded networked sensor systems, pages 125–138. ACM.
  * Ji and Chen, (2017) Ji, S. and Chen, T. (2017).  On designing collusion-resistant incentive mechanisms for mobile crowdsensing systems.  In Trustcom/BigDataSE/ICESS, 2017 IEEE, pages 162–169. IEEE.
  * Jin et al., (2017) Jin, H., Su, L., and Nahrstedt, K. (2017).  Theseus: Incentivizing truth discovery in mobile crowd sensing systems.  arXiv preprint arXiv:1705.04387.
  * Kamble et al., (2015) Kamble, V., Marn, D., Shah, N., Parekh, A., and Ramachandran, K. (2015).  Truth serums for massively crowdsourced evaluation tasks.  arXiv preprint arXiv:1507.07045.
  * Lambert and Shoham, (2009) Lambert, N. and Shoham, Y. (2009).  Eliciting truthful answers to multiple-choice questions.  In Proceedings of the 10th ACM conference on Electronic commerce, pages 109–118. ACM.
  * Lane et al., (2010) Lane, N. D., Miluzzo, E., Lu, H., Peebles, D., Choudhury, T., and Campbell, A. T. (2010).  A survey of mobile phone sensing.  IEEE Communications magazine, 48(9).
  * Nie et al., (2017) Nie, X., Tian, X., Taylor, J., and Zou, J. (2017).  Why adaptively collected data have negative bias and how to correct for it.  arXiv preprint arXiv:1708.01977.
  * Prelec, (2004) Prelec, D. (2004).  A bayesian truth serum for subjective data.  science, 306(5695):462–466.
  * Rong and Halpern, (2014) Rong, N. and Halpern, J. Y. (2014).  Cooperative equilibrium: A solution predicting cooperative play.  arXiv preprint arXiv:1412.6722.
  * (18) Shah, N. B. and Zhou, D. (2016a).  Double or nothing: Multiplicative incentive mechanisms for crowdsourcing.  Journal of Machine Learning Research, 17:1–52.
  * (19) Shah, N. B. and Zhou, D. (2016b).  No oops, you won’t do it again: mechanisms for self-correction in crowdsourcing.  In International Conference on Machine Learning.
  * Shah et al., (2015) Shah, N. B., Zhou, D., and Peres, Y. (2015).  Approval voting and incentives in crowdsourcing.  In International Conference on Machine Learning.
  * Thiagarajan et al., (2009) Thiagarajan, A., Ravindranath, L., LaCurts, K., Madden, S., Balakrishnan, H., Toledo, S., and Eriksson, J. (2009).  Vtrack: accurate, energy-aware road traffic delay estimation using mobile phones.  In Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems, pages 85–98. ACM.
  * Wan et al., (2016) Wan, J., Liu, J., Shao, Z., Vasilakos, A. V., Imran, M., and Zhou, K. (2016).  Mobile crowd sensing for traffic prediction in internet of vehicles.  Sensors, 16(1):88.
  * Wang and Shah, (2018) Wang, J. and Shah, N. B. (2018).  Your 2 is my 1, your 3 is my 9: Handling arbitrary miscalibrations in ratings.  arXiv preprint arXiv:1806.05085.
  * Wang et al., (2013) Wang, X. O., Cheng, W., Mohapatra, P., and Abdelzaher, T. (2013).  Artsense: Anonymous reputation and trust in participatory sensing.  In INFOCOM, 2013 Proceedings IEEE, pages 2517–2525. IEEE.
  * Wang et al., (2014) Wang, X. O., Cheng, W., Mohapatra, P., and Abdelzaher, T. (2014).  Enabling reputation and trust in privacy-preserving mobile sensing.  IEEE Transactions on Mobile Computing, 13(12):2777–2790.
  * Yang et al., (2012) Yang, D., Xue, G., Fang, X., and Tang, J. (2012).  Crowdsourcing to smartphones: Incentive mechanism design for mobile phone sensing.  In Proceedings of the 18th annual international conference on Mobile computing and networking, pages 173–184. ACM.
  * Zhang et al., (2016) Zhang, X., Yang, Z., Sun, W., Liu, Y., Tang, S., Xing, K., and Mao, X. (2016).  Incentives for mobile crowd sensing: A survey.  IEEE Communications Surveys & Tutorials, 18(1):54–67.
  * Zhao et al., (2014) Zhao, D., Li, X.-Y., and Ma, H. (2014).  How to crowdsource tasks truthfully without sacrificing utility: Online incentive mechanisms with budget constraint.  In INFOCOM, pages 1213–1221. IEEE.
  * Zheng et al., (2013) Zheng, Y., Liu, F., and Hsieh, H.-P. (2013).  U-air: When urban air quality inference meets big data.  In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1436–1444. ACM.
  * Zheng et al., (2017) Zheng, Z., Wu, F., Gao, X., Zhu, H., Tang, S., and Chen, G. (2017).  A budget feasible incentive mechanism for weighted coverage maximization in mobile crowdsensing.  IEEE Transactions on Mobile Computing, 16(9):2392–2407.