# Linear Delta Arrays for Compliant Dexterous Distributed Manipulation

Sarvesh Patil, Tony Tao, Tess Hellebrekers, Oliver Kroemer, F. Zeynep Temel

S. Patil, T. Tao, O. Kroemer, and F. Z. Temel are with the Robotics Institute,
Carnegie Mellon University, Pittsburgh, PA 15213, USA {sarveshp, longtao,
okroemer, ztemel} @andrew.cmu.eduTess Hellebrekers is with Meta AI
<EMAIL_ADDRESS>https://iamlab-cmu.github.io/delta-arrays/

###### Abstract

This paper presents a new type of distributed dexterous manipulator: delta
arrays. Our delta array setup consists of 64 linearly-actuated delta robots
with 3D-printed compliant linkages. Through the design of the individual delta
robots, the modular array structure, and distributed communication and
control, we study a wide range of in-plane and out-of-plane manipulations, as
well as prehensile manipulations among subsets of neighboring delta robots. We
also demonstrate dexterous manipulation capabilities of the delta array using
reinforcement learning while leveraging compliance. Our evaluations show that
the resulting 192 DoF compliant robot is capable of performing various
coordinated distributed manipulations of a variety of objects, including
translation, alignment, prehensile squeezing, lifting, and grasping.

###### Index Terms:

Multi-Robot Systems, Soft Robot Applications, Dexterous Manipulation

##  I Introduction

The term _dexterous manipulation_ often invokes the image of a five-fingered
hand delicately holding an object as a human would. However, robots are not
restricted to human morphology. Imagine instead a surface covered in fingers.
Each finger can move its fingertip in a small 3D workspace above its fixed
base and interact with parts of objects that enter its workspace. The fingers
can work together to shift, tilt, lift, block, and even pinch objects. The
large number of fingers provides additional redundancy, with larger objects
being manipulated by tens of fingers at a time. The distributed nature of the
fingers also means that multiple objects can be easily manipulated in parallel
in different regions of the surface. This type of system would thus represent
a distributed dexterous manipulation paradigm.

In this paper, we present an array of linear delta robots for the development
of distributed dexterous manipulation strategies. Delta arrays consist of
grids of small prismatic soft delta robots (3 degrees-of-freedom (DoF) each)
that work together to manipulate objects. We propose a modular design for the
delta arrays that consist of $2\times 2$ units (12 DoF each) with each unit
having a standalone mechanical and electronic design. Each unit has its own
processor and controllers, allowing for distributed computation with a central
computer providing high-level commands. We also present a real hardware
implementation of an $8\times 8$ array consisting of $16$ units and providing
$192$ degrees of freedom.

Figure 1: Delta array dexterous manipulation setup with robots facing down.
(a) The setup consists of 64 delta robots actuated by linear motors and a
camera. (b) Checkered board on the object used for pose estimation. (c)
Distributed manipulation strategy for tilting wooden block.

Each compliant delta robot in the array is actuated by three linear actuators.
These actuators are connected via parallel mechanisms to an end-effector
platform. The platform and parallel linkages are 3D printed together out of
thermoplastic polyurethane (TPU - 95A shore hardness) for easier assembly,
compliant interactions, and low hysteresis under extreme deformations. The
linear-actuator design allows for the delta robots to be packed closely
together, in a hexagonal grid, and for their end-effectors to move outside of
the footprint of the actuators. This allows the workspaces of neighboring
deltas to overlap, and perform prehensile manipulations such as pinching
between neighboring delta robots.

We present two modes of operating the delta array:

  * •

Facing Down - Objects are placed on a plexiglass plane and manipulated from
the top with a camera underneath the array for visual feedback (Fig. 1).

  * •

Facing Up - Objects are placed on top of the array and manipulated from
underneath or on the sides (Fig. 5).

The delta array provides a basis for a wide range of different manipulation
strategies. Similar to smart conveyors, delta arrays are capable of executing
various planar transportation behaviors. Unlike smart conveyors, delta arrays
need to use a finger gaiting approach, with coordinated making and breaking of
contacts across delta robots, to shift objects across the array’s workspace.
This added complexity, however, means delta arrays can make better contact
with objects that have non-planar surfaces. The additional flexibility and
non-planar motions of the deltas also allow for a number of other strategies
that require out-of-plane motions in 3D workspaces. These strategies contrast
with traditional manipulators in the sense that the end-effectors are static
as opposed to being mounted on a robotic arm, and rely more on cooperation
between multiple agents to accomplish tasks.

In the facing-up mode, the variable height allows for the rolling and tilting
of objects on the array surface. Fingers can be raised to create fixture-like
structures for aligning objects. The lateral motions allow the deltas to grasp
and pinch objects of various sizes across the array. Although many of these
strategies have been individually supported by other distributed or dexterous
manipulation systems, to the best of our knowledge, this is the first system
that supports all of these strategies and thus the possibility of combining
strategies, as well as learning new ones.

Figure 2: The modular design of the delta array. Each robot consists of three
linear actuators and a 3D printed TPU end effector (left). Four robots
organized in a $2\times 2$ hexagonal grid form a module, which shares the
electrical components (middle). 16 modules form the delta array (right).

Implementing and controlling an array of delta robots presents a number of
challenges. The design needs to be modular for easy construction, extension,
and maintenance. The individual delta robots need to be robust and safe, but
also precise and capable of supporting a wide range of manipulation
strategies. The communication needs to be fast and scalable to minimize
command latency throughout the array network. In the remainder of this paper,
we will explain and discuss our design decisions in developing the delta
arrays and how we tackle each of these systemic requirements. Sections II,
III, and IV describe the modular arrays in a bottom-up manner, while sections
V, and VI present basic control strategies for manipulating objects with the
arrays. The focus of this paper is on the design of the delta arrays and
demonstrating its ability to execute a variety of distributed dexterous
manipulation strategies. Developing more advanced and hybrid strategies is
left to future work.

##  II Related Work

###  II-A Delta robots

Delta robots were introduced by Clavel in 1990 and initially designed as a
pick-and-place tool [1]. Conventional delta robots have a fixed base and a
moving stage that are always parallel to each other. These platforms are
connected by three kinematic chains with revolute and universal joints. These
chains are each driven by single-DoF actuators that are positioned at the
fixed base. The motion is transmitted from the base arm to the moving stage by
three parallelograms, which are the key to the delta robot’s functionality
[2]. In our recent work [3], we presented a gripper based on two prismatic
delta manipulators using 3D-printed parallelogram links presented in [4].
Unlike traditional parallel jaw grippers, our robots have compliant end-
effectors, which makes them modular and accessible. This 6-DoF system is able
to perform dexterous manipulation tasks, such as aligning a pile of coins,
picking up a card from a deck, plucking a grape off of a stem, and rolling
dough.

###  II-B Robot hand and finger design for dexterous manipulation

Current robot hands with fingers span a range of different designs and
complexity. Basic two-fingered grippers often have a single DoF, while complex
anthropomorphic hands will often have multiple DoF per finger [5, 6]. Current
designs use serial mechanisms for the individual fingers, similar to human
hands. However, the more dexterous designs either require relatively bulky
motors to be placed in the fingers, where they significantly increase the
inertia, or they are actuated by cable drives [7], which are subject to highly
non-linear effects and temporal variations due to slack and friction along the
cables.

###  II-C Dynamic surfaces

Dynamic surfaces have the potential to be used not only for object
manipulation, but also as shape-changing interfaces. Distributed manipulation
systems have many types, such as vibrating plates [8], actively controlled
arrays of air jets [9], planar micromechanical actuator arrays [10], and
actuated workbenches using magnetic forces [11]. These dynamic surfaces with
an actuator array are also widely used in interactive displays. However, prior
works focus on the motion on a plane, rather than working on the motion in 3D
space. An additional DoF on the normal surface allows the delta array to
interact with objects while utilizing contacts in 3D space.

###  II-D Distributed and dexterous manipulation primitives

Dexterous manipulation using soft grippers is a challenging task due to
stochasticity in the kinematics of the soft robot bodies. Various robust
model-based control strategies use Lagrangian formulations to model the system
[12][13]. Another way is to use human demonstrations and Dynamic Motion
Primitives (DMPs) to generate dynamically constrained trajectories for
manipulation [14][15][16]. However, using analytical methods for a multi-agent
system can lead to excessively high demand in compute, and generating human
demonstrations for such a high degree of freedom system is logistically
infeasible. Thus, we deploy a model-free RL algorithm directly on the hardware
to generate trajectories for pushing and tilting an object against other
robots to demonstrate the dexterous manipulation capabilities of the delta
arrays.

##  III Prismatic Delta Robots

A delta array consists of multiple delta robots arranged in a planar grid
structure. In this section, we explain the design of the individual delta
robots. Each delta robot consists of three actuators connected by a parallel-
bar linkage end-effector platform, as shown in Fig.2.

###  III-A Actuators

Delta robots are often designed with rotational actuators that provide torque
to individual links [2, 17]. These designs provide rapid and precise movements
at the end-effector, but at the cost of a wide robot base. Due to the
excessive width, which would conflict with the goal of creating a closely
packed array of delta robots, we utilize linear actuators that enable us to
position each robot in close proximity to one another. The linear actuators
(Actuonix) have a $10$ cm stroke length and internal potentiometers to provide
analog feedback for position control. The end effector design is based on our
previous work [3].

Figure 3: (a) Cross-section view of the fingertip assembly in CAD (b) Cross-
section view of 3D printed fingertip shows air pocket created by $0\%$ infill
(c) Attachment clip latches into underside of link using catch on end of the 3
prongs.

###  III-B End Effector and Parallelogram Linkages

The end-effector platform is connected to three actuators through a
parallelogram link, which converts linear motions into precise 3D x-y-z
motions at the end-effector while keeping the platform parallel to the base.

The delta links are 3D printed as a single part with living hinges. Additional
details can be found at [4]. The delta links were printed using thermoplastic
polyurethane (TPU) for its low Young’s modulus. This compliance allows the
robots to safely interact with objects, other robots, and reduce the wear and
tear of the system.

To perform dexterous manipulation, we design a fingertip that is inspired by
the texture and feel of a human finger. The fingertip is attached as an end-
effector to the delta platform using a reusable clip printed using durable
formv3 resin for strength and flexibility. The fingertips were 3D printed
using Polylactic acid (PLA) for the inner bone structure and NinjaFlex 85A for
the outer skin which was fused together using a dual extrusion printer. Fig. 3
shows the cross-sectional structure of the design.We achieve this hollow
structure by using $0\%$ infill for the NinjaFlex and thin, two-layer walls
which results in an enclosed cavity that provides the surface compliance for
the finger.

###  III-C Delta Robot Workspace

A key benefit of the prismatic delta design is that the workspace of the
delta’s end-effector extends beyond the triangular footprint of the three
actuators. For our implementation, the horizontal distance between the centers
of two actuators in a delta robot is 2cm, while the width of the workspace is
approximately 6cm. To avoid excessive collisions between neighboring deltas,
we restrict the horizontal workspace to a diameter of 3cm. The vertical
workspace corresponds to the 10cm stroke length of the actuators.

The delta robots are operated within a workspace that is far away from their
singularities. Ambiguities in the inverse kinematics can therefore be easily
resolved to determine a suitable joint trajectory for a given desired end-
effector trajectory.

##  IV Modular Array Structure

Sets of delta robots are arranged into hexagonal grids to create delta arrays.
Rather than constructing an array out of single deltas, we instead developed a
modular $2\times 2$ array unit for four deltas. Each unit can be operated in a
standalone manner and provides a shared set of electronics and
microcontrollers. To create an $8\times 8$ array, we simply place 16 of the
modules in a $4\times 4$ macro grid, and a central computer then communicates
to all of the modules to create coordinated manipulation strategies. The
$2\times 2$ modules thus provide a modular and extendable basis for easily
constructing arrays of different sizes and replacing parts as needed. Our
$8\times 8$ configuration allows the manipulation of objects of a range of
sizes and demonstrates the potential of such arrays in dexterous tasks.

###  IV-A $2\times 2$ Delta Modules

Each $2\times 2$ module employs a hexagonal structure as shown in the middle
image of Fig.2. The linear actuator bodies are held together using two laser-
cut plexiglass plates, which are, in turn, supported by aluminum stand-offs.
The stand-off configuration equally compresses the $12$ linear actuators from
both sides forming a stable structure.

Each robot in the module is then secured through the base of the linear
actuators using a 3D-printed connector made from PLA and then attached to a
3D-printed enclosure made of PLA. This hardware box houses the electronics
needed to control the four deltas in that module and allows the module to be
connected with a base plate that supports the array. The resulting $2\times 2$
delta modules offer a balance between modularity and ease of maintenance.

For the face-down mode of operation, the setup is inverted and mounted onto
pillars made of 80/20 aluminum extrusions—constrained at the top by the base
plate and on the bottom by an optical breadboard. Between the array and the
breadboard, a clear plexiglass platform is supported by a movable linear slide
on each corner. Planar manipulations are performed ontop of this platform.
These sliders allow the height of the platform to be manually adjusted
depending on the size of the objects being manipulated. The transparent
platform enables our vision pipeline to track the pose of objects from below
as they are manipulated.

###  IV-B Electronics

Figure 4: Communication flowchart for a $2\times 2$ module. The control of
three actuators of each robot in a four-robot module is accomplished by three
motor drivers. Colored arrows show the distributed control framework between
drivers, actuators, and ADCs.

Adafruit Feather M0 boards control four deltas ($12$ actuators) in a module
and they are housed in the hardware enclosure box. Adafruit DC Motor/Stepper
FeatherWing is used to control the velocity of the end effectors through PWM
signals. We use an analog-to-digital converter (ADC) to couple the position
feedback from the linear actuators. This also acts as a low-pass filter to
eliminate high-frequency noise from the electromagnetic interference generated
in the circuit for precise position control. We use a 12-bit ADC that resolves
the 100 mm length, and we apply a low level PID control with a final precision
of upto $0.3$ mm.

We use the $I^{2}C$ bus on the Feather M0 and distribute the data bus, clock,
and a 12W power supply across three FeatherWing motor drivers using a custom
electronic shield circuit. The compactness of the design allows us to maintain
close proximity among all the delta modules.

For perception, we mount a USB camera module on the bottom plane looking
upwards. The camera tracks object poses with minimal occlusions while
dexterous manipulation is being performed by the delta array from above.

###  IV-C Communication Across the Array

To efficiently control the entire array of 64 robots, communication factors
like latency, noise, and amplitude of signal need to have stable optimal
values. Instead of using TTL communication using wires, which results in
exhaustive cable management and noise, we use off-the-shelf ESP-01 WiFi
modules operating at 115,200 baud rate, enabling low latency, low noise, and
speedy wireless communication. A high-level flowchart of communication is
shown in (Fig. 4). We use protocol buffers (protobuf) to transmit control data
because of their high compressibility and effectiveness in networked
communications as shown in [18].

Figure 5: Top-view and side-view representation of the ellipsoid trajectories
of the two-beat gaits. (a) represents 2 odd rows from the array for execution
of the Dexterous Gripping Primitive and (c) represents the entire delta array
executing the Planar Rotation Primitive. Both follow two-beat gait patterns
shown in (b) and (d) respectively

##  V Predefined Distributed Manipulation Strategies

The $8\times 8$ array in ”facing-up” mode can execute a variety of dexterous
manipulation strategies distributed across its delta robots. These strategies
include planar manipulations like translation, rotation, and convergence, as
well as out-of-plane and prehensile manipulations. To test the capabilities of
the delta array, we implemented a series of basic manipulation policies. Each
delta robot is given $(x,y)$ coordinates representing its position $\vec{p}$.
For every primitive, we use simple linear algebraic operations to determine
the position-controlled trajectories of the delta robots.

The delta array policies are designed as two-beat finger-gaiting strategies
that repeatedly cause the deltas to make and break contact with the objects
being manipulated. The planar trajectory moves in the vertical direction, with
a constant gait, and along a horizontal direction as given by a high-level
primitive. The movements can be considered as going from $[-\vec{p},z_{min}]$
to $[\vec{p},z_{max}]$ as shown in Fig.5A, where $z_{min}=7cm$ and
$z_{max}=10cm$ are the alternating end-effector positions on $Z-axis$. The
two-beat gait means that half of the deltas in the array will be in an up
configuration while the other half are in a down configuration, i.e., $180$
degrees out of phase. We use a two-beat gait to maximize the number of deltas
in contact with the object at a given time as described in [19].

###  V-A Dexterous Gripping Primitive

Apart from purely planar manipulation strategies, we present a _grip-and-push_
primitive that can be deployed to grasp objects within a line of delta robots
and push the object forward or backward along the line. We use a two-beat
finger gait with a constant $Z$ value, and periodically switching $Y_{max}$
and $Y_{min}$ to push objects along the $X-axis$. A demonstration of the
strategy on a foam bell pepper is shown in Fig.5[(a), (b)] and Fig. 6A.

###  V-B Planar Translation Primitive

For planar translations, a straightforward implementation of up, down, left,
and right movements can be shown by placing a point along the $X$ and $Y$ axes
at infinity, computing the unit distance vector from the center of the robot
to that point and plug the unit vector in the aforementioned two-beat finger-
gaiting pattern for planar translation of objects on the surface of the linear
delta arrays.

Figure 6: The rows of images demonstrate manipulations of different objects
using the $8\times 8$ delta array. The numbers beneath each row indicate the
timestamp. (A) A toy bell pepper object that weighs $4g$ with a characteristic
length of $60mm$ is transported from one edge of the array to the other using
a dexterous gripping primitive from (a) to (e). (B)A box object is rotated
while the position on the array stayed the same as shown from (f) to (j).

###  V-C Planar Rotation Primitive

For planar rotation, the distance vector from each robot to the center is
multiplied by the rotation matrix to generate rotating unit vectors for planar
rotation as shown in Fig.5[(c), (d)] and Fig.6B.

###  V-D Wall Primitive

A unique feature of linear delta arrays is the ability to use a subset of
delta robots to form walls of various shapes for restricting the movements of
objects. Dexterous tasks like clamping or aligning an object along the wall
and turning it around for inspection can be performed using simple yet
effective policies, an inverted version of which we present in the next
section.

Figure 7: Using the delta robots for tilting an object using learned
trajectories

##  VI Learning Dexterous Manipulation Strategies

The array can also be used to learn basic dexterous manipulation skills. We
design an RL environment on the real hardware with the delta array in the
facing-down mode 7. From the robot’s camera, we track the SE(3) pose of a
checkerboard pattern attached to a wooden block that the robot should
manipulate using the neighboring 6 delta robots. The pose of the object is
tracked to generate the reward for performing the task. We compute the L2
error between the current pose and desired pose and compare it with a
threshold of 0.1 cm for translation and 0.5 rad for rotation. We use the
following formula to compute the reward to maximize:

$\displaystyle f(x)=\begin{cases}-1*T_{e}-3*R_{e},&\text{if }T_{e}>0.1\lor
R_{e}>0.5\\\ +10,&\text{otherwise}\end{cases}$ (1)

Where $T_{e}$ is the translational error and $R_{e}$ is the rotational error.

The errors generated by the vision system are used to train fingertip
trajectories for grasping and tilting the wooden block using episodic relative
entropy policy search (eREPS) [20]. The trajectories are generated by
weighting the output of eREPS on 5 basis functions of the DMPs. eREPS is a
model-free RL algorithm that iteratively optimizes a Gaussian distribution
over the weights of the DMP. We initialize the distribution with a zero mean
and a diagonal covariance matrix of $0.7$.

In each execution episode, the robot samples the weights of the DMP, generates
and executes the corresponding fingertip trajectory, and computes the
resulting reward. The Gaussian policy is updated every ten episodes. The
algorithm runs until a success rate of at least 90% has been achieved, which
takes approximately 270 epochs.

##  VII Experiments

This section describes the experimental evaluations performed using the delta
array.

###  VII-A Facing-up Manipulation Experiment

We constructed an $8\times 8$ delta array using the design described in
Sections III and IV. We implemented the distributed manipulation strategies
explained in Section V for the upward facing configuration. The robot could
then manipulate objects placed on top of the array. The robot successfully
performed non-prehensile translation and rotation manipulations of objects of
dimensions ranging from $60$mm $\times$ $40$mm $\times$ $20$ mm to $300$mm
$\times$ $300$mm $\times$ $80$mm and weights ranging from $4$g to $1$kg.
Examples of different manipulations are shown in Fig. 6. Each picture
represents a snapshot of the manipulation task being performed. Our methods
work on objects with a stable center of mass and a moderate coefficient of
friction. Objects like soda cans with a shifting center of mass are hard to
manipulate in an open-loop control setting.

Figure 8: Using REPS to generate weights of the basis functions of a DMP to
generate a 2D trajectory (curved lines from (0,0) till end-point predicted by
REPS) for the delta robots. Faint trajectories represent initial exploration
trajectories with low/negative rewards, darker trajectories represent learned
exploitation with high rewards

###  VII-B Facing-down Manipulation Experiment

We implemented the learning of dexterous manipulation strategies in Section VI
for the downward facing configuration. This was done only in the facing-down
configuration due to the ease of resetting the environment as compared to the
upright configuration.The robot could learn to grasp and tilt objects placed
on a planar surface directly in the real world without simulation. The face-
down mode provides a more stable environment for easier resetting of objects
between episodes. Throughout the training, the trajectories generated by the
robot are shown in Fig. 8.

In the initial stages, the algorithm explores the action spaces while
generating very low rewards shown as the faint tinted trajectories in Fig. 8.
As the training progresses, the actions converge to more optimal values and
the model becomes exploitative to generate maximum reward consistently towards
the end of the training as shown by the darker lines in Fig. 8. The learning
approach could be used to generate DMPs for other shapes of objects as well.
Due to the soft linkages, heavy objects with smooth surfaces are hard to lift
using the delta robots.

###  VII-C Discussion

For the upward facing configuration, the results show that the delta arrays
can be used for a variety of manipulation types. In-plane translation and
rotations perform better when applied to larger objects where more delta
robots make contact with the objects at any time. In some cases, smaller
objects can get stuck between deltas in the array, but the compliance keeps
the system safe in these situations. The weight of objects plays an important
role in the performance of the non-prehensile manipulations as well. We found
that heavier objects tended to be manipulated more easily. Part of this may be
due to the correlation in size and higher friction forces between the delta
robots and the object.

The wall policy allows the delta array to successfully align objects against
the side of sets of delta robots. In this manner, the delta array can remove
some of the uncertainty of the object’s position. The wall policy can also be
seen as a hybrid policy that combines the use of the translational policy with
using some fingers as fixtures/obstacles. The delta array thus presents a
suitable base for exploring a variety of mixed manipulation strategies in the
future.

For the downward facing configuration, we observe that the design of the
fingertips played an important role since higher friction generated by the
fingertip surface made objects easier to tilt against the walled fingertips.
The hollow cavity in the fingertips helps the surface to conform to the
surface of the object to make lifting the objects easier. The compliance of
the robots also adds robustness to the policy which makes it slightly more
sample efficient.

##  VIII Conclusion

We proposed delta arrays as a new type of dexterous manipulation robot. We
presented the assembly of individual delta robot modules for close packing and
overlapping workspaces, and we proposed a modular design and distributed
control framework. We constructed and tested an $8\times 8$ array of delta
robots and showed that the delta arrays can be used to perform a variety of
manipulation strategies in two different configurations. For the facing-up
configuration, our current manipulation primitives tend to be better suited
for larger objects, where the redundancy of the array provides robustness.
While for the facing-down configuration, we were able to learn grasping and
tilting strategies directly on the hardware with low-level visual supervision.

To show generalizability across objects, we plan to incorporate vision
feedback to extract object poses and learn grasping strategies to generalize
to objects of various shapes and sizes. We also plan to extend the use of the
delta arrays for deformable object manipulation and to demonstrate the
effectiveness of compliant multi-agent manipulation systems.

##  IX Acknowledgements

The research presented in this work was funded by the National Science
Foundation under project Grant No. CMMI-2024794 and Meta AI Research under
award number RPS6.

## References

  * [1] R. Clavel, “Device for the movement and positioning of an element in space,” Dec. 11 1990, uS Patent 4,976,582.
  * [2] L. Rey and R. Clavel, “The delta parallel robot,” pp. 401–417, 1999.
  * [3] P. Mannam, A. Rudich, K. Zhang, M. Veloso, O. Kroemer, and F. Temel, “A low-cost compliant gripper using cooperative mini-delta robots for dexterous manipulation,” _Robotics: Science and Systems XVII_ , 2021.
  * [4] P. Mannam, O. Kroemer, and F. Z. Temel, “Characterization of Compliant Parallelogram Links for 3D-Printed Delta Manipulators,” in _Experimental Robotics_ , B. Siciliano, C. Laschi, and O. Khatib, Eds. Cham: Springer International Publishing, 2021, vol. 19, pp. 75–84, series Title: Springer Proceedings in Advanced Robotics. [Online]. Available: https://link.springer.com/10.1007/978-3-030-71151-1_7
  * [5] U. Kim, D. Jung, H. Jeong, J. Park, H.-M. Jung, J. Cheong, H. R. Choi, H. Do, and C. Park, “Integrated linkage-driven dexterous anthropomorphic robotic hand,” _Nature Communications_ , vol. 12, no. 1, p. 7177, Dec. 2021. [Online]. Available: https://www.nature.com/articles/s41467-021-27261-0
  * [6] O. M. Andrychowicz, B. Baker, M. Chociej, R. Józefowicz, B. McGrew, J. Pachocki, A. Petron, M. Plappert, G. Powell, A. Ray, J. Schneider, S. Sidor, J. Tobin, P. Welinder, L. Weng, and W. Zaremba, “Learning dexterous in-hand manipulation,” _The International Journal of Robotics Research_ , vol. 39, no. 1, pp. 3–20, 2020. [Online]. Available: https://doi.org/10.1177/0278364919887447
  * [7] O. M. Andrychowicz, B. Baker, M. Chociej, R. Józefowicz, B. McGrew, J. Pachocki, A. Petron, M. Plappert, G. Powell, A. Ray, J. Schneider, S. Sidor, J. Tobin, P. Welinder, L. Weng, and W. Zaremba, “Learning dexterous in-hand manipulation,” _The International Journal of Robotics Research_ , vol. 39, no. 1, pp. 3–20, 2020.
  * [8] K.-F. Bohringer, V. Bhatt, and K. Goldberg, “Sensorless manipulation using transverse vibrations of a plate,” in _Proceedings of 1995 IEEE International Conference on Robotics and Automation_ , vol. 2, 1995, pp. 1989–1996 vol.2.
  * [9] M. Yim, J. Reich, and A. A. Berlin, “Two approaches to distributed manipulation,” in _Distributed Manipulation_. Springer, 2000, pp. 237–261.
  * [10] G. Bourbon, P. Minotti, P. Htlin, and H. Fujita, “Toward smart surfaces using high-density arrays of silicon-based mechanical oscillators,” _Journal of intelligent material systems and structures_ , vol. 10, no. 7, pp. 534–540, 1999.
  * [11] G. Pangaro, D. Maynes-Aminzade, and H. Ishii, “The actuated workbench: Computer-controlled actuation in tabletop tangible interfaces,” in _Proceedings of the 15th Annual ACM Symposium on User Interface Software and Technology_ , ser. UIST ’02. New York, NY, USA: Association for Computing Machinery, 2002, p. 181–190. [Online]. Available: https://doi.org/10.1145/571985.572011
  * [12] A. Kazemipour, O. Fischer, Y. Toshimitsu, K. W. Wong, and R. K. Katzschmann, “A robust adaptive approach to dynamic control of soft continuum manipulators,” _CoRR_ , vol. abs/2109.11388, 2021. [Online]. Available: https://arxiv.org/abs/2109.11388
  * [13] G. Zhang and D. Cheng, “Adaptive fault-tolerant guaranteed performance control for euler-lagrange systems with its application to a 2-link robotic manipulator,” _IEEE Access_ , vol. 8, pp. 184 160–184 171, 2020.
  * [14] J.-P. Saut, A. Sahbani, S. El-Khoury, and V. Perdereau, “Dexterous manipulation planning using probabilistic roadmaps in continuous grasp subspaces,” in _2007 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2007, pp. 2907–2912.
  * [15] R. Jäkel, S. R. Schmidt-Rohr, S. W. Rühl, A. Kasper, Z. Xue, and R. Dillmann, “Learning of Planning Models for Dexterous Manipulation Based on Human Demonstrations,” _International Journal of Social Robotics_ , vol. 4, no. 4, pp. 437–448, Nov. 2012. [Online]. Available: https://doi.org/10.1007/s12369-012-0162-y
  * [16] A. Gupta, C. Eppner, S. Levine, and P. Abbeel, “Learning dexterous manipulation for a soft robotic hand from human demonstrations,” in _2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2016, pp. 3786–3793.
  * [17] Sam Alvares, “Building DeltaZ,” Aug. 2021. [Online]. Available: https://www.youtube.com/watch?v=Mg2i0toDOXg
  * [18] S. Popić, D. Pezer, B. Mrazovac, and N. Teslić, “Performance evaluation of using protocol buffers in the internet of things communication,” in _2016 International Conference on Smart Systems and Technologies (SST)_ , 2016, pp. 261–265.
  * [19] S. Thompson, P. Mannam, Z. Temel, and O. Kroemer, “Towards robust planar translations using delta-manipulator arrays,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 6563–6569.
  * [20] J. Peters, K. Mülling, and Y. Altün, “Relative entropy policy search,” in _Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence_ , ser. AAAI’10. AAAI Press, 2010, p. 1607–1612.


# Electrical Vehicle Fleet Routing Accounting for Dynamic Battery Degradation

Daniel Gebbran  Department of Electrical Engineering
Technical University of Denmark
Kgs. Lyngby, Denmark
<EMAIL_ADDRESS>Jeppe Rich  Department of Technology,
Management and Economics
Technical University of Denmark
Kgs. Lyngby, Denmark
<EMAIL_ADDRESS>Tomislav Dragičević  Department of Electrical Engineering
Technical University of Denmark
Kgs. Lyngby, Denmark
<EMAIL_ADDRESS>
###### Abstract

The increasing uptake of electrical vehicles (EVs) has increased the awareness
of battery degradation costs and how they can be minimized. However, from a
planning perspective it is difficult to integrate battery degradation models
into existing route planning models and to assess how policies that aim at
reducing battery degradation affect route planning costs and degradation
across the fleet. In this paper, a simple transportation vehicle routing
problem (VRP) is formulated as a mixed-integer nonlinear problem (MINLP), with
a modification that allows monitoring the maximum and minimum depth-of-
discharge (DoD) of the entire fleet. This allows us to measure the battery
health degradation _during_ the online optimization process. The results show
that accounting for the impact of different route characteristics on battery
degradation can have an impact on the route planning of the entire fleet as
well as the battery degradation for all vehicles. The latter is achieved by
forcing vehicles to adapt to certain DoD boundaries in the long term.

###### Index Terms:

Vehicle route problem, EV fleet, battery degradation, depth-of-discharge,
cycle lifetime.

##  I Introduction

The electrification of transport will be an essential part of addressing goals
for reduction in $\textnormal{CO}_{2}$ emissions since transportation accounts
for 32% of final energy demand, of which 96.7% is supplied by non-renewable
energy as of 2017 [1]. While electrical vehicles (EVs) accounted for only 2.6%
of global car sales in 2019, they registered a 40% year-on-year increase, and
electrification of transport is gaining momentum by ambitious policy
initiatives, which define clear, long-term signals for the auto industry [2].
In the past few years, government entities and car manufacturers have all made
commitments and investments with respect to EV technology. Furthermore, large
corporations are in the process to transfer their vehicle fleets to EV fleets
and non-automotive companies are investing more heavily in the sector [1].

This increasing uptake of EVs is also altering the way that vehicle routing
strategies are computed, which now has to account for both the traditional
routing problem combined with characteristics arising from EV operation.
Therefore, new factors come into play, such as the charging strategies [3] and
infrastructure111While optimal placing and sizing of charging infrastructure
for EVs is another important topic, it is in itself, it constitute yet another
research problem. For more details, please refer to [4] and references
therein., battery range, battery degradation, speed- and acceleration-
dependent power consumption [5], and the altered waiting times at recharging
stations caused by the longer charging time when compared to fueling internal
combustion vehicles (ICVs) [4].

In parallel, recent research has also focused on how to address such factors,
analyzing driving techniques for predictive energy management of EVs [6], or
dynamic recommendations based on driving patterns [7]. However, even the most
recent works [5] only addresses the degradation modeling within routing
problems to a limited extent.

In contrast, the actual use of more accurate battery models – including
degradation – in optimization frameworks can bring complexities in which they
invoke the use of non-deterministic (non-differentiable) functions [8]. The
battery degradation can be modeled based on thermodynamics and battery state-
of-charge (SoC) dynamics, both of which affect cycle degradation and calendar
aging, finally reflecting the difference in battery performance and total loss
of capacity [9]. The mission profile (i.e., static and dynamic parameters and
variables) of EVs operation, determining temperature and power profile can,
therefore, be used to compute the battery degradation. In particular,
different profiles for charging and discharging the battery can determine
variations in the battery depth-of-discharge (DoD), which in turn affects
advanced cycles. A good method to account for the degradation is the rainflow-
counting algorithm, which also reflects the fact that higher DoDs can lead to
a more pronounced battery degradation [10].

As such, recent works consider degradation models using approximations. In [5]
it is proposed to use an operational planning model for route and charging of
an EV fleet, for which the cost of battery degradation is included in the
objective function. Its degradation model, however, is simplified in the sense
that they use a general degradation cost based on average energy consumption
(a parameter set _a priori_) across vehicles, regardless of their DoD. In
contrast, the use of more accurate degradation models within optimization
frameworks will require the use of non-linear and possibly non-differentiable
frameworks. Recent works have addressed partially this issue using a novel
cost formulation proposed in [8], where authors simplify the rainflow-counting
algorithm to account for the discharging part of the battery operation, using
an auxiliary one-cycle cost curve and a mathematical reformulation of the DoD
with a single time delay to avoid non-differentiable logical expressions that
cannot be interpreted by optimization solvers.

Finally, if the transport sector is to get on track to meet global climate
targets for 2030 goals and beyond, the momentum of transportation
electrification has to be progressively increased [2]. Therefore, it is
important to address open questions relating to the use of EVs and route
planning algorithms. Given the previously described literature gap, the main
contribution of this paper is the proposal of a framework that accounts for
battery degradation _dynamically_ (i.e., preemptively) when calculating
optimal routing strategies for a fleet of EVs. While it still uses a linear
approximation of the DoD such as [5], it assigns a cost associated with the
difference among DoD across multiple vehicles in the problem, avoiding that
any one vehicle has a higher DoD that could result in increased degradation
over time, leading to a result similar to [8].

##  II Modeling approach

###  II-A Modified vehicle routing problem

For any number of EVs $k\in\mathcal{K}$ and path between nodes $i=1,...,n$ and
$j=1,...,n$, we formulate the following modified static VRP as a mixed-integer
nonlinear problem (MINLP):

$\displaystyle\underset{\boldsymbol{x}\in\\{0,1\\}}{\mbox{minimize}}\quad\sum_{k=1}^{\mathcal{K}}\sum_{i=1}^{n}\sum_{j=1}^{n}\left(x_{ijk}c_{ij}+\alpha\>f(\boldsymbol{DoD}^{\textrm{fleet}})\right),$
(1a) subject to:
$\displaystyle\sum_{i=1}^{n}x_{ijk}=\sum_{i=1}^{n}x_{jik}\quad\forall\;j\in\mathcal{N},k\in\mathcal{K},$
(1b) $\displaystyle\hskip
21.33955pt\sum_{k=1}^{p}\sum_{i=1}^{n}x_{ijk}=1\quad\forall\;j\in\mathcal{N}\backslash\\{1\\},$
(1c) $\displaystyle\hskip
35.56593pt\sum_{j=2}^{n}x_{1jk}=1\quad\forall\;k\in\mathcal{K},$ (1d)
$\displaystyle u_{i}-u_{j}+x_{ijk}*n\leq
n-1\quad\forall\;i\in\mathcal{N}\backslash\\{1\\},j\in\mathcal{N},i\neq
j,k\in\mathcal{K},$ (1e) $\displaystyle\hskip
7.11317pt\overline{DoD}^{\textrm{fleet}}\leq
100-SoC^{\textrm{end}}_{k}\quad\forall\;k\in\mathcal{K},$ (1f)
$\displaystyle\hskip 7.11317pt\underline{DoD}^{\textrm{fleet}}\geq
100-SoC^{\textrm{end}}_{k}\quad\forall\;k\in\mathcal{K},$ (1g) $\displaystyle
SoC^{\textrm{end}}_{k}=SoC^{\textrm{start}}_{k}-\sum_{i=1}^{n}\sum_{j=1}^{n}x_{ijk}*e_{ij}\quad\forall\;k\in\mathcal{K},\normalsize$
(1h)

where $x$ is the binary variable representing whether vehicle $k$ is on the
path between $i$ and $j$. $c$ is the travel cost associated with such path and
(1a) is the total cost function which include a penalization term that account
for battery degradation. (1b) ensures each vehicle leaves the node it entered,
(1c) ensures every node is entered at least once, (1d) ensures all vehicles
leave the depot $i=\\{1\\}$, (1e) is the Miller-Tucker-Zemlin (MTZ) sub-tour
elimination constraint, which ensures there are no sub-tours formed within
each vehicle’s tour, and uses the extra auxiliary variable $u$ [11], $\alpha$
is the multi-objective weighting factor related to the associated degradation
cost, $\overline{DoD}^{\textrm{fleet}}$ and $\overline{DoD}^{\textrm{fleet}}$
are the maximum and minimum DoD of the vehicles in the fleet, which is ensured
by (1f) and (1g), and $SoC^{\textrm{end}}_{k}$ is the final battery state-of-
charge for each vehicle, which is computed using (1h), using the energy
$e_{ij}$ associated with each path and the vehicle’s initial SoC, given by
$SoC^{\textrm{start}}_{k}$.

The relaxation of the objective function, by adding the battery degradation
penalization to the original VRP can be modeled in two different ways. The
most intuitive way is to reduce the absolute difference between maximum and
minimum DoDs for the EV fleet, using a quadratic term
$f(\boldsymbol{DoD}^{\textrm{fleet}})=(\underline{DoD}^{\textrm{fleet}}-\overline{DoD}^{\textrm{fleet}})^{2}$.
This will be referred to as Algorithm 1 and requires that the problem is
stated as a mixed-integer nonlinear problem (MINLP). A linear simplification
with $f(\boldsymbol{DoD}^{\textrm{fleet}})=-\overline{DoD}^{\textrm{fleet}}$
allows the problem to be stated as a mixed-integer linear problem (MILP),
referred to as Algorithm 2.

###  II-B Battery degradation modeling

In the paper, we apply a degradation model that accounts for the relationship
between the DoD and the battery cycle lifetime. An example of a Wôhler curve
is shown in Fig. 1, where the relationship between higher DoDs and battery
degradation is shown by the reduction in the battery’s lifetime.

Figure 1: Wôhler curve associating battery degradation with number of cycles
and operational DoD [10].

##  III Results

The given VRP (1) has been modelled in Python, using Pyomo [12] and solved
with MindtPy [13], which also makes use of IPOPT [14]. The test case has used
three vehicles $k\in\mathcal{K}$ and eight nodes for $i$ and $j$. Table I
depicts the results obtained using different weights222Changes in $\alpha$
between the given values shown in the table did not generate any different
results. for $\alpha$ for both Algorithm 1 and Algorithm 2. The table
illustrates the cost deviation in comparison to the basic VRP, the individual
final SoC percentage, the DoD percentage, and the lifetime cycle estimation of
the worst-case battery in the fleet, based on Fig. 1.

It is possible to see that without any change in the route cost, routes and
charging strategies that lead to increasing discharging percentages, will
cause severe degradation of the battery. However, assigning a large
degradation weight might cause largely similar DoD levels across the fleet,
which will also reduce the flexibility and the cost from the perspective of
the operator. Still, this is a known property in multiobjective optimization
problems [15].

This effect is especially notable in the management of EV fleets within large
networks and extensive routes because the degradation is accrued over the DoD,
which is affected in a short-term planning horizon. For instance, a given
vehicle using routes with DoDs of 65% and 20%, every other day, will lead to a
cycle lifetime under 10000 cycles (i.e., as seen in the result with
$\alpha=0$), whereas the same vehicle using routes averaging below 45% DoD
will (i.e., as seen in the result with $\alpha=0.05$) have a lifetime over
25000 cycles – effectively, more than doubling its cycle lifetime. On the
contrary. traditional ICVs maintenance and mechanical degradation are
accumulated over longer planning horizons, instead of differences in daily
use.

TABLE I: Simulation results | Base case | Algorithm 1 | Algorithm 2
---|---|---|---
$\alpha$ | 0 | 0.05 | 0.125 | 0.05 | 2
Cost diff. [%] | N/A | 0 | 45 | 0 | 45
$SoC_{k}^{\textrm{end}}$ [%] | {34,79,80} | {59,75,59} | {41,43,44} | {59,75,59} | {41,43,44}
$DoD_{k}$ [%] | {66,21,20} | {41,25,41} | {41,43,44} | {41,25,41} | {41,43,44}
Cycles | <10000 | <30000 | <27500 | <30000 | <27500

##  IV Discussion

While there have been recent works that focus on the degradation of batteries,
as discussed throughout the introduction, there is still much room for
associating the dynamic degradation of EV batteries within VRPs. Using the
present work as a starting point, this section discuss ramifications and
directions for future research.

Intuitive extensions of the work herein presented include increasing the
dimension of the problem, temporally and spatially, including more diverse
simulation scenarios. Moreover, accounting for the charging schedules of the
fleet of EVs [5] and associating the SoC of EVs across time periods are
natural extensions. On top of that, combining predicted vehicle demand
forecast and prioritizing the charging of EVs during periods with lower
electricity prices are other improvements that have been investigated in the
literature, but without considering the dimension of degradation effects in
the fleet as herein presented. Naturally, those modifications require adopting
more advanced algorithms instead of the simple MINLP herein adopted.

Furthermore, the problem can be re-cast within the purview of on-demand
services, which allows for a more truthful representation of reality where a
differentiated organization for charging and operation intervals can be
associated with predicted fleet autonomy, charging time, and expected service
requests over a given time horizon.

With regards to battery technologies, an improved rainflow-counting algorithm
with included cell temperature effects and specifics for specific fleet
battery cells can be implemented similarly as [8], which allows for a more
detailed calculation of degradation during the operation of the fleet (e.g.,
by improving the association between the degradation cost $\alpha$). In
parallel, more detailed real-time data acquisition can lead to a finer degree
of degradation modeling, associating thermodynamic impacts on the battery [9]
with aggressive driving patterns, and even extending the impact of such
driving behaviors associated with loss of energy (e.g., reduced use of
regenerative braking, and frequent intense acceleration episodes) – which has
been found to account for nearly 40% reduction in battery life when compared
to gentle drivers [16]. These behaviors can also be identified using outlier
detection with online or post-processing diagnosis. Moreover, the degradation
of the battery itself should not be taken as a sole decision variable and must
be combined, for example, with the total energy expenditure and the total
transportation cost having in mind the actual degradation cost in comparison
to these other quantities.

Finally, because calendar aging also plays an important role, it is necessary
to re-evaluate the fleet dispatch accordingly. In other words, excessive
degrading of a single EV compared to others will inevitably lead to a battery
replacement, associated with high costs, whereas the cycles ”saved” by the
other batteries will in fact never be used, since the battery’s calendar aging
itself will then be the pronounced cause for the loss of capacity [9].
Moreover, an investigation on the use of second-hand use batteries might prove
a profitable investment for fleet operators. For instance, if the known-ahead
operating conditions have unavoidable high cycle degradation, the reduced
cycle lifetime will be compensated by the lower purchase costs of second-hand
batteries, and still be a good investment even with a smaller calendar
lifetime [10].

##  V Conclusion

The electrification of transport prompts for improved algorithms that account
for the characteristics of electrical vehicles (EVs) to best use their
potential and increase their operational efficiency. A modified version of the
transportation vehicle routing problem (VRP) was formulated, accounting for
the dynamic depth-of-discharge (DoD) on different EVs of an operating fleet.
It has been shown that by accounting for battery degradation across the fleet,
by forcing the difference between DoD levels for the fleet to be small,
battery degradation can be reduced significantly and thus prolonging the cycle
lifetime of the batteries, while not negatively affecting the fulfillment of
logistic demands. This has been shown in a simple example network, and the
full effect of the battery degradation was computed in retrospect. Unlike
other recent works, this allows a simple way of accounting for the battery
degradation across the fleet of EVs. Finally, other relevant issues have been
discussed, describing possible future directions for this research area.

## References

  * [1] REN 21, “Renewables 2020 Global Status Report (GSR),” Tech. Rep., 2020.
  * [2] IEA, “Global EV Outlook,” Tech. Rep., June 2020.
  * [3] J. J. Q. Yu and A. Y. S. Lam, “Autonomous vehicle logistic system: Joint routing and charging strategy,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 19, no. 7, pp. 2175–2187, 2018.
  * [4] A. F. Jensen, M. Thorhauge, S. E. Mabit, and J. Rich, “Demand for plug-in electric vehicles across segments in the future vehicle market,” _Transportation Research Part D: Transport and Environment_ , vol. 98, p. 102976, 2021.
  * [5] P. Diaz-Cachinero, J. I. Muñoz-Hernandez, J. Contreras, and G. Muñoz-Delgado, “An enhanced delivery route operational planning model for electric vehicles,” _IEEE Access_ , vol. 8, pp. 141 762–141 776, 2020.
  * [6] Y. Zhou, A. Ravey, and M.-C. Péra, “A survey on driving prediction techniques for predictive energy management of plug-in hybrid electric vehicles,” _Journal of Power Sources_ , vol. 412, pp. 480–495, 2019.
  * [7] M. Eider and A. Berl, “Dynamic EV battery health recommendations,” in _Proceedings of the Ninth International Conference on Future Energy Systems_ , ser. e-Energy ’18. New York, NY, USA: Association for Computing Machinery, 2018, p. 586–592.
  * [8] J.-O. Lee and Y.-S. Kim, “Novel battery degradation cost formulation for optimal scheduling of battery energy storage systems,” _International Journal of Electrical Power & Energy Systems_, vol. 137, p. 107795, 2022.
  * [9] L. Calearo, A. Thingvad, and M. Marinelli, “Modeling of battery electric vehicles for degradation studies,” in _2019 54th International Universities Power Engineering Conference (UPEC)_ , 2019, pp. 1–6.
  * [10] S. F. Schneider, P. Novák, and T. Kober, “Rechargeable batteries for simultaneous demand peak shaving and price arbitrage business,” _IEEE Transactions on Sustainable Energy_ , vol. 12, no. 1, pp. 148–157, 2021.
  * [11] P. Toth and D. Vigo, _Vehicle routing: Problems, methods, and applications_. SIAM, 2014.
  * [12] W. E. Hart, C. D. Laird, J.-P. Watson, D. L. Woodruff, G. A. Hackebeil, B. L. Nicholson, and J. D. Siirola, _Pyomo–optimization modeling in python_ , 2nd ed. Springer Science & Business Media, 2017, vol. 67.
  * [13] D. E. Bernal, Q. Chen, F. Gong, and I. E. Grossmann, “Mixed-integer nonlinear decomposition toolbox for Pyomo (MindtPy),” in _13th International Symposium on Process Systems Engineering (PSE 2018)_ , ser. Computer Aided Chemical Engineering, M. R. Eden, M. G. Ierapetritou, and G. P. Towler, Eds. Elsevier, 2018, vol. 44, pp. 895–900.
  * [14] A. Wächter and L. T. Biegler, “On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming,” _Mathematical Programming_ , vol. 106, no. 1, pp. 25–57, March 2006.
  * [15] D. Gebbran, S. Mhanna, Y. Ma, A. C. Chapman, and G. Verbič, “Fair coordination of distributed energy resources with Volt-Var control and PV curtailment,” _Applied Energy_ , vol. 286, p. 116546, Mar. 2021.
  * [16] M. Jafari, A. Gauchia, S. Zhao, K. Zhang, and L. Gauchia, “Electric vehicle battery cycle aging evaluation in real-world daily driving and vehicle-to-grid services,” _IEEE Transactions on Transportation Electrification_ , vol. 4, no. 1, pp. 122–134, 2018.