# Underwater Soft Robotic Hand with Multi-Source Coupling Bio-Inspired Soft
Palm and Six Fingers Driven by Water Hydraulic

Haihang Wang, He Xu∗, Chen Yang, Xin Li, and Siqing Chen The authors are with
College of Mechanical and Electrical Engineering, Harbin Engineering
University, China. Corresponding to He Xu: e-mail<EMAIL_ADDRESS>
###### Abstract

A new fluid-driven soft robot hand in this study uses the idea of the bionics
and has the anthropomorphic form, which is oriented to the flexible grasp
function. The soft robot hand is composed of a new kind of multi-freedom soft
finger and soft palm, which realizes the characteristic grasping function of
forehand and backhand. Combined with the fine fluid control system, the soft
hand can realize flexible grasping under high pressure, so as to realize
flexible grasping operation for different types of target objects in the
underwater environment. The soft robot hand was controlled based on water
hydraulic platform, Finally, the soft robot hand and the fine fluid control
system were connected to form the underwater soft robot hand experiment
platform.

##  I Introduction

Robotics research is becoming increasingly involved in different directions of
scientific research, new robotic platforms are being developed. Different
forms of innovation and challenges are emerging, and new scientific
discoveries are becoming possible. More and more technological inspiration of
human innovation comes from natural features. Bionic robot refers to the
transformation of biological principles into engineering design rules, which
have different challenges that must be solved, and also make innovation more
in line with nature and life [1]. Human-Robot Interaction (HRI) has been a
topic of wide concern in academic circles. The development of robots is the
cornerstone, autonomous movement and information exchange are the development
[2].

Traditional rigid robots have been widely used in manufacturing. Because their
overall structure is rigid, they have disadvantages such as a single task and
limited adaptability, and they are unsafe to interact with humans. At present,
soft robot has gradually attracted more and more scholars and laboratories to
carry out research and breakthrough. The function and information exchange
capability of soft robot cannot be replaced by traditional rigid robot. In
contrast to rigid robots, the soft robot is made of a soft and stretchable
material, such as the silicone rubber. The soft robot has a continuous
deformable drive structure similar to muscle, which can simulate the
biological system to achieve different high curvature bending and twisting,
and achieve relatively large degree of freedom. This makes the soft robot show
unprecedented adaptability and agility. Compared with rigid robots, soft
robots can operate in a limited space. Because of its structure and materials,
soft robots are highly adaptive and can safely interact with humans and the
natural environment. The human-computer interaction capability of soft robots
is also an increasingly developing research and application field, which
includes many challenging problems. Recent advances in the field of soft
robotics have made it possible to accelerate the development of digital design
and manufacturing tools with the potential for solutions that have a positive
social impact [3].

Figure 1: The underwater soft robotic hand in this study. Figure 2: The Design
of the pneumatic hand in Ref. [4] and the water hydraulic hand in this paper.

The material and actuator of soft robot are the key points of its composition
and structure, which directly affect its driving speed and bearing pressure.
At present, the popular soft robot drive technology is the use of compressed
air and pressurized fluid mode. This technology provides a powerful drive
system for soft materials. Compressed air and fluid can directly inflate the
chamber by using the channel network in the elastomer. The contraction device
of McKibben actuator can generate relatively high force and displacement after
deforming through compressed air, and make the robot move accordingly in
combination with other structures of the robot [5]. Worms move by using
cylindrical parts of their bodies to produce traveling waves that contract and
expand. The worm robot uses Pascal’s principle to convert forces and
displacements to achieve mechanical movements. By contracting the longitudinal
muscles, they shorten the body and thus increase its diameter, and by
contracting the circumferential muscles they lengthen the body by decreasing
the diameter. Many worm-like robots are developed based on hydrostatic
structures, and worm-like robot crawlers use shape memory alloy (SMA)
actuators, most of which are soft-hard combined structures [6]. Some complex
soft-bodied movements are very attractive models, such as octopuses and squid.
Flexible arms based on the anatomy and mechanism of octopus arm movement,
highly deformable mechanical structures are woven from plastic fibers. The
soft actuators are arranged laterally and longitudinally, and the overall
bending is achieved by the longitudinal actuators. The flexible arm can
shorten, elongate, bend or twist. Mimicking the actual state of an octopus,
the muscle tissue maintains a constant volume, using hydrostatics to exchange
displacement and force. The flexible arm works in water, taking advantage of
the interaction with the environment [7, 8]. Other solutions for soft
manipulators, such as the Octarm robot, use pneumatic muscles to bend in all
directions [9]. The internal elastomer contains embedded channels that can be
pressurized by fluid or air. Through careful design of chamber size, wall
thickness and geometry, the charging and pressure relief of these internal
channels can result in a variety of shapes of the software manipulator [10].
Soft robots can treat the entire structure as a continuum. In order to
minimize the force required to cause deformation, low modulus materials shall
be used. Silica gel is a very good material, it not only has the
characteristics of low modulus, but also has the characteristics of high
strain and convenient production. The whole structure of the soft robot is
continuous, and the deformation is highly nonlinear due to the large strain.
The field of soft robotics is also creating computing and sensing materials
that allow soft robots to operate better. Different environments also require
different software selectors. Accordingly, soft robots can also follow the
principles of artificial intelligence to enable us to develop biologically
inspired artificial intelligence, which rigid robots cannot do [11, 12, 13].

##  II Related Work

TABLE I: Technical parameters of the silicone materials Silicone | Shore Hardness | Tensile Strength | 100% Modulus | Elongation at Break (%) | Cure type
---|---|---|---|---|---
|  | psi | N/mm2 | MPa | psi | kPa |  |
Dragon Skin 10 | 10A | 475 | 3.28 | 3.28 | 22 | 151 | 1000% | Platinum
Dragon Skin 30 | 30A | 500 | 3.45 | 3.45 | 86 | 593 | 364% | Platinum
Smooth Sil 936 | 36A | 550 | 3.8 | 3.8 | 180 | 1241 | 500% | Platinum
Elastosil M 4601 | 28A | 942 | 6.5 | 6.5 | 54-65 | 375-450 | 700% | Platinum
VytaFlex 20A | 20A | 200 | 1.38 | 1.38 | 50 | 345 | 1000% | Urethane
EcoFlex 00-30 | 00-30 | 200 | 1.38 | 1.38 | 10 | 69 | 900% | Platinum
Mold Star 30 | 30A | 420 | 2.9 | 2.9 | 96 | 662 | 339% | Platinum

The core function of an effective soft robot design is grasping. Because the
soft robot with continuous structure breaks the structure of the connecting
rod joint, the shape of the soft robot hand is more universal than that of the
rigid robot hand. Combined with its own flexible materials to achieve a new
more secure and effective grasping strategy and interactive functions.
Artificial muscle hydrostatic device design and intelligent muscle alignment
of octopus-like robotic arm, can achieve bending, shortening and elongation
functions. Through the combination of different longitudinal actuators, global
bending can be obtained in each direction, and then grasping function can be
realized [14]. At the same time, the internal cables will lead to the
shortening and recovery of the robotic arm. The relationship between
elongation and diameter reduction corresponds to the model of braids. A
universal gripper composed of granular materials wrapped in elastic film can
quickly grab and release various objects by using a combination of positive
and negative pressures [15]. You can grab objects that are challenging for
general purpose grippers, such as flat objects, soft objects, or objects with
complex geometries. The gripper passively conforms to the shape of the target
object, grabs the object in a vacuum hardening rigid way, and then uses the
positive pressure to reverse back to the original form to achieve the effect
of releasing the object. Human hands also offer great inspiration for adaptive
robots. The joints maintain passive finger compliance, giving the fingers
flexibility and an extended range of motion. Passive flexibility is the result
of the direction of motion determined by the stiffness and geometric
constraints of the joint. Using anatomically correct phalanx, elastic
ligaments, and antagonistic tendons, an anthropogenic joint with
multidirectional passive compliance was constructed. Fingers are directly used
in coordination, which is conducive to mechanical adaptation when grasping
large objects [16]. Professor George M. Whitesides Group developed a soft
robot, which is driven by a pneumatic net formed by small channels, can
achieve simple operation and complex movement. The whole structure design is
made of elastomer material, which can realize the fast and large movement of
the pneumatic network, and has a lower fatigue and failure rate. In order to
achieve the multi-angle bending effect, a non-retractable material is needed
to suppress the expansion of the cavity wall. The combination of high
actuation rate and high reliability of soft robot actuator opens up a new
application field for its expansion rate, channel shape and structural
performance, thus achieving the advantages of fast inflation, easy control and
measurement, light weight and so on [17].

Soft robot hand is made of soft material, which has the advantages of strong
flexibility, good man-machine interaction and simple structure and easy
control. As an important branch of soft robot, soft manipulator has been
gradually studied by more and more researchers and applied to people’s
production and life. The ability of soft robot hand to bend, elongate,
contract, expand and twist is also an important aspect of research work at
home and abroad. Wearable robotic hands have been used in medicine to drive
the motor function of disabled hands and carry out strength training. The
integral exoskeleton glove is a soft exoskeleton with an underactuated tendon
actuation mechanism in the adaptive mechanism. Algorithms are used to limit
the maximum level of muscle activation to prevent muscle and joint damage.
Impedance-controlled rehabilitation exercises can provide different
stimulation to muscles through different combinations of impedance parameters
and adjust the exercise intensity by changing the control gain of the motion
program controller [18]. Min Li team from Xi’an Jiaotong University [19]
designed a robot teleoperation soft hand based on tactile feedback of
fingertips is used to complete complex tasks and ensure the safety and
friendliness of human-computer interaction. Manipulator can achieve finger
flexion and contraction action. Bend sensors are embedded in the finger to
monitor the bending Angle of the actuator. A pressure sensor on the fingertip
feeds contact forces back to the operator. The manipulator is used for
grasping fragile items, rescuing the injured, remote interaction with patients
and other complex work, and the precision of the movement is very high.
Manipulator demonstrates the application potential of flexible robot hands in
complex operation tasks. Fluid driven flexible manipulator is highly compliant
and can adapt to various objects. The tendon-driven flexible manipulator has
the advantages of simple control, high flexibility, large output, but poor
compliance. The fluid-driven manipulator improves this shortcoming. Most
manipulator designs have only one drive method. A simple two-mode actuator is
proposed that combines fluid and tendon actuation [20]. These brakes play to
each other’s strengths and compensate for each other’s limitations, but design
and control become more complex. By twisting the tube to drive, only one motor
is needed to produce two drive modes. The finite element part of the actuator
ensures the flexibility and softness of the fingers during grasping. The
bending Angle, bending force and grasping ability of the flexible manipulator
are improved, but the disadvantage is that the volume is large and the weight
is large, which is not conducive to the wearable of soft robot. Deimel et al.
of the Technical University of Berlin proposed a highly supple, underdriven,
robust and dexterous anthropomorphic hand. This software hand has the
advantage of being cheap to manufacture and adaptable to form. Efficient hand
design with PneumFlex actuator. The effective dimension of grasping posture
exceeds the dimension of driving signal, which proves that relatively simple
control can achieve complex grasping behavior [21]. Yang Yang’s team at the
University of Hong Kong has designed a novel design of soft robot hand. The
robot is 3D-printed and consists of five fingers and a palm. All fingers can
be driven independently, and sensing modules are built into the entire hand
structure. The fingers are driven by compressed air. In the bending process,
the chamber is filled with loosely arranged particles and squeezed by air,
which makes the fingers have high stiffness and increase the output force and
carrying capacity [22].

##  III Design

###  III-A Soft Robotic Hand

Our previous work in Ref. [4] focused on the design of a novel soft robotic
hand with an biomimetic morphology. Its soft palm is designed in modular
design approach, which includes two parts: Part A and B. The inspiring
function of applying the soft actuator as the palm of the soft hand was
presented and tested. The soft palm with inspiring function by applying the
soft actuator in human hand-like motion performed a diversity of grasps.

The first generation and the second generation of the soft robot hand design
are shown in Figure 2(a). The relevant research of the first generation of the
pneumatic soft hand [17] provides the preliminary configuration design and
experience. It is pneumatic and the driving pressure range is generally
between 0-50 kPa, the max pressure value in it can reach 70 kPa under the
ultimate load. However, too high pressure will lead to the rupture risk of
soft airbag of the hand. The low actuation pressure limits the soft hand’s
ability to grasp heavy objects.

Due to the shortcomings of the pneumatic soft hand, a soft bionic hand was
designed which is driven by the water pressure. The new type soft hand can
bear 300 kPa water pressure in the underwater environment, which has the large
grasping force output for the underwater target. Figure Figure 2(b) is the
water hydraulic soft hand in the study, which is driven by water hydraulic
pressure and works in an underwater environment. The main performance
requirement of soft robot actuator is to inflate. The soft robot hand can meet
the performance requirements of inflating, bending and twisting based on
aerodynamic deformation.

###  III-B Material

Silicone material is the key factor to determine the pressure resistance of
the soft actuator. Tab. I lists the commonly used silicone materials and the
key technical parameters in the production of soft robots in the literature.
Ecoflex 00-30 has a minimum shore hardness of 00 at 30, which means a very low
hardness, equivalent to a racket or gel insoles. With a minimum tensile
strength of 200 psi and a minimum 100% modulus of 10 psi, Ecoflex 00-30 is the
most stretchable and flexible material. The Dragon Skin 10 has a tensile
strength of 475 psi and a maximum elongation at break of 1000%, which reflects
better toughness and high flexibility. Based on the experience of the first
and second generation pneumatic soft hands, the S11 finger made with the
Platinum-cured silicone of the Dragon Skin 10 has a 270 degree bend Angle
output at 50 kPa. The shore hardness of the material is the core parameter
that determines the pressure required to achieve the same bending angle.

The reason why the soft actuators break is not only that the water pressure is
too high, but that the air cavity in the hand expands indefinitely without
constraint, which makes some structural weak points continue to be stretched
and then break. In order to improve its pressure bearing capacity, the third
generation of soft hand was made of Smooth-Sil 936 two-component platinum
cured silicone produced by Smooth-On Company, with a shore hardness of 36A, a
natural color of blue, and a tensile strength of 550 psi, which was the ideal
silicone material for this study.

###  III-C Sealing method

Fluid-driven soft robots, when driven by the low pressure, basically use
silicone self-sealing type that is that the trachea is directly inserted into
the air cavity and the sealing effect is achieved by relying on the elastic
deformation of silicone itself. Under high pressure, relying on the elasticity
of silicone itself cannot be sealed, so the rigid joint is needed. The soft
actuators in this paper are all sealed with the inverted taper joint with the
screw fastening. The sealing structure of the reverse cone joint is composed
of the reverse cone plug, the reverse cone ring and the matching Teflon hard
tube. When in use, the end face of the hard tube is cut flat, and the reverse
cone plug and the reverse cone ring are set in turn, and the bottom of the
pressing ring is flush with the end face of the hard tube. When the reverse
cone plunger is tightened, the reverse cone plunger compresses the reverse
cone ring so that the ring closes the joint. The backward taper plug thread is
1/4 - 28UNF thread, and the sealing strength is 0.7 MPa.

###  III-D Soft Finger

Figure 3: The CAD model and prototypes of the soft fingers

The soft fingers of this work adopt the bionic appearance design, and the
overall configuration refers to the shape and size of human fingers, which is
shown in Figure 3. Its driving structure refers to the advantages of the
Pneunets actuator and the fiber enhanced actuator. The fiber reinforced
structure is added to the grid-shaped finger main structure in order to
restrain the radial invalid deformation and the soft actuator can maximize its
effective deformation potential.

Figure 4: The Structure of the soft finger

Figure 4 shows the structural design of the soft finger, which consists of an
expandable and modular fingertip, a soft finger body, a sealing plug, an
inverted tapered joint combination structure and a hard tube. The soft finger
body is composed of a Smooth Sil 936 silicone. The sealing plug is based on
the 3D printing technology and is made of the imported nylon material. The
1/4-28UNF tap is used to tap the four holes reserved to match the reverse
taper joint seal structure. Taper joint components are produced and sold by
Nanjing Runze Fluid Company, China. The soft finger contains four symmetrical
independent software cavities, which requires four sets of inverted cone seal
combinations. Four groups of inverted cone joints with inverted cone
combination realize the independent drive of four independent cavities. The
gap between the sealing plug and the body of the soft finger is sealed by
tightening and winding the thin wire, which is the red rope in Figure 4(b).

Figure 5: The inner chambers of the soft finger

The fiber reinforced structure is the key structure to improve the pressure
resistance of the soft finger. It restricts the expansion and deformation of
the soft air cavity in the radial direction through regular cross winding, so
as to maximize the expansion and bending ability of the soft air cavity in the
axial direction. In Figure 4(b), the green thin line is the fiber rope which
is a super tensile subline. It is non-extensible, imported raw wire rope of 12
brails and can withstand a breaking ultimate tension of 164 N.

Figure 5 shows the auxiliary groove structure on the body of the soft finger
to guide the winding path. The main body of the soft finger silicone is a
four-cavity symmetrical design with a wall thickness of 2mm, as shown in
Figure 10. The upper part of the green and the lower part of the yellow are
the symmetrical structures. The green is an inextensible limiting layer and
the material is organza.

###  III-E Soft Palm

For the hand grasping, the palm always works together with the fingers to
realize various operations. This paper discusses the function of soft palm
from the perspective of human palm movement. Two main functions can be
achieved, which are the thumb abduction and the palm bending. An important
feature of the human hand is the abduction and adduction of the thumb, which
allows the thumb to rotate and adjust position and orientation relative to the
object being manipulated, it is essential for grasping.

Bending the entire plane of the palm helps to grasp smaller objects. The thumb
of a soft hand cannot touch the other fingers without the aid of palm bending,
even though all fingers are bent 180 degrees under the highest pressure. The
software palm adopts modular design method. As shown in Figure 11, the
structural design of the palm was inspired by the mechanism of the pneumatic
mesh actuator which is consisted of a mesh chamber inside a silicone resin on
a strain-limiting layer. It realizes the abduction of the thumb and the
overall bending of the palm. The bending motion of the palm is achieved by
enlarging the horizontal width of the pneumatic net actuator. The width of the
air chamber along the palm is designed to be as wide as possible to generate
enough force to bend the palm along the distal fingers. In addition, the
humanoid aesthetic design is realized in the last step after ensuring that the
soft actuator works as expected and does not affect the performance of the
pneumatic actuator.

##  IV Experiment

###  IV-A Test of the soft finger

Figure 6: The test results of the soft finger when actuating single chamber

The soft finger used in this study was tested to analyze its performance on
bending and grasping. The bending motions are shown in Figure 6. One of the
four individual chambers was driven from 0 to 0.40 MPa. The finger can bend up
to 270 degree when the pressure was 0.40 MPa. In general, the soft fingers are
designed for being actuated under 0-0.35 MPa pressure. The finger under 0.35
MPa can bend 180 degree, which meet most situation in real world.

###  IV-B Test of the soft palm

Figure 7: The test results of the soft finger

The human-inspired soft palm used in this study was tested to analyze its
performance on palmar bending and thumb abduction. As shown in Figure 7, the
soft palm module was test and its two soft actuators were driven respectively.
The inflating motions by the soft actuators will be transferred as the bending
motions of the palm and thumb. And the compression force generated by the
inflated chambers will be transferred as the grasping force of the soft palm.

###  IV-C Water hydraulic valve control system

Figure 8: The water hydraulic valve control system

The experimental setups for the pressure regulation characteristics of the
water pressure proportional pressure valve is shown in Figure 8. It is mainly
composed of a control cabinet, a computer, a proportional amplifier, an analog
input and output module, a proportional pressure control experimental valve,
and a display instrument device. The proportional pressure control experiment
valve is connected to the piping system of the water hydraulic experiment
bench through a pneumatic quick connector. The water hydraulic test bench can
provide a pressure of 6 MPa. The inlet pressure of the test valve can be set
by adjusting the working frequency of the motor in the control cabinet and the
overflow valve in the piping system of the test bench. The outlet pressure of
the test bench can be obtained on the display instrument. pressure.

###  IV-D Experimental setups

Figure 9 shows the experimental setups of the underwater soft robotic hand. It
mainly includes software robot hand, fine hydraulic control system, water
tank, bracket, water hydraulic test bench, electric control system, etc. Fill
the water tank with water, even if the soft robot hand is working in an
underwater environment, so as to test its effectiveness in underwater
operations.

Based on the laboratory water hydraulic test system, the experimental platform
of the software robot hand, the water pressure proportional pressure control
valve, and the water pressure solenoid switch valve that can be used in this
paper is built. The soft robot hand is fixed by a bracket and placed in an
underwater environment. Each soft finger has 4 independent cavities, so 4
independent pipelines are required for pressurization control. When the
software robot hand performs the grasping operation, through the precision
hydraulic control system, the pressure adjustment and switch control of the
independent chambers of the soft robotic hand are carried out, so that the
fingers and the software palm cooperate to achieve grasping of the target
object.

Figure 9: The experimental setups of the underwater soft robotic hand

##  V Conclusions

A new fluid-driven soft robot hand in this study uses the idea of the bionics
and has the anthropomorphic form, which is oriented to the flexible grasp
function. The soft robot hand is composed of a new kind of multi-freedom soft
finger and soft palm, which realizes the characteristic grasping function of
forehand and backhand. Combined with the fine fluid control system, the soft
hand can realize flexible grasping under high pressure, so as to realize
flexible grasping operation for different types of target objects in the
underwater environment. According to the existing water hydraulic valve
technology, a new proportional pressure control valve was designed by using
the hydraulic half bridge circuit to control its pressure. The water hydraulic
proportional throttle valve was selected as the adjustable fluid resistance in
the C hydraulic half axle and the manual throttle valve as the fixed fluid
resistance. According to the design parameters of the proportional throttle
valve structure design, the proportional throttle valve and manual throttle
valve were integrated into a valve to form a new proportional pressure control
valve based on the C-type hydraulic half bridge. Five new proportional
pressure regulating valves were made, and a fine fluid control system was
formed. Finally, the soft robot hand and the fine fluid control system were
connected to form the underwater soft robot hand experiment platform.

## ACKNOWLEDGMENT

This work was supported by the Natural Science Foundation of China under Grant
51875113, Natural Science Joint Guidance Foundation of the Heilongjiang
Province of China under Grant LH2019E027.

## References

  * [1] G.-Z. Yang, J. Bellingham, P. E. Dupont, P. Fischer, L. Floridi, R. Full, N. Jacobstein, V. Kumar, M. McNutt, R. Merrifield, B. J. Nelson, B. Scassellati, M. Taddeo, R. Taylor, M. Veloso, Z. L. Wang, and R. Wood, “The grand challenges of science robotics,” _Science Robotics_ , vol. 3, no. 14, p. eaar7650, 2018.
  * [2] M. A. Goodrich and A. C. Schultz, “Human-robot interaction: a survey,” _Found. Trends Hum.-Comput. Interact._ , vol. 1, no. 3, p. 203–275, 2007\.
  * [3] D. Rus and M. T. Tolley, “Design, fabrication and control of soft robots,” _Nature_ , vol. 521, no. 7553, pp. 467–475, 2015.
  * [4] H. Wang, F. J. Abu-Dakka, T. Nguyen Le, V. Kyrki, and H. Xu, “A novel soft robotic hand design with human-inspired soft palm: Achieving a great diversity of grasps,” _IEEE Robotics Automation Magazine_ , vol. 28, no. 2, pp. 37–49, 2021.
  * [5] G. G. Wallace, P. R. Teasdale, G. M. Spinks, and L. A. Kane-Maguire, _Conductive electroactive polymers: intelligent polymer systems_. CRC press, 2008.
  * [6] K. Quillin, “Kinematic scaling of locomotion by hydrostatic animals: ontogeny of peristaltic crawling by the earthworm lumbricus terrestris,” _Journal of Experimental Biology_ , vol. 202, no. 6, pp. 661–674, 03 1999\.
  * [7] L. Margheri, C. Laschi, and B. Mazzolai, “Soft robotic arm inspired by the octopus: I. from biological functions to artificial requirements,” _Bioinspiration & Biomimetics_, vol. 7, no. 2, p. 025004, may 2012.
  * [8] B. Mazzolai, L. Margheri, M. Cianchetti, P. Dario, and C. Laschi, “Soft-robotic arm inspired by the octopus: II. from artificial requirements to innovative technological solutions,” _Bioinspiration & Biomimetics_, vol. 7, no. 2, p. 025005, may 2012.
  * [9] D. Trivedi, C. D. Rahn, W. M. Kier, and I. D. Walker, “Soft robotics: Biological inspiration, state of the art, and future research,” _Applied Bionics and Biomechanics_ , vol. 5, pp. 99–117, 2008.
  * [10] R. F. Shepherd, F. Ilievski, W. Choi, S. A. Morin, A. A. Stokes, A. D. Mazzeo, X. Chen, M. Wang, and G. M. Whitesides, “Multigait soft robot,” _Proceedings of the National Academy of Sciences_ , vol. 108, no. 51, pp. 20 400–20 403, 2011.
  * [11] S. Kim, C. Laschi, and B. Trimmer, “Soft robotics: a bioinspired evolution in robotics,” _Trends in Biotechnology_ , vol. 31, no. 5, pp. 287–294, 2013\.
  * [12] D. Trivedi, C. D. Rahn, W. M. Kier, and I. D. Walker, “Soft robotics: Biological inspiration, state of the art, and future research,” _Applied Bionics and Biomechanics_ , vol. 5, p. 520417, 2008.
  * [13] F. Iida and C. Laschi, “Soft robotics: Challenges and perspectives,” _Procedia Computer Science_ , vol. 7, pp. 99–102, 2011.
  * [14] C. Laschi, M. Cianchetti, B. Mazzolai, L. Margheri, M. Follador, and P. Dario, “Soft robot arm inspired by the octopus,” _Advanced Robotics_ , vol. 26, no. 7, pp. 709–727, 2012.
  * [15] J. R. Amend, E. Brown, N. Rodenberg, H. M. Jaeger, and H. Lipson, “A positive pressure universal gripper based on the jamming of granular material,” _IEEE Transactions on Robotics_ , vol. 28, no. 2, pp. 341–350, 2012.
  * [16] U. Çulha and F. Iida, “Enhancement of finger motion range with compliant anthropomorphic joint design,” _Bioinspiration & Biomimetics_, vol. 11, no. 2, p. 026001, 2016.
  * [17] B. Mosadegh, P. Polygerinos, C. Keplinger, S. Wennstedt, R. F. Shepherd, U. Gupta, J. Shim, K. Bertoldi, C. J. Walsh, and G. M. Whitesides, “Pneumatic networks for soft robotics that actuate rapidly,” _Advanced Functional Materials_ , vol. 24, no. 15, pp. 2163–2170, 2014.
  * [18] U. Jeong, H.-K. In, and K.-J. Cho, “Implementation of various control algorithms for hand rehabilitation exercise using wearable robotic hand,” _Intelligent Service Robotics_ , vol. 6, no. 4, pp. 181–189, 2013.
  * [19] M. Li, Y. Zhuo, J. Chen, B. He, G. Xu, J. Xie, X. Zhao, and W. Yao, “Design and performance characterization of a soft robot hand with fingertip haptic feedback for teleoperation,” _Advanced Robotics_ , vol. 34, no. 23, pp. 1491–1505, 2020.
  * [20] Y. Li, Y. Chen, T. Ren, Y. Hu, H. Liu, S. Lin, Y. Yang, Y. Li, and J. Zhou, “A dual-mode actuator for soft robotic hand,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 1144–1151, 2021.
  * [21] R. Deimel and O. Brock, “A novel type of compliant and underactuated robotic hand for dexterous grasping,” _The International Journal of Robotics Research_ , vol. 35, no. 1-3, pp. 161–185, 2016.
  * [22] Y. Yang, Y. Li, Y. Chen, Y. Li, T. Ren, and Y. Ren, “Design and automatic fabrication of novel bio-inspired soft smart robotic hands,” _IEEE Access_ , vol. 8, pp. 155 912–155 925, 2020.


# Enforcing Timing Properties in Motorway Traffic

Christopher Bischopink Carl von Ossietzky University Oldenburg, Oldenburg
<EMAIL_ADDRESS>
###### Abstract

In previous work [5], we proposed a _Runtime Enforcement_ Approach to deal
with timing properties in motorway traffic, which are present in form of
_Timed Multi-Lane Spatial Logic (TMLSL)_ formulae, a logic tailored to express
both spatial and timing properties. Employing communication between the cars,
we utilised a nondeterministic controller “guessing” which actions to execute
next for each car, before asking the local monitors of the cars for permission
to execute the announced actions. In this contribution, we consider a more
reasonable controller that only considers sequences that satisfy its own
properties. This is done utilising region automata that one can generate from
the cars’ specifications. In the approach, we also came along a minor
decidability result for TMLSL.

##  1 Introduction

With the number of (at least partially) autonomous cars increasing on the
roads around the globe, challenges and advantages in the specification and
verification of their behaviour occur. If one assumes that the cars are able
to communicate with each other, a more detailed interplay between them is
possible than with human drivers and allows finding solutions for complicated
traffic situations that human drivers could easily miss.

The roads we consider here are motorways, formalised as _traffic snapshots_
[10] with a logic to reason about them called _Multi-Lane Spatial Logic
(MLSL)_ [10]. We extended this spatial logic towards _Timed Multi-Lane Spatial
Logic (TMLSL)_ to also cover the timing aspect of a car’s specification in
[4]. Based on TMLSL, we proposed a runtime-enforcement approach in [5],
employing a nondeterministic controller that asked for the permission of other
cars for the actions it wants to execute. Due to the nondeterminism,
completely unreasonable sequences that even violate the own car’s
specification could be announced. In the lack of a result that allow
announcing/checking only reasonable sequences, the nondeterministic controller
still allowed us to show that the approach is complete.

In this work, we propose a more reasonable approach, utilising the region
automaton of the cars’ specifications. Still, all cars announce sequences they
want to achieve, but this time all announced sequences would yield satisfying
runs at least for the car that announces them. The announced sequences are
then checked by a central entity, e.g. a road-side unit, for a run that is
satisfying for all cars and informs the cars accordingly. We furthermore
present a minor decidability result, eliminating one of the causes for the
semi-decidability of TMLSL [4].

#### Related Work

In the context of MLSL, different topologies have been explored in addition to
motorway traffic, namely country roads [9] and urban traffic [18], as well as
their satisfaction problems [14][7] and controllers for cars in these
topologies with different desirable properties such as liveness and fairness
[6, 19]. Other approaches in the context of autonomous or automated driving
systems use e.g. _differential dynamic logic_ [13] or a specification with
extended types of timed automata [11]. These approaches mostly concentrate on
a top-level view of the system under control. A more technical view of the
evolution of a cars dynamics in an adaptive cruise control setting is e.g.
given in [2]. Runtime Enforcement [17] and runtime verification [8] are also
well studied topics. To the best of our knowledge, runtime enforcement
approaches however are more intensively considered in more restricted settings
than motorway traffic, where the system evolves quiet dynamically to the input
given. Another feature is that in our case, the input and output of the system
under control are different from each other.

##  2 Preliminaries

In this Section, we introduce the formal concepts our approach is build on. We
start with the model of motorway traffic, its logic and evolution in Sect. 2.1
and continue with the timing model used, Sect.2.2. The combination of them is
called TMLSL and covered in Sect. 2.3.

###  2.1 Spatial Model of and Logic for Motorway Traffic

#### Model

The spatial model we use in the setting of motorway traffic was introduced in
[10]. It allows only traffic in one direction on a fixed set of lanes
$\mathbb{L}=\\{1,\dots,N\\}$ with an infinite extension each. On these lanes,
cars from the set of car identifiers $\mathbb{I}=\\{A,B,\dots\\}$ drive, each
car $C$ of them with a certain speed $\mathit{spd}(C)$, acceleration
$\mathit{acc}(C)$ and position on the lane, $\mathit{pos}(C)$. There are two
different types of occupation a car can have on lanes, either a reservation
$\mathit{res}:\mathbb{I}\rightarrow\mathcal{P}(\mathbb{L})$, the space it
physically occupies (multiple lanes if it is changing lanes at this moment) or
a claim $\mathit{clm}:\mathbb{I}\rightarrow\mathcal{P}(\mathbb{L})$, the lane
a car wishes to change to, which is the equivalent of setting a turn signal.
Altogether, this information is represented as a traffic snapshot
$\mathit{TS}=(\mathit{res},\mathit{clm},\mathit{pos},\mathit{spd},\mathit{acc})$.

In a traffic snapshot, there is no information present what the sizes of the
cars and their braking distances are, as $\mathit{pos}$ only stores the rear
end of each vehicle. We neglect the concept of a _Sensor Function_ here that
makes this information available to us and simply assume that size and braking
distance of each car is known. Also omitted is the _View_ that allows to only
consider a finite extension of the infinite extension of a traffic snapshot
when evaluating formulae. A graphical representation of three traffic
snapshots is depicted in Fig. 1, where we also omitted showing concrete values
for the position, speed and acceleration of the cars.

As already hinted at, a traffic snapshot describes the situation on the road
at one point in time only. A situation on the road may evolve, which is
handled in the model via _transitions_.

#### Transitions

We divide the set of transitions usable in a traffic snapshot into transitions
regarding the discrete behaviour between lanes and transitions regarding the
continuous behaviour along the lanes. The first set consists of car $C$
claiming a lane $n$ resp. withdrawing all claims
(${\mathsf{c}(C,n)}/{\mathsf{wd\ c}(C)}$) and car $C$ reserving a lane resp.
withdrawing all reservations except the one on lane $n$
(${\mathsf{r}(C)}/{\mathsf{wd\ r}(C,n)}$). The second set is the one we focus
more on, as it is considered more intensively in what follows, they handle the
change of a car’s acceleration to some value $a$ ($\mathsf{acc}(C,a)$) as well
as the passing of $t$ time units ($t$). In the following definition, $\oplus$
is the overriding operator of Z [20]:

$\displaystyle\mathcal{TS}\xrightarrow{t}\mathcal{TS^{\prime}}$
$\displaystyle\Leftrightarrow\ \ $
$\displaystyle\mathcal{TS^{\prime}}=(\mathit{res},\mathit{clm},\mathit{pos}^{\prime},\mathit{spd}^{\prime},\mathit{acc})$
$\displaystyle\land\forall
C\in\mathbb{I}:\mathit{pos}^{\prime}(C)=\mathit{pos}(C)+\mathit{spd}(C)\cdot
t+\frac{1}{2}\mathit{acc}(C)\cdot t^{2}$ $\displaystyle\land\forall
C\in\mathbb{I}:\mathit{spd}^{\prime}(C)=\mathit{spd}(C)+\mathit{acc}(C)\cdot
t$
$\displaystyle\mathcal{TS}\xrightarrow{\mathsf{acc}(C,a)}\mathcal{TS^{\prime}}$
$\displaystyle\Leftrightarrow\ \ $
$\displaystyle\mathcal{TS^{\prime}}=(\mathit{res},\mathit{clm},\mathit{pos},\mathit{spd},\mathit{acc}^{\prime})$
$\displaystyle\land\mathit{acc}^{\prime}=\mathit{acc}\oplus\\{C\mapsto a\\},$

Over the set of actions, which are the transitions without the one where only
time passes, we define _timed words of actions_
$\omega=\langle(\alpha_{0},t_{0}),\dots,(\alpha_{n},t_{n})\rangle$, with
$\alpha_{i}$ an action and $\langle t_{0},\dots,t_{n}\rangle$ a real-time
sequence. For a formal account, we refer to [15].

A graphical representation of a transition sequence including two transitions
(one discrete and one continuous) is shown in Fig. 1. It can be interpreted as
the timed word $\omega_{1}=\langle({\mathsf{r}(A)},3)\rangle$.

######  Remark 1 (Dynamic behaviour of the cars).

The model used for describing the dynamics of the cars is a quiet simple one,
ignoring many difficulties that one would encounter in the real world, such as
friction or variable acceleration capabilities based on the current speed.
Still, we believe that it is a good abstraction of the real world’s dynamics.
Especially if one considers that the positions (plus size and braking
distance) could be over-approximations, this allows some degree of freedom in
achieving a behaviour to match the correct positions.

Figure 1: A transition sequence with three traffic snapshots and two actions,
taking place with two cars on two lanes. Car $A$ is faster than car $B$, so it
comes closer when $t=3$ time units pass. Afterwards, it reserves its formerly
claimed space (dashed copy of it on the neighbouring lane), one step further
in an attempt to overtake car $B$.

#### Logic

To reason about the traffic situations formalised as traffic snapshots, the
logic MLSL [10] was introduced . Here, we consider a variant of MLSL called
MLSLS (MLSL _with scopes_) [7], limiting the range of cars over which car
variables are evaluated to a finite range. Formulae of MLSLS are constructed
according to the grammar

$\varphi::=\gamma=\gamma^{\prime}\mid\mathit{free}\mid\mathit{re}(\gamma)\mid\mathit{cl}(\gamma)\mid
l=k\mid\exists
c.\varphi\mid{\varphi_{1}}{\,\operatorname{\smallfrown}\,}{\varphi_{2}}\mid\begin{array}[]{c}\varphi_{1}\\\
\varphi_{2}\end{array}\mid cs:\varphi,$

and standard Boolean combinations of such formulae, where $\gamma$ and
$\gamma^{\prime}$ are car variables, $k\in\mathbb{R}$ and $cs$ is a (sub-)set
of car variables.

The atoms that formulae are constructed from are the comparison of two car
variables $\gamma=\gamma^{\prime}$, $\mathit{free}$ denotes a segment with
free space that is not occupied by others, the reservation
${\mathit{re}(\gamma)}$ of a car $\gamma$, the claim ${\mathit{cl}(\gamma)}$
of a car $\gamma$ and the comparison $l=k$ of the length $l$ of the considered
segment against some value $k$. With $\exists c.\varphi$ one asks for the
existence of a car $c$ that satisfies $\varphi$. The horizontal chop operator
$\left({\varphi_{1}}{\,\operatorname{\smallfrown}\,}{\varphi_{2}}\right)$ is
used to determine if it is possible to divide the current segment into two
parts along the lanes s.t. in the first part $\varphi_{1}$ and in the part
directly ahead of it $\varphi_{2}$ holds. The same can be specified with the
vertical chop operator $\left(\begin{array}[]{c}\varphi_{1}\\\
\varphi_{2}\end{array}\right)$, but the point to divide is in between two
lanes this time. $cs:\varphi$ limits the scope over which $\varphi$ is
evaluated to the finite domain $\mathit{cs}$ and effects only formulae that
use quantification over the cars in their semantics and thus only $\exists
c.\varphi$ and $\mathit{free}$. In Sect. 3, we focus on length comparisons
$l=k$ and simply abbreviate them as $\theta$, as there can be multiple of them
regarding the same segment.

A common abbreviation used is the _somewhere_ modality
$\left\langle\varphi\right\rangle$, expressing that there is a partition on
the road along and in between the lanes s.t. $\varphi$ holds in some point of
the partition.

For a formal definition, especially about the exact semantics of MLSLS
formulae, we refer the reader to [7], but would like to point out that MLSLS
is, in contrast to pure MLSL, decidable.

###  2.2 Model and Logic of Time

The logic we consider here for the timing aspects is called _State-Clock Logic
(SCL)_ [16]. Formulae from this logic are constructed over an alphabet of
propositions $\Sigma$ according to the grammar

$\psi::=p\ \mid\ \psi_{1}\lor\psi_{2}\ \mid\ \lnot\psi\ \mid\
\psi_{1}\mathcal{U}\psi_{2}\ \mid\ \psi_{1}\mathcal{S}\psi_{2}\ \mid\
\vartriangleright_{\sim c}{\psi}\ \mid\ \vartriangleleft_{\sim c}{\psi},$

with $\ \sim\ \in\\{<,\leq,=,\geq,>\\}$ and $p\in\Sigma$.

Apart from well-known Boolean combinations of formulae and the usual until-
and since operators ($\mathcal{U}$ resp. $\mathcal{S}$ ), SCL allows to
measure the time since ($\vartriangleleft$)/ until ($\vartriangleright$) a
formula $\psi$ held/holds for the last/next time and compare this difference
with $\sim c$.

The semantics of SCL formulae is evaluated on (usually infinite) _timed
sequences of states_ $m=\langle(s_{0},I_{0},),(s_{1},I_{1}),\dots\rangle$ with
$s_{i}\subseteq\Sigma$ and $\langle I_{0},I_{1},\dots\rangle$ a monotonically
increasing sequence of adjacent intervals. Intuitively, the formula
$\vartriangleright_{\sim\ c}{\psi}$ holds at time point $t$ in the $i$th state
of $m$, written $(m,i,t)\vDash\vartriangleright_{\sim\ c}{\psi}$ iff there is
some state $(s_{j},I_{j})$ at position $j>i$ where $\psi$ holds, all states in
between $i$ and $j$ do not satisfy $\psi$ and the difference between the left
border of the $j$th interval $I_{j}$ and $t$ satisfies $\sim\ c$ . The
analogous applies for the operator $\vartriangleleft_{\sim\ c}{\psi}$, the
semantics of the remaining operators is as expected. Example for both syntax
and semantics are given in the next section, for a more formal account on the
topic we refer the reader to [16].

The decidability problem of SCL is known to be decidable. Given a SCL formula
$\psi$, one can construct a _State-Clock (SC)_ Automaton
$A_{\psi}=(\mathcal{P},C_{\mathcal{P}},L,L_{0},E,\mathcal{L},\Delta,\mathcal{F})$,
with $\mathcal{P}$ the set of propositions used, $C_{\mathcal{P}}$ the set of
clocks, $L$ and $L_{0}$ the (initial) locations of $A_{\psi}$, a transition
relation $E\subseteq L\times L$, a labelling function $\mathcal{L}$ assigning
the propositions valid in it to every location of $L$, another labelling
function $\Delta$ assigning constraints over $C_{\mathcal{P}}$ to every
location of $L$ and a family of Büchi acceptance sets $\mathcal{F}$. From
there on a _Region-Automaton_ $\mathcal{R}(A_{\psi})$ [16][3] can be
constructed. Having operators to compare the time to for both the future and
the past, SC automata have a history clock $x_{p}$ and a prophecy clock
$y_{p}$ for each proposition $p\in\mathcal{P}$ in $C_{\mathcal{P}}$. Both
types of clocks need to be respected when constructing the region automaton. A
_region_ $[\nu]$ describes a class of clock valuations $\nu$ that cannot be
distinguished by any SC automaton and can be represented as a set of
(in-)equalities over the set of clock variables $x_{y},\ y_{p}$ and the
natural numbers $\mathbb{N}$. Iff the language of $\mathcal{R}(A_{\psi})$ is
not empty, the formula $\psi$ is satisfiable. In [5], we extended State-Clock
automata with _broadcast communication_ like the timed automata of UPPAAL
[12]. For a formal account on the broadcast communication used we refer to
[18] and only point out that sending some data $d$ over a channel $c$ is
denoted as $c!\langle d\rangle$ and receiving this data on the same channel is
denoted as $c?\langle d\rangle$. We also allowed simple functions dealing with
data structures and simple computations on the transitions of communicating SC
automata.

###  2.3 TMLSL

To express and reason about both spatial and timing properties in motorway
traffic, we introduced _TMLSL_ [4]. The idea of this logic is to use MLSLS-
formulae as the propositions that SCL formulae are build from. The intuitive
idea for the semantics is that a traffic snapshot $\mathit{TS}$ with a timed
word of actions $\omega$ is a model for a formula $\varphi$,
$\mathit{TS}_{0},\omega\vDash\varphi$ iff there is a timed sequence of states
$m(\mathit{TS}_{0},\omega)$ that is propositionally consistent and complete in
the subformulae of $\varphi$, describes the evolution of $\mathit{TS}$ along
$\omega$ and is a model of $\varphi$ in the SCL-semantics,
$m(\mathit{TS},\omega)\vDash_{SCL}\varphi$. We now give an example for a TMLSL
formula as well as their satisfaction. For simplicity, we use car identifiers
instead of car variables in the MLSLS propositions in the formula.

######  Example 1 (TMLSL).

Consider the TMLSL formula

$\varphi_{1}=\left\langle{\mathit{re}(A)}{\,\operatorname{\smallfrown}\,}\mathit{free}\land{l=21}{\,\operatorname{\smallfrown}\,}{\mathit{re}(B)}\right\rangle\implies\vartriangleright_{=5}{\left\langle{\mathit{re}(A)}{\,\operatorname{\smallfrown}\,}\mathit{free}\land{l=15}{\,\operatorname{\smallfrown}\,}{\mathit{re}(B)}\right\rangle}$

that specifies that when the distance between the reservations of the two cars
$A$ and $B$ is equal to $21$ distance units somewhere in the traffic snapshot,
it needs to be equal to $15$ distance units within exactly $5$ time units. A
satisfying sequence of states is

$\displaystyle
m=\langle(\left\langle{\mathit{re}(A)}{\,\operatorname{\smallfrown}\,}\mathit{free}\land{l=21}{\,\operatorname{\smallfrown}\,}{\mathit{re}(B)}\right\rangle,[0,0]),(\left\langle{\mathit{re}(A)}{\,\operatorname{\smallfrown}\,}\mathit{free}\land{l\leq
21\land
l>15}{\,\operatorname{\smallfrown}\,}{\mathit{re}(B)}\right\rangle,(0,5)),$
$\displaystyle(\left\langle{\mathit{re}(A)}{\,\operatorname{\smallfrown}\,}\mathit{free}\land{l=15}{\,\operatorname{\smallfrown}\,}{\mathit{re}(B)}\right\rangle,[5,7))\rangle,$

one that is not is

$\displaystyle
m^{\prime}=\langle(\left\langle{\mathit{re}(A)}{\,\operatorname{\smallfrown}\,}\mathit{free}\land{l=21}{\,\operatorname{\smallfrown}\,}{\mathit{re}(B)}\right\rangle,[0,0]),(\left\langle{\mathit{re}(A)}{\,\operatorname{\smallfrown}\,}\mathit{free}\land{l\leq
21\land
l>15}{\,\operatorname{\smallfrown}\,}{\mathit{re}(B)}\right\rangle,(0,5]),$
$\displaystyle(\left\langle{\mathit{re}(A)}{\,\operatorname{\smallfrown}\,}\mathit{free}\land{l=15}{\,\operatorname{\smallfrown}\,}{\mathit{re}(B)}\right\rangle,(5,7))\rangle,$

as the distance between the two cars reached the value $15$ too late. The only
difference between $m$ and $m^{\prime}$ are the shapes of the second and third
interval. Please note that we omitted some subformulae of $\varphi_{1}$ in the
sequences in an attempt to keep them readable.

Ex. 2 gives values for the positions, speeds and accelerations of the cars in
the first traffic snapshot $\mathit{TS}$ of Fig. 1 and a timed word of actions
$\omega$ s.t. applying $\omega$ to $\mathit{TS}$ results in the timed sequence
of states $m(\mathit{TS}_{0},\omega)$ that satisfies $\varphi_{1}$ written
$\mathit{TS},\omega\vDash\varphi_{1}$, resp.
$m(\mathit{TS}_{0},\omega)\vDash_{SCL}\varphi_{1}$.

######  Remark 2.

Using MLSLS formulae as the propositions of SCL rather than MLSL actions
imposes some difficulties, still some situations on the road can only be
described using formulae rather than action. Additionally, actions take zero
time in the model, so one could argue that they are not observable from the
outside. So for the cars on the motorway that we want to control, we have MLSL
actions as the input to them, but the system produces evolutions of traffic
snapshots as an output, which we observe through MLSLS formulae.

#### Finite Semantics

In [5], we introduced a finite semantics for TMLSL, suited for the finite
sequences that are usually available in runtime monitoring/enforcement and the
reality on motorways. Intuitively, a finite word of actions $\omega$ satisfies
a formula $\varphi$ in the finite semantics up to time $t$,
$\mathit{TS},\omega\vDash_{t}\varphi$ iff there exists at least one suffix
$m^{\prime}$ s.t. $m(\mathit{TS},\omega).m^{\prime}\vDash_{SCL}\varphi$ in the
infinite semantics.

##  3 Decidability Results

Regarding the decidability of TMLSL, we point out that the logic is at least
semi-decidable [4]. In answering this question, we considered maximum values
on the acceleration of the cars (from $\mathit{acc}_{min}$ to
$\mathit{acc}_{max}$) and the speed (from $0$ to $\mathit{spd}_{max}$), as in
the real world there are (at least) physical bounds, too. We do the same here.
The decidability results of SCL and MLSLS do not directly transfer to TMLSL,
as we need to interpret the SCL-propositions, which are MLSLS-formulae, and
the cars in the traffic snapshot may not be able to behave as specified in
TMLSL. One cause for only semi-decidability are the actions regarding the
dynamic behaviour along the lanes, the change of a car’s acceleration and the
passing of time. While it is easy to see what discrete actions need to be
executed and when, given a timed sequence of states $m$, it was unknown how
many acceleration changes are needed to achieve cars behaving correct with
respect to the lengths constraints specified in $m$. In this paper, we give an
algorithm that decides this question. Before doing so, however, we start with
an example (adjusted example of [4]):

######  Example 2.

Consider a traffic snapshot with one lane and two cars $A$ and $B$, $B$
driving ahead of $A$, where the distance between the two cars is equal to $21$
and both of them have a speed of $4$. For simplicity, we furthermore assume
that car $B$ cannot change its acceleration, it is fixed at $0$, the initial
acceleration of $A$ does not matter. For this traffic situation, we have a
specification expressing that the distance between the two cars needs to be
equal to $15$ within $5$ time units, formalised as the formula $\varphi_{1}$
from Ex. 1. Furthermore, assume that we have $\mathit{acc}_{min}=-10,\
\mathit{acc}_{max}=5$ and $\mathit{spd}_{max}=13$ as bounds on the dynamic
behaviour. In this example, there is no timed word of actions that allows the
traffic snapshot to behave as specified, if we only allow acceleration changes
at one point in time, as we either obtain a speed to fast or need to
accelerate stronger than the specified bounds allow. If we allow acceleration
changes at two points, there is a solution:
$\omega=\langle(\mathit{acc}(A,0.75),0),(\mathit{acc}(A,-6),4)\rangle$.
Letting one further time unit pass results in a distance exactly $15$.

As described in Sect. 2.1, the dynamics of each car $C$ evolves according to
the simple mechanical equation
$\mathit{pos}^{\prime}(C)=\mathit{pos}(C)+\mathit{spd}(C)\cdot
t+\frac{1}{2}\cdot\mathit{acc}(C)\cdot t^{2}$, with $t$ being the time that
elapses and $\mathit{pos}^{\prime}(C)$ the new position of $C$. The speed
evolves according to
$\mathit{spd}^{\prime}(C)=\mathit{spd}(C)+t\cdot\mathit{acc}(C)$.

For a finite timed sequence of states
$m=\langle(s_{0},I_{0}),\dots,(s_{m},I_{m})\rangle$ and a number $n$ of points
in which we can split the interval $I=[0,t]=\langle I_{0},\dots,I_{m}\rangle$,
we define $\mathit{DYN}(m,n,I)$ as the set of equations that describe the
solution space of $m$ on the (timing) interval $I$ for these $n$ splitting
points. In the equations listed below, we only consider the length
measurements/constraints that we need to satisfy in $s_{i}$, as the question
which discrete actions one need to execute between two phases is easy to
answer. We summarise these constraints as $\theta_{m}(t)$ for the length
constraints that occur in the phase $(s_{i},I_{i})$ of $m$ with $t\in I_{i}$.
Iff the difference in the position of any two cars affected by it satisfies
$\theta_{m}(t)$ at point $t$, we denote this as
$\Delta\mathit{pos}(t)\vDash\theta_{m}(t)$. Please note that $\theta_{m}(t)$
can consist of an arbitrary number of constraint, e.g. when we require that
the distance between two cars is smaller than some value and greater than some
other value, for example when we want to exclude (potential) collisions while
being quite close to the car in front. Additionally, $\theta_{m}(t)$ can
constrain the distance between more than two cars.

$\displaystyle\mathit{DYN}(m,n,I)=$ $\displaystyle\mathit{pos}_{0}(C)\text{
and }\mathit{spd}_{0}(C)\text{ are as in }\mathit{TS}_{0},$ (1)
$\displaystyle\mathit{pos}_{n}(C)=\mathit{pos}_{n-1}(C)+\mathit{spd}_{n-1}(C)\cdot
t_{n-1}\cdot\frac{1}{2}\cdot\mathit{acc}_{n-1}(C)\cdot t_{n-1}^{2},$ (2)
$\displaystyle\mathit{spd}_{n}(C)=\mathit{spd}_{n-1}(C)+\mathit{acc}_{n-1}(C)\cdot
t_{n-1},$ (3) $\displaystyle\forall t^{\prime}\in
I:\Delta\mathit{pos}(t)\vDash\theta_{m}(t)\text{ and}$ (4)
$\displaystyle\forall t^{\prime}\in I,\ \forall
C\in\mathit{cs}:\mathit{spd}_{t^{\prime}}(C)\text{ and
}\mathit{acc}_{t^{\prime}}(C)\text{ remain in the specified bounds.}$ (5)

An illustration of the solution space and a solution we are searching for for
two cars is depicted in Fig. 2. As one can see, we want to find out how many
splitting points there need to be such that the difference in the position of
the cars satisfies the spatial constrains $\theta_{i}$ of each phase
$(s_{i},I_{i})$ of $m$ as well as the constraints on the speeds of the cars.
The possible curves for the relative position that the evolution yields are
furthermore constrained by the maximal and minimal acceleration forces
possible. Initial values for the relative position and the speeds are fixed,
as they are determined by the traffic snapshot from which on we ask for a
satisfying sequence of actions. In the figure, we have both a maximum and a
minimum spatial constraint on the distance between the cars in each of the
phases. Please note that also a single constraint (distance is e.g. greater
than some value) or even no constraint (the distance between the cars is not
important in this phase) is possible. Despite being possible, the later one
should usually not occur because requiring collision freedom should always be
included in a specification, which immediately imposes length constraints.

If $\mathit{DYN}(m,n,I)$ is satisfied, $n$ splitting points are sufficient to
obtain a satisfying sequence of actions that satisfies the behaviour specified
by $m$. We furthermore need a relaxed version $\mathit{DYN}^{\prime}(m,n,I)$,
which is equivalent to $\mathit{DYN}$, except that we alter equation $(4)$ and
remove the length constraint on the last phase of $m$ not reached. Please note
that we can rewrite the equations $(4)$ and $(5)$ in an equivalent form that
does not use quantifiers, so we gain an easy to solve equation system not
dealing with quantifiers over infinite domains.

Later, we are interested how $\mathit{DYN}^{\prime}$ behaves when answering
the question whether or not there is a solution to $\mathit{DYN}$. For this
purpose, we denote with $\mathit{max\\_extension(DYN^{\prime})}$ the maximal
value $x$ s.t. $\mathit{DYN^{\prime}}(m,n,[0,x])$ has a solution. Similarly,
we denote with $\mathit{max\\_outcome\\_pos(DYN^{\prime})}$ the largest
interval $[y,y^{\prime}]$ s.t. $\mathit{DYN}^{\prime}(m^{\prime},n,I)$ has a
solution, where $m^{\prime}$ is identical to $m$ except that in the last
phase, the length constraints are replaced with $[y,y^{\prime}]$.
$\mathit{max\\_outcome\\_spd(DYN^{\prime})}$ is the largest interval
$[z,z^{\prime}]$ for the speed that a car can have when exceeding $I$ while
$\mathit{DYN}^{\prime}(m,n,I)$ still has a solution.

Despite not focusing on that topic, we would like to mention that both
$\mathit{max\\_outcome\\_pos(DYN^{\prime})}$ and
$\mathit{max\\_outcome\\_spd(DYN^{\prime})}$ are vectors, the first one over
the differences in positions that are compared in the phases and the second
one over the cars.

Figure 2: Dynamic Evolution of two cars on a timing interval with one
additional acceleration change for each car in between. For a sequence of
actions that satisfies the specification, all values need to stay inside the
specified intervals. For the relaxed version $\mathit{DYN}^{\prime}$, this
does not apply for the last length constraint ($\theta_{1}$ here).

Utilising the aforementioned equations, we now can give an answer to the
question whether or not there is a satisfying sequence of actions s.t. the
cars behave as specified:

######  Theorem 1 (Number of Accelerations).

Given a traffic snapshot $\mathit{TS}$ and timed sequence of states
$m=\langle(s_{0},I_{0}),\dots,(s_{n},I_{n})\rangle$ with adjacent intervals
$I_{i}$ and sets $s_{i}$ of lengths constraints $\theta$ between the cars to
achieve, one can decide after finitely many steps whether or not there is a
sequence of acceleration changes
$\omega=\langle(\alpha_{0},t_{0}),\dots,(\alpha_{n^{\prime}},t_{n^{\prime}})\rangle$
s.t. $m(\mathit{TS}_{0},\omega)=m$.

We can decide this question using Alg. 1.

Algorithm 1 Deciding Acceleration

1:Input: sequence of states $m=\langle p_{1},\dots,p_{m}\rangle$, Interval
$I=[0,t]$

2:$n\leftarrow 0;\ i\leftarrow 1;$

3:while $i\leq m$ do

4: $m^{\prime}\leftarrow\langle p_{1},\dots,p_{i}\rangle;$

5: while
$\mathit{max\\_extension(DYN^{\prime}(m^{\prime},I,n))}\neq\mathit{max\\_extension(DYN^{\prime}(m^{\prime},I,n+1))}$

6:
$\lor\mathit{max\\_outcome\\_pos(DYN^{\prime}(m^{\prime},I,n))}\neq\mathit{max\\_outcome\\_pos(DYN^{\prime}(m^{\prime},I,n+1))}$

7:
$\lor\mathit{max\\_outcome\\_spd(DYN^{\prime}(m^{\prime},I,n))}\neq\mathit{max\\_outcome\\_spd(DYN^{\prime}(m^{\prime},I,n+1))}$
do

8: $n\leftarrow n+1;$

9: end while

10: $i\leftarrow i+1;$

11:end while

12:if $\mathit{DYN(m,I,n)}$ has a solution then

13: return
$\langle(\mathit{acc}_{0}(C),t_{0}),\dots,(\mathit{acc}_{n}(C),t_{n})\rangle$
of $\mathit{DYN(m,I,n)}$ (for each car $C$)

14:else

15: return no Solution existent.

16:end if

######  Lemma 1 (Termination and Correctness).

Algorithm 1 terminates $\mathit{iff}$a solution is found and returns it or
there is no solution at all.

###### Proof.

(sketched) Alg. 1 subsequently maximises the outcome that the dynamics
(position and speed) may have after each phase of $m$, iterating through
prefixes $m^{\prime}$ of $m,$ solving $\mathit{DYN}^{\prime}$ for this prefix.
The first line of the second while-condition (line 4) ensures that we have
sufficiently many splitting points such that we reach the right (time) border
of the phase. Line 5 ensures that we maximise the difference in the position
between two cars at the end of the current phase $p_{i}$, where line 6
maximises the differences in their speeds. If none of these values increases
any further within one iteration, no further iteration will. Aborting then is
possible because the outcome of the dynamics is strictly monotone in the
number of splitting points and thus has converged against a solution that is
maximal for the phase. ∎

This result is needed in the next section:

##  4 Enforcement

We now present our – in comparison to [5]– enhanced runtime enforcement
approach, utilising the results from the previous section.

In this section, we show how cars can find actions to execute in a distributed
manner s.t. the overall evolution of the traffic snapshot satisfies the
specified properties up to some time bound. In distinction to previous work
[5], where the cars non-deterministically guessed actions to execute, they now
only propose timed sequences of states that are valid at least for their own
properties. The proposed sequences $\Pi_{C}$ are afterwards – either by one of
the cars or by another central entity – combined into a set of timed sequences
of states $\Pi$, where each sequence represents a combined behaviour of all
cars. It is then checked for the existence of a satisfying sequence of actions
$\omega$. If existent, the participating cars get informed over the timed
actions $\omega_{c}$ they themself must execute to comply to $\omega$.

As the sequences $\Pi$ are in the end checked by a single entity, one could
argue that it would be easier to refrain from having the specification
distributed over all cars. There are, however, several benefits that one gains
when using the more distributed approach. First of all, the whole
specification does not need to be known beforehand, neither to the other cars
nor to the entity that checks if there is a satisfying sequence of actions.
Being able to handle such cases is one big strength of runtime enforcement
approaches. Additionally, only the specification up to some time bound needs
to be known, not the behaviour beyond that timed horizon, which might not be
of interest to the others. Therefore, each car knows its whole specification
completely and the central entity/other cars just enough to fulfil its/their
task(s). While this argument mostly aimed at privacy concerns, we can also
consider it in the light of complexity: The size of the region automaton is
exponential in the size of the corresponding SC automaton, which itself is
exponential in the size of the specification in SCL. When we considers that
only the behaviour up to some time bound is of interest to us, a central SC
automaton or even worse, region automaton, would be unnecessary large.

We now focus on the question wherefrom the cars know which timed sequences of
states to announce. This includes getting sequences of regions first (Lemma.
2) and computing a satisfying timed sequence of states from them (Lemma. 3).

Before doing so, we would like to mention some results from [5]: Given an
region automaton $\mathcal{R}(A_{\psi})$ for a specification $\psi$ in SCL,
one can label some of the states as _bad_ , these are the once that, if
reached, do not allow the run of the region automaton to be extended in a way
that allow $\psi$ to get satisfied. Vice versa, if a sequence ends in a state
that is not bad, one can extend it in a way s.t. $\psi$ is satisfied.

The second case, however, does not hold if we consider specifications
$\varphi$ in TMLSL rather than SCL: Here, it can be the case that the region
automaton claims that there is an extension s.t. $\varphi$ is satisfied, but
the cars are not able to behave in a way that conforms to this extension.
Thus, the sequences of regions that the region automaton suggests as
satisfiable might actually not be satisfiable (but are candidates):

######  Lemma 2 (Sequences of regions as potential solutions).

In every traffic snapshot $\mathit{TS}$, one can compute the set $\Pi$ of
sequences of regions $\pi=\langle[\nu_{i}],\dots,[\nu_{j}]\rangle$ that start
with the region $[\nu_{i}]$ reached in the region automaton
$\mathcal{R}(A_{\varphi})$ in the evolution towards $\mathit{TS}$ and are
candidates for satisfying runs of the region automaton. Moreover, there is no
sequence $\pi^{\prime}$ not in $\Pi$ but with
$m(\pi^{\prime})\vDash_{t}\varphi$.

###### Proof.

Using Def. 3 of [5], we can compute the set of locations
$\\{l_{0},\dots,l_{n}\\}$ that the SC automaton $A_{\varphi}$ reaches along
the evolution towards $\mathit{TS}$. Each location
$l\in\\{l_{0},\dots,l_{n}\\}$ corresponds to a set of regions
$\\{[\nu_{1}],\dots,[\nu_{m}]\\}$, with $[\nu_{i}]\vDash\Delta_{x}(l)$ that
is, the region $[\nu_{i}]$ satisfies the clock constraints over the history
clocks of the location $l$ and especially $p\in\mathcal{L}(l_{i})\
{\mathit{iff}}\ [\nu_{i}](p)=0$ for every proposition $p$. We ignore
constraints over the prophecy clocks here, because the future is (at least at
the end of the sequence) unknown and the history clocks are sufficient for
determining the intervals. ∎

Given a sequence of regions, we can compute a timed sequence of states that
satisfies the sequence of regions:

######  Lemma 3 (From regions to timed sequences of states).

For every sequence of regions $\pi=\langle[\nu_{0}],\dots,[\nu_{n}]\rangle$
one can construct a timed sequence of state
$m(\pi)=\langle(s_{0},I_{0}),\dots,(s_{m},I_{m})\rangle$ s.t. $m\vDash\pi$.

###### Proof.

For simplicity, we assume that there is a global clock that is not reset,
counting the time from the beginning of the sequence. Starting with
$[\nu_{0}]$ and subsequently going trough all $[\nu_{i}]$, we determine for
each point in time $t$ which propositions $p$ are valid in it, which is
achieved by looking at formulae of the form $x_{p}=0$. To determine the shape
of the intervals ($[],(),[)\text{ or }(]$), we consider the (in-)equalities in
the regions: If some $p$ is valid in the next point in time, $y_{p}=1$ leads
to a closed interval border (“]”), $y_{p}<1$ leads to an open one (“)”). We do
the same for the history clocks $x_{p}$. ∎

As all cars announce timed sequences of states, we need to combine them into a
single sequence that the central entity can check:

######  Lemma 4 (Combining Sequences of states).

Given two finite timed sequences of states $m_{1}$ and $m_{2}$, one can
construct a timed sequence $m$ s.t. for every $\varphi:\
m_{1}\vDash\varphi\lor m_{2}\vDash\varphi\implies m\vDash\varphi$.

###### Proof.

We start with an “empty” sequence
$m=\langle(\\_,[0,0]),(\\_(0,1)),(\\_,[1,1]),(\\_,(1,2)),\dots(\\_,I_{n})\rangle$.
Going through each state $(\\_,I_{i})$ of $m$, we look in both $m_{1}$ and
$m_{2}$ and insert the propositions from the states $(s_{j},I_{j})$, where
$I_{j}$ contains $I_{i}$. If it happens that for some two neighbouring states
$(s_{i},I_{i})$ and $(s_{i+1},I_{i+1}),\ s_{i}=s_{i+1}$ holds, we can fuse the
two into a single state $(s_{i},I_{i}+I_{i+1})$. As a last step, we check if
the resulting sequence is consistent. If it happens that there is a
contradiction in one of the states, say ${\mathit{cl}(A)}$ and
$\lnot{\mathit{cl}(A)}$ need to hold in the same (time) interval, the timed
sequence of states cannot be satisfied at all and is thus invalid. ∎

Please note that the other direction not necessarily holds, as e.g. $p1\land
p_{2}$ could hold in $[1,1]$ of $m$, but in $m_{1}$ only $p_{1}$ and in
$m_{2}$ only $p_{2}$ holds in the respective interval.

We utilise the aforementioned results in the controllers of the cars and the
central entity that determines whether a solution exists. The controller is
depicted in Fig. 3 and the central entity $\mathit{RSU}$ (Road-Side Unit) in
Fig. 4.

$q_{0}$$q_{1}$$q_{2}$$q_{3}$Y1.0e0]pt$\mathit{com}?\langle(\alpha,t)\rangle$$\mathcal{R}.\mathit{update}(\alpha,t)$Y1.0e0]pt$\mathit{send!}\langle\Pi_{C}\rangle$$\mathit{receive}?\omega=\langle(\alpha_{0},t_{0}),\dots,(\alpha_{n},t_{n})\rangle$$\mathit{execute\\_and\\_remove\
first}(\omega)$$\mathit{is\\_empty}(\omega)$ Figure 3: Controller for each car
$C$, each is equipped with an instance of it. The controller keeps track of
the traffic situation in $q_{0}$ and updates the sequences it could announce
accordingly. When announcing the sequences $\Pi_{C}$, it proceeds to $q_{1}$
and waits for a positive response from the central entity and executes the
sequence of actions $\omega$ that it received from there, until there are not
further actions to execute. Please note that we omitted clock constraints to
actually force the controller to leave a state.

Both of them use several functions on their transitions. In the controller,
$\mathcal{R}.\mathit{update}(\alpha,t)$ is used so that the internal region
automaton keeps track about the behaviour on the road and thus is in the
correct state(s), before the enforcement mechanism is triggered. In this
location, we may already have an evolution that leads to a state s.t. all
further extensions are unsatisfiable. If such a behaviour is undesired,
constraints should be added s.t. one does not stay in this location.
$\mathit{execute\\_and\\_remove\\_first}(\omega)$ takes the first time stamped
action $(\alpha_{1},t_{1})$ from the action sequence
$\omega=\langle(\alpha_{1},t_{1}),\dots,(\alpha_{n},t_{n})\rangle$, waits
until the clock reaches $t_{1}$ and executes $\alpha_{1}$. Afterwards, this
element is removed from $\omega$, so that the next action is ready to be
executed. $\mathit{is\\_empty}(\omega)$ is true for the empty sequence
$\langle\rangle$.

In $\mathit{RSU}$, the function $\mathit{D.push}(\Pi_{C})$ is used to
internally store the announced sets of timed sequences of states $\Pi_{C}$ for
each car $C$ in some data structure $D$. The set of sequences representing all
possible satisfying sequences for all cars is constructed using
$\mathit{combine}(C_{1},\dots,C_{n})$ and stored in $\Pi$. Using Alg. 1, it
can then decide whether or not one of the sequences in $\Pi$ is one for which
there is a satisfying sequence of actions. If so, the solution $\omega$ is
computed and afterwards split into single solutions $\omega_{c}$ for each car
$c$, so that every car only gets informed of the actions it itself has to
execute. After informing a car, it is removed from the data structure $D$.

$p_{0}$$p_{1}$$p_{2}$$p_{3}$$p_{4}$Y1.0e0]pt$\mathit{send}?\langle\Pi_{C}\rangle$$\mathit{D.push}(\Pi_{C})$Y1.0e0]pt$\Pi:=\mathit{combine}(\Pi_{C_{1}},\dots,\Pi_{C_{n}})$Y1.0e0]pt$\Pi\mathit{\
is\ sat.}$$\mathit{with\ solution}$$\omega$$\Pi\ \mathit{not\
sat.}$Y1.0e0]pt$\mathit{inform}(\omega_{c})$$C.\mathit{remove(c)}$$\mathit{is\\_empty}(C)$
Figure 4: Central Entity $\mathit{RSU}$. $\mathit{RSU}$ waits in $p_{0}$ for
announced sequences $\Pi_{C_{i}}$ from the cars and combines them into a
single set of sequences $\Pi$, which it than can check for a satisfying run.
If positively answered, it sends the sequence to execute to each car.

The communication takes place over the channels $\mathit{com}$, over which the
cars announce action they execute before the enforcement mechanism is
triggered. Channel $\mathit{send}$ is used to inform $\mathit{RSU}$ about the
possible plans $\Pi_{c}$ of each car. $\mathit{receive}$ is used for the
opposite direction, informing the cars which actions to execute.

######  Theorem 2 (Correct- and Soundness).

If the controller from Fig. 3 proceeds to location $q_{3}$, the specification
of all cars is satisfied up to the given time bound $t$. If it cannot proceed
to location $q_{3}$, then there is no sequence of actions for the cars to take
that respects the specification of all cars.

###### Proof.

Due to Lemma 2, we get all possible satisfying sequences of regions of cars.
Due to Lemma 3, we can compute equivalent timed sequences of states from them.
Lemma 4 lets us combine them towards some $\Pi$ on the transition from $p_{0}$
to $p_{1}$ in $\mathit{RSU}$ s.t. all possible combinations of solutions for
all cars are considered. Each of them is checked using Alg. 1, so the due to
Lemma 1, the solution found is a correct one. ∎

If $\mathit{RSU}$ reaches location $p_{3}$, the specification is
unsatisfiable, so there is no sequence of actions for the cars to execute. In
this case collision freedom can still be guaranteed (assuming that there were
no collisions yet), as the reservations of the cars occupy a space big enough
to come to a standstill within that space.

######  Remark 3 (Number of sequences to consider).

If all cars announce all timed sequences of states that satisfy their
specification, the central entity/road-side unit needs to check all
combinations of these sequences (with exactly one sequence in the combination
for each car), resulting in a lot of computation. However, these computations
do not depend on each other and can thus be parallelised. If we consider that
the cars themself compute this, rather than some road cite unit, one can think
of a more advanced protocol than the one proposed here, where the cars
distribute the sequences to check and thus the computational effort between
each other.

######  Remark 4 (Discrete Actions).

Through both Sect. 3 and Sect. 4, we only considered how the cars can change
their accelerations to ensure that they satisfy the length measurements in the
specification, ignoring the discrete actions completely. As said, given a
timed sequence of states, it is easy to see what discrete actions are to
execute when, as they directly change the formulae valid and thus the phase.
Some of them, however, need to be respected when constructing the length
comparisons $\theta_{i}$ that we check in $\mathit{DYN}$.

##  5 Conclusion

#### Contribution

In this paper, we proposed a runtime enforcement approach for autonomous car
in motorway traffic, employing communication between the cars, where the
knowledge about the satisfaction of a property is represented using a region
automaton. In answering the question whether or not a specification (now in
the form of a timed sequence of states) is satisfiable, we were able to
eliminate one of the roots for the semi-decidability of the satisfiability
problem of TMLSL.

#### Future Work

Future work on the topic includes studying the satisfiability problem of TMLSL
again, in an effort to show that the logic is indeed decidable over infinite
runs. Further topics also include the extension of the logic and the proposed
runtime enforcement approach towards the aforementioned more complex road
topologies. Both of them offer some challenges in the semantics and runtime
enforcement, as their models are more complicated that the ones for motorway
traffic. For urban traffic, the assumption that there is a central entity that
all cars can communicate with is not too far from reality, as on almost all
intersections traffic lights are present, some of which already communicate
with the buses that cross/approach them.

Steps towards an implementation for solving the decidability problem of
$TMLSL$ were made and could be adjusted to be used in the runtime enforcement
setting. With an implementation, we could also examine if the proposed
approach is suited for real-time applications like car control on motorways,
e.g. the computation happens fast enough.

#### Acknowledgements.

We thank the anonymous reviewers for their helpful comments.

## References

  * [1]
  * [2] Matthias Althoff, Sebastian Maierhofer & Christian Pek (2021): _Provably-Correct and Comfortable Adaptive Cruise Control_.  IEEE Trans. Intell. Veh. 6(1), pp. 159–174, 10.1109/TIV.2020.2991953.
  * [3] Rajeev Alur & David L. Dill (1994): _A Theory of Timed Automata_.  Theor. Comput. Sci. 126(2), pp. 183–235, 10.1016/0304-3975(94)90010-8.
  * [4] Christopher Bischopink & Ernst-Rüdiger Olderog (2022): _Spatial and Timing Properties in Highway Traffic_.  In Helmut Seidl, Zhiming Liu & Corina S. Pasareanu, editors: Theoretical Aspects of Computing - ICTAC 2022 \- 19th International Colloquium, Tbilisi, Georgia, September 27-29, 2022, Proceedings, Lecture Notes in Computer Science 13572, Springer, pp. 114–131, 10.1007/978-3-031-17715-6_9.
  * [5] Christopher Bischopink & Ernst-Rüdiger Olderog (2023): _Time for Traffic Manoeuvres_ , pp. 163–179.  Springer Nature Switzerland, Cham, 10.1007/978-3-031-40132-9_11.
  * [6] Christopher Bischopink & Maike Schwammberger (2019): _Verification of Fair Controllers for Urban Traffic Manoeuvres at Intersections_.  In Emil Sekerinski, Nelma Moreira, José N. Oliveira, Daniel Ratiu, Riccardo Guidotti, Marie Farrell, Matt Luckcuck, Diego Marmsoler, José Creissac Campos, Troy Astarte, Laure Gonnord, Antonio Cerone, Luis Couto, Brijesh Dongol, Martin Kutrib, Pedro Monteiro & David Delmas, editors: Formal Methods. FM 2019 International Workshops - Porto, Portugal, October 7-11, 2019, Revised Selected Papers, Part I, Lecture Notes in Computer Science 12232, Springer, pp. 249–264, 10.1007/978-3-030-54994-7_18.
  * [7] Martin Fränzle, Michael R. Hansen & Heinrich Ody (2015): _No Need Knowing Numerous Neighbours - Towards a Realizable Interpretation of MLSL_.  In Roland Meyer, André Platzer & Heike Wehrheim, editors: Correct System Design, Lecture Notes in Computer Science 9360, Springer, pp. 152–171, 10.1007/978-3-319-23506-6_11.
  * [8] Klaus Havelund & Allen Goldberg (2008): _Verify Your Runs_ , pp. 374–383.  Springer Berlin Heidelberg, Berlin, Heidelberg, 10.1007/978-3-540-69149-5_40.
  * [9] Martin Hilscher, Sven Linker & Ernst-Rüdiger Olderog (2013): _Proving Safety of Traffic Manoeuvres on Country Roads_.  In Zhiming Liu, Jim Woodcock & Huibiao Zhu, editors: Theories of Programming and Formal Methods - Essays Dedicated to Jifeng He on the Occasion of His 70th Birthday, Lecture Notes in Computer Science 8051, Springer, pp. 196–212, 10.1007/978-3-642-39698-4_12.
  * [10] Martin Hilscher, Sven Linker, Ernst-Rüdiger Olderog & Anders P. Ravn (2011): _An Abstract Model for Proving Safety of Multi-lane Traffic Manoeuvres_.  In Shengchao Qin & Zongyan Qiu, editors: Formal Methods and Software Engineering - 13th International Conference on Formal Engineering Methods, ICFEM 2011, Durham, UK, October 26-28, 2011. Proceedings, Lecture Notes in Computer Science 6991, Springer, pp. 404–419, 10.1007/978-3-642-24559-6_28.
  * [11] Kim Guldstrand Larsen, Marius Mikucionis & Jakob Haahr Taankvist (2015): _Safe and Optimal Adaptive Cruise Control_.  In Roland Meyer, André Platzer & Heike Wehrheim, editors: Correct System Design, September 8-9, 2015. Proceedings, Lecture Notes in Computer Science 9360, Springer, pp. 260–277, 10.1007/978-3-319-23506-6_17.
  * [12] Kim Guldstrand Larsen, Paul Pettersson & Wang Yi (1997): _UPPAAL in a Nutshell_.  Int. J. Softw. Tools Technol. Transf. 1(1-2), pp. 134–152, 10.1007/s100090050010.
  * [13] Sarah M. Loos, André Platzer & Ligia Nistor (2011): _Adaptive Cruise Control: Hybrid, Distributed, and Now Formally Verified_.  In Michael J. Butler & Wolfram Schulte, editors: FM 2011: Formal Methods - 17th International Symposium on Formal Methods, Limerick, Ireland, 4, 2011. Proceedings, Lecture Notes in Computer Science 6664, Springer, pp. 42–56, 10.1007/978-3-642-21437-0_6.
  * [14] Heinrich Ody (2015): _Undecidability Results for Multi-Lane Spatial Logic_.  In Martin Leucker, Camilo Rueda & Frank D. Valencia, editors: Theoretical Aspects of Computing - ICTAC, Lecture Notes in Computer Science 9399, Springer, pp. 404–421, 10.1007/978-3-319-25150-9_24.
  * [15] Heinrich Ody (2020): _Monitoring of traffic manoeuvres with imprecise information_.  Ph.D. thesis, University of Oldenburg, Germany.  Available at https://oops.uni-oldenburg.de/4730.
  * [16] Jean-François Raskin & Pierre-Yves Schobbens (1997): _State Clock Logic: A Decidable Real-Time Logic_.  In Oded Maler, editor: Hybrid and Real-Time Systems, International Workshop. HART’97, Grenoble, France, March 26-28, 1997, Proceedings, Lecture Notes in Computer Science 1201, Springer, pp. 33–47, 10.1007/BFb0014711.
  * [17] Fred B. Schneider (2000): _Enforceable security policies_.  ACM Trans. Inf. Syst. Secur. 3(1), pp. 30–50, 10.1145/353323.353382.
  * [18] Maike Schwammberger (2018): _An abstract model for proving safety of autonomous urban traffic_.  Theor. Comput. Sci. 744, pp. 143–169, 10.1016/j.tcs.2018.05.028.
  * [19] Maike Schwammberger (2018): _Introducing Liveness into Multi-lane Spatial Logic lane change controllers using UPPAAL_.  In Mario Gleirscher, Stefan Kugele & Sven Linker, editors: Proceedings 2nd International Workshop on Safe Control of Autonomous Vehicles, SCAV@CPSWeek 2018, Porto, Portugal, 10th April 2018, EPTCS 269, pp. 17–31, 10.4204/EPTCS.269.3.
  * [20] J. C. P. Woodcock & Jim Davies (1996): _Using Z - specification, refinement, and proof_.  Prentice Hall international series in computer science, Prentice Hall.


Thermodynamics and Energy Technology Laboratory (ThEt),
University of Paderborn, Warburger Str. 100, 33098 Paderborn, Germany

# Molecular simulation of fluid dynamics on the nanoscale

Jadran Vrabec111Corresponding author: Prof. Dr.-Ing. habil. Jadran Vrabec
<EMAIL_ADDRESS>phone +49 5251 602 421. Elmar Baumhögger  Andreas
Elsner  Martin Horsch
Zheng Liu (gbsn刘峥)  Svetlana Miroshnichenko  Azer Nazdrajić & Thorsten
Windmann

###### Abstract

Abstract: Molecular dynamics simulation is applied to Poiseuille flow of
liquid methane in planar graphite channels, covering channel diameters between
3 and 135 nm. On this length scale, a transition is found between the regime
where local ordering induced by the wall dominates the entire system and
larger channel diameters where the influence of boundary slip is still
present, but of a more limited extent. The validity of Darcy’s law for
pressure-driven flow through porous media is not affected by the transition
between these regimes.

###### keywords:

Keywords: Molecular dynamics, boundary slip, microporous and nanoporous media

On the nanometer length scale, continuum approaches like the Navier-Stokes
equation break down, cf. Karnidiakis et al. (2005). Therefore, the study of
nanoscopic transport processes requires a molecular point of view and
preferably the application of molecular dynamics (MD) simulation.

In the past, MD could be applied to small systems with a few thousand
particles only, due to the low capacity of computing equipment. Consequently,
a large gap between MD simulation results on the one hand and experimental
results as well as calculations based on continuum methods was present. The
constant increase in available computational power is eliminating this
barrier, and the characteristic length of the systems accessible to MD
simulation approaches micrometers, see also Bernreuther and Vrabec (2005) for
a discussion of efficient massively parallel simulation algorithms and their
implementation.

The present work deals with the flow behavior of liquid methane, modeled by
the truncated and shifted Lennard-Jones (LJTS) potential, cf. Allen and
Tildesley (1987), confined between graphite walls. While the LJTS potential
can also be applied to the interaction between the solid wall and the fluid,
the carbon structure itself is modeled using a rescaled variant of the Tersoff
(1988) multi-body potential. The unlike interaction parameters of the LJTS
potential acting between methane and carbon were determined according to the
Lorentz-Berthelot combination rule with the Lennard-Jones parameters of Wang
et al. (2000) for ‘pure’ sp2 configured carbon.

MD simulations of methane confined between graphite walls with up to 4,800,000
interaction sites, i.e. carbon atoms and methane molecules, were conducted
while the channel diameter was varied to include both the boundary-dominated
regime and the transition to the continuum regime. A pressure gradient was
induced by an external gravitation-like acceleration acting on all methane
molecules and a force in the opposite direction acting on the carbon atoms of
the graphite wall. The flow was regulated using a proportional-integral
controller such that the wall velocity was zero while the fluid reached a
specified average velocity.

The fluid-solid interaction induces a local ordering in the vicinity of the
wall. For channel diameters below 5 nm, cf. Fig. 1, this effect determines the
structure of the entire system. The resulting velocity profile is affected by
the local structure and therefore does not exhibit an exactly parabolic shape.
However, aggregated quantities such as the slip velocity and the slip length,
serving as boundary conditions for higher-order CFD methods and in particular
for Navier-Stokes solvers, can be determined by extrapolating a parabolic fit
as shown in Fig. 2.

Figure 1:  Density profile for liquid methane at a temperature of 175 K in
confined within a planar graphite channel with a diameter of 3 nm from MD
simulation, averaged over the time intervals from 60 to 120 ps (– –) and from
420 to 480 ps (—) after simulation onset.  Figure 2:  MD simulation results
$\mathrm{(\textnormal{---})}$ with a parabolic fit ($\cdot\cdot\cdot$) for the
velocity profile during Poiseuille flow of liquid methane through a planar
graphite channel with a diameter of 8.5 nm for an average flow velocity of 50
m/s at a density of 19 $\pm$ 1 mol/l in the central region of the channel and
a temperature of 166.3 K.

For channel diameters between 20 and 50 nm, the boundary slip undergoes a
qualitative transition, cf. Fig. 3. In an extremely narrow channel the regular
ordering of the fluid molecules due to the vicinity of the wall entirely
dominates not only the static structure, but also the fluid dynamics. With
respect to the characteristic direction of the system, this highly ordered
structure does not support the extreme velocity gradient that would be implied
by the no-slip condition.

However, down to molecular length scales, the pressure drop
$-\Delta\mathnormal{p}/\Delta\mathnormal{z}$ is approximately proportional to
the average velocity $\bar{\mathnormal{v}}_{\mathnormal{z}}$ and inversely
proportional to the cross-sectionional area of the channel, cf. Fig. 3, in
agreement with Darcy’s law. Therefore, it can be concluded that the
qualitative transition between boundary-dominated laminar flow and laminar
flow which is only influenced by boundary slip to a certain extent is not
reflected by a corresponding change for the effective adhesive forces acting
between the fluid and the solid.

Figure 3: Pressure drop $-\Delta\mathnormal{p}$ in terms of
$\bar{\mathnormal{v}}_{\mathnormal{z}}$ and the channel length
$\Delta\mathnormal{z}$ (top) as well as slip velocity in terms of
$\bar{\mathnormal{v}}_{\mathnormal{z}}$ (bottom), for Poiseuille flow of
saturated liquid methane at a temperature of $\mathnormal{T}$ = 166.3 K and
average velocities $\bar{\mathnormal{v}}_{\mathnormal{z}}$ of 10 m/s (circles)
and 30 m/s (bullets), in dependence of the channel width; solid line: Darcy’s
law.

The authors would like to thank M. Bernreuther (Stuttgart), M. Buchholz
(Munich), J. Harting (Eindhoven), H. R. Hasse (Kaiserslautern), S. Jakirlić
(Darmstadt), and T.-H. Yen (Tainan) for technical support as well as fruitful
discussions and the German Federal Ministry of Education and Research (BMBF)
for funding the project IMEMO. The presented research was carried out under
the auspices of the Boltzmann-Zuse Society of Computational Molecular
Engineering (BZS) and the simulations were performed on the Nehalem cluster
laki at the High Performance Computing Center Stuttgart (HLRS) under the grant
MMSTP.

## References

  * Allen, M. P. & Tildesley, D. J. 1987 Computer Simulation of Liquids, Clarendon, Oxford.
  * [1] Bernreuther, M. & Vrabec, J. 2005 Molecular simulation of fluids with short range potentials. High Performance Computing on Vector Systems, Springer, Heidelberg, pp. 187-195.
  * [2] Giovambattista, N., Debenedetti, P. G. & Rossky, P. J. 2007 Effect of surface polarity on water contact angle and interfacial hydration structure. J. Phys. Chem. B, Vol. 111, pp. 9581-9587.
  * [3] Karnidiakis, G., Beskok, A. & Aluru, N. 2005 Microflows and Nanoflows: Fundamentals and Simulation, Springer, New York.
  * [4] Tersoff, J. 1988 Empiric interatomic potential for carbon, with applications to amorphous carbon. Phys. Rev. Lett., Vol. 61, pp. 2879-2882.
  * [5] Wang, Y., Scheerschmidt, K. & Gösele, U. 2000 Theoretical investigations of bond properties in graphite and graphitic silicon. Phys. Rev. B, Vol. 61, pp. 12864-12869.