[阅读笔记] 2019 ICRA - Coordinated multi-robot planning while preserving individual privacy

🛣[阅读笔记] 2019 ICRA - Coordinated multi-robot planning while preserving individual privacy

• 本文介绍了一种隐私保护的协作多机器人路径规划方法，使用了安全计算几何、混淆电路、同态加密等密码学技术，实现了在不共享🙅🏻‍♀️机器人🤖规划路径的前提下的路径碰撞检测方法。

• 算法具体细节介绍见我的下一篇笔记：本文解释一下安全多方计算技术是如何在不泄露两个机器人未来路径的基础上实现对碰撞预测的。

• 🙋‍♂️张同学 📧zhangruiyuan@zju.edu.cn 有问题请联系我~

一、⚽️ Introduction

⛳️ 在不纰漏机器人🤖的路径前提下，实现路径的规划是一个重要的课题：

• 🚗 不同的公司的飞行器🛩之间存在碰撞💥可能性，如在不泄露隐私下仍能做好规划是最理想的解决办法。

  An obstacle to the widespread commercial use of small Unmanned Aerial Vehicles (UAVs) is the potential for collisions, not only against each other but also against larger manned aircraft [1]. As various airborne vehicles are owned and operated by different companies and stake- holders, it would be ideal if one could provide assurances of collision-free paths without mandating the disclosure of information that some parties would be uneasy revealing.

• 🚕 假设某一台机器人🛫被绑架的场景下，隐私保护的路径🚞规划能够实现路径信息不会泄露。

  Consider a covert mission against some adversary where multiple robots must coordinate, for example, to ren- dezvous behind enemy lines. In the event of one of the robots being abducted or compromised, we would like guarantees that any information that might be extracted from the captured agent will not make the other robots vulnerable.

⛳️ 本文的贡献：

This is one of the first implementations of SMC in Robotics.

• 🚗 一种路径碰撞判断的密码学原子⚛协议

  A secure path intersection protocol based on the polygon intersection ideas presented in [5] and simplifie to make its implementation feasible using open source software packages.

• 🚕 一种用来确保两个机器人🤖不会相撞的原子⚛协议，以及其软件模拟实验、硬件实验

  A protocol that ensures that two robots will not collide while executing their task, its software implementation, and hardware proof of concept experiments.

• 🚙 一种考虑时间因素⏰、3D空间条件下的碰撞💥协议

  A new, secure 3D path collision protocol that can be used in plans involving time or 3D workspaces.

二、🏀 Related Work

⛳️ 本文作者的动机来源介绍&本文所用的基本技术介绍：

• 🚗 多方安全计算领域是本文的动机

  The motivation of our work comes from the area of Secure Multi-Party Computations [2], [3] where a group of players needs to compute a joint function without disclosing their inputs.

• 🚕 为了解决隐私保护下的路径规划，本文从安全计算几何中获得了灵感，本文的工作(3D路径判断原语、SMC实践系统)建立在「在安全计算几何中使用的一些原语：Yao’s millionaires, Garbled Circuits, 1-out-N oblivious transfer, and Homomorphic Encryption」的基础上。

  In particular, due to the close connection of planning algorithms to Computational Geometry, our ideas take inspiration from Secure Computational Geometry [7], [5], [8], [9], [10] that proposes geometric constructions to computational problems involving intersections [5] (point in polygon, polygonpolygon intersection) or based on distance [7] (distance be- tween parametric equations and line segments). These secure geometric constructions use the primitives such as Yao’s millionaires, Garbled Circuits, 1-out-N oblivious transfer, and Homomorphic Encryption. In our work, we build our protocols on top of some of these primitives, specifically from [5] and simplify them to implement using open source software and inexpensive robot platforms.

⛳️ 其他学者们的工作：

• 🚗 安全领域

  Security issues in multi-robot networks have been the focus of recent research [12], [13].

  • ⭐️ In [13], defense mech- anisms for Sybil attacks have been proposed and imple- mented in commodity Wi-Fi radios. Their approach has also been tested in mobile robotic platforms.

• 🚕 隐私保护领域

  Privacy issues related to robots have also been investigated in several recent works [14], [15], [16].

  • ⭐️ Among the investigated robotic privacy techniques, a differential privacy model is proposed in [16] for swarms of heterogeneous robots,
  • ⭐️ also, combinatorial filters are designed in [14] satisfying privacy
  • ⭐️ and utility constraints which have been explored for the privacy- preserving target tracking [15].

三、🏈 Preliminaries

本章首先在A部分对模型进行抽象定义，然后将本文要解决的问题具体成下面B部分中表述的3条。

A. 🍏 Model Definition

The robots move in a $2-D$​​​​​ workspace$ W = R2$​​​​​​. The free space of the environment is defined as $E=W\backslash O$​​​​​, where $O\subset R2$​​​​​​. We initially have two robots Alice and Bob that operate in a shared environment. Both robots have a representation of the environment $E$​​​​​, can plan obstacle-free paths in the environment, and can communicate with each other. Let $P_A$​​​​​ be the path of Alice and $P_B$​​​​​ be the path of Bob.

我这里有一个疑问：为啥环境的空闲需要 $E=W\backslash O$ 这样表示，emmm，我很懵，希望有大佬能帮我回答一下。

B. 🍎 Problem Formulation

首先，需要一个不泄露隐私的方法来判断路径是否能碰撞在一起。

In our first primitive, we require a privacy-preserving mechanism to allow for Alice and Bob to determine whether their paths (PA and PB) collide without revealing the path information to the other party. We propose to do this in a decentralized fashion and without relying on the existence of any trusted third-party. These constraints motivate our first problem of interest.

🥇 Problem 0. Privacy-Preserving Path Intersection:

本文需要解决的第〇个问题：如何在不共享数据的情况下判断路径是否是存在交点

Given two robots, Alice and Bob with paths PA and PB, inform the robots whether the paths have at least one point of intersection without sharing the path information.

本文需要解决的第二个问题，我个人觉得下面的「保护隐私的持续监控 」这个问题表达的是「持续监控两个机器人🤖的网络通信吧，emmm」

We will use the above problem as a building block for solving more pragmatic tasks in a privacy-preserving fashion. We are interested in a continuous monitoring task where both robots are executing the task but need to guarantee collision avoidance. This motivates the following problem of interest.

🥈 Problem 1. Privacy-Preserving Persistent Monitoring:
Given two robots Alice and Bob that are executing a mission in E, ensure, without sharing any information about their paths or position, that they will not collide.

为了解决3D场景下、考虑时间参数的情况下的碰撞，提出了下面的问题

We are also interested in problems involving time- parametrized trajectories. For this purpose, we need to con- struct secure primitives to calculate if two 3D line segments intersect. This primitive will allow us to solve the following problem

🥉 Problem 2. Ascertaining Rendezvous Securely:

There are two robots, Alice and Bob, and each of them has a time-parametrized trajectory. They want to know if their paths intersect without sharing either respective paths or the intersection point and time.

四、⚾️ Method

本章将解决上第三章中定义的问题

本章需要请你阅读原文了，这里只给出了主要的点子~

A. 🍏 Privacy-Preserving Path Intersection

本节给出了判断路径是否存在交互点的原子协议

🏓 为什么要使用同态加密算法呢？

为了避免路径信息泄露

So far, if Alice sends $m,p_A,q_A$ to Bob, Bob can easily compute $i,i^{\prime },j,j^{\prime }$​ and do the intersection determination logic and finally send the result back to Alice, then each of them would know if there is a collision, but this reveals detailed information of Alice’s path, and Bob may send a spurious result to Alice. However, this problem can be addressed by taking advantage of the Paillier homomorphic encryption system (PES). PES is an additive homomorphic encryption system [17], meaning that the sum of two encrypted numbers is the encrypted sum of the plain numbers. Paillier also supports scalar multiplication, which means that a scalar multiplied by an encrypted number yields the encryption of the scalar multiplied by the plain number. We emphasize that, though not a fully homomorphic encryption system, it suffices for the protocol we outline. To prevent the path information from being revealed, Alice can send encrypted information using PES, and Bob may perform the com- putation using these encrypted numbers only.

🏓 只是如上使用同态加密算法，会造成Bob的信息泄露，那该怎么办呢？

添加随机数

However, in doing so, Bob might expose his information as stated in [5]. To prevent this, Bob adds some random numbers to the intermediate results (h1 to h4), then sends the outcomes to Alice. Then, Alice decrypts them and uses them as the inputs to the garbled circuit. Thus, Protocol 1 securely decides if two paths collide, avoiding leaking any path information.

B. 🍎 Privacy-Preserving Persistent Monitoring

本节我看的不是很懂，我理解的本节是用来持续监控另一个小车的通信，本节是一个通信协议的介绍

⛳️ 两个小车的算法如下：

Algorithms 1 and 2 show the implementation of the privacy-preserving persistent monitoring task for two parties Alice and Bob.

如果两个小车的路径不能发生碰撞，这两个小车将同时运动；否则，将轮流运动。

If no collision is detected, Alice and Bob may safely move simultaneously. Otherwise, they will have to take turns.

C. 🍐 Rendezvous Using Secure 3D Intersection

本节的内容是对协议二、三的描述，这两个协议考虑了时间参数、3D空间。协议二是对两组路径是否在同一个平面的安全原子检测，协议三对协议二的扩展，用来检测空间上、时间上某两段路径之间是否能发生碰撞💥。

⛳️ 如何简单地解释一下协议二、三的流程：

The intersection of segments in the 3D case can be resolved using the following step：

1. Determine whether two segments are coplanar.

2. If they are coplanar, solve the problem in a subspace.

五、🎾 实验结果

线上的实验视频可以点击这个链接：http://users.cis.fiu.edu/%7Ejabobadi/securemp

A. 🍏 Software Implementation of Persistent Monitoring

⛳️ 软件模型两个小车之间的运动：

• 🚗 绿色的圈表示不会相撞

• 🚕 红色的圈表示会发生相撞

⛳️ 两个小车的运动轨迹：a => b => c => d：

从上图中可以看出，在a阶段结束后两个小车检测出来接下来会发生碰撞💥，所以Alice率先进行运动（阶段b），然后Bob才进行运动（阶段c）。

B. 🍎 Implementation of 3D Intersection

3维交叉口实验

🏓 3D的和2D的有什么不同？

需要使用全同态加密，具体哪里使用了，我觉得需要去看一下代码。

• 🚗 Since the secure intersection decision in 3D environments involves multiplication between encrypted numbers, a partial homomorphic cryptosystem like Paillier cannot implement Protocol 3. Hence, a fully homomorphic cryptosystem is needed instead. The Simple Encrypted Arithmetic Library (SEAL) [23], [24] meets the necessary requirements. This li- brary was developed by the Cryptography Research Group at Microsoft Research and has a Python wrapper PySEAL [25], [26] making it possible to use within Python.

需要生成两个秘钥对

• 🚕 Unlike the 2D case, where only Alice generates a public/private key pair, in the 3D case, both Alice and Bob generate key pairs. Thereafter, they exchange their encrypted points. We let Bob handle the vector computations related to the co-planar determination and have Alice handle the vector computations related to intersection calculation. This split is not essential for solving the problem: either Alice or Bob could perform all the calculations but doing so allows us to distribute the computational load.

⛳️ 图4同样证明了考虑时间维度后，算法依旧能检测出来碰撞点。

⛳️ 图4讲解了另一个比较优秀的例子，用来论证为啥必须用隐私保护的路径规划算法：

Fig. 4 presents the simulation results for the algorithm that computes time-parameterized path collisions for objects moving in 3D space. This exemplifies our motivating exam- ple of shared areas where manned aircraft and small UAVs need to navigate without revealing their path information.

⛳️ 图5讲解了为啥要使用时间变量：

• 🚗 若不考虑时间，可能会有假碰撞点
• 🚕 考虑时间之后，就能找到真碰撞💥点

Fig. 5 shows a secure rendezvous experiment for Alice and Bob using 3D intersection. If only two dimensions (Fig. 5 right) are considered, then two rendezvous points might be found. However, when the time is considered, by the moment Bob arrives at the meeting point, Alice may have been there in the past, or she may only arrive in the future and so no real rendezvous will occur. A rendezvous (Fig. 5 left) only occurs when there is an intersection in $R2\times T$.

C. 🍐 Hardware Experiment

⛳️ 实验环境：

A physical implementation was also conducted to test the persistent monitoring algorithms with two iRobot Create 2 platforms (see Fig. 1). The mobile robot platforms are connected to laptops running Ubuntu 12.0 SO, Intel Atom at 2.0 GHz, and 2 GB RAM. Two robots communicate with each other using the pycreate2 Python library [27]

图一证明了，当在a阶段发现可能的碰撞💥后，由Alice先行动的过程。

Fig. 1(a) shows the initial configurations and the intended path. In this experiment, all the segments are compared to each other. Since one collision is detected, Alice (blue line) moves first (Fig. 1(b) and 1©). Fig. 1(d) shows their final position. The interface to send commands to the robots takes care of the orientation of the robot, and the distance traveled at each segment. Finally, the robots face “EAST”.

六、🏐 Conclusion And Future Work

• 🚗 作者希望沿着这个密码学原语的路线继续探索

  We will explore this route in the future to extend the range of privacy-preserving robotic tasks that we can solve.

• 🚕 半诚实机器人假设研究（假设机器人是好奇的）

  We are currently exploring semi-honest models [29] where robots will follow the protocol but one robot is curious to learn the other robot’s information.

• 🚙 多个机器人的场景（机器人组中机器人的动态接入接出）

  A scheme to allow more than two parties is also a worthy aim, enabling multiple robots to decide how to move to prevent any collision. It presents several system challenges as to how many active connections they would manage and how to dynamically handle robots entering and leaving groups of interacting robots.

• 🚌 继续在其他移动平台的实践（比如微型飞行器）

  Finally, other mobile platforms, such as micro aerial vehicles, could be used for validation in future implementations.

七、🏉 我获悉的感悟

• 🚗 本文的贡献

  • ✨ 本文介绍了一种隐私保护的协作多机器人路径规划方法，使用了安全计算几何、混淆电路、同态加密等密码学技术，实现了在不共享🙅🏻‍♀️机器人🤖规划路径的前提下的路径碰撞检测方法。

  • ✨ 本文是第一篇在机器人领域应用多方安全计算的实践，证明了隐私计算的可行性。

  • ✨ 本文的motivation选题优秀，直击痛点。

• 🚕 本文中可以改进的问题

  • ✨ 多机器人平台下的接入（如作者所言），可以使用区块链？来解决动态接入接出问题？
  • ✨ 半诚实性机器人假设研究（如作者所言）
  • ✨ 密码原子操作（如作者所言），可以沿着本文的思路，将隐私计算应用到其他领域？比如铰链操作。

• 🚙 未来我可以在机器人领域做哪些隐私计算的工作？

  • ✨ 路径规划这个场景下，能不能应用联邦学习呢？

    按照本文的逻辑，这是一个多方安全计算的任务。但路径规划场景下，应该不只是有碰撞检测任务，应该也有障碍物识别任务，可以将这种任务中使用联邦学习来进行。

  • ✨ 使用安全多方计算，能不能应用到其他机器人🤖的场景下呢？

    要探究这个问题，需要找一个能够相互通信的场景，他们之间传递的数据流可能存在隐私泄露，回想一下昨天看的综述，有没有这样的设备。

  • ✨ 我应该找一下其他技术在机器人领域的应用，看一下还有没有坑可以填一下（就比如说本文这样，第一个坑）

🎱 参考文献

• 🚗 原文献：Li L, Bayuelo A, Bobadilla L, et al. Coordinated multi-robot planning while preserving individual privacy[C]//2019 International Conference on Robotics and Automation (ICRA). IEEE, 2019: 2188-2194.