Multi-Agent Path Finding (MAPF) is a challenging combinatorial problem that
asks us to plan collision-free paths for a team of cooperative agents. In this
work, we show that one of the reasons why MAPF is so hard to solve is due to a
phenomenon called pairwise symmetry, which occurs when two agents have many
different paths to their target locations, all of which appear promising, but
every combination of them results in a collision. We identify several classes
of pairwise symmetries and show that each one arises commonly in practice and
can produce an exponential explosion in the space of possible collision
resolutions, leading to unacceptable runtimes for current state-of-the-art
(bounded-sub)optimal MAPF algorithms. We propose a variety of reasoning
techniques that detect the symmetries efficiently as they arise and resolve
them by using specialized constraints to eliminate all permutations of pairwise
colliding paths in a single branching step. We implement these ideas in the
context of the leading optimal MAPF algorithm CBS and show that the addition of
the symmetry reasoning techniques can have a dramatic positive effect on its
performance - we report a reduction in the number of node expansions by up to
four orders of magnitude and an increase in scalability by up to thirty times.
These gains allow us to solve to optimality a variety of challenging MAPF
instances previously considered out of reach for CBS.

本文针对多智能体路径规划中的对称性问题，提出了一种通过推理技术解决对称性问题的方法，并将其应用于 CBS 算法，实现了在性能和效率方面的显著提升。

多智能体路径规划搜索的配对对称性推理

Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search

Massive Machine-Type Communications (MTC) over cellular networks is expected
to be an integral part of wireless "Smart City" applications. The Long Term
Evolution (LTE)/LTE-Advanced (LTE-A) technology is a major candidate for
provisioning of MTC applications. However, due to the diverse characteristics
of payload size, transmission periodicity, power efficiency, and quality of
service (QoS) requirement, MTC poses huge challenges to LTE/LTE-A technologies.
In particular, efficient management of massive random access is one of the most
critical challenges. In case of massive random access attempts, the probability
of preamble collision drastically increases, thus the performance of LTE/LTE-A
random access degrades sharply. In this context, this article reviews the
current state-of-the-art proposals to control massive random access of MTC
devices in LTE/LTE-A networks. The proposals are compared in terms of five
major metrics, namely, access delay, access success rate, power efficiency, QoS
guarantee, and the effect on Human-Type Communications (HTC). To this end, we
propose a novel collision resolution random access model for massive MTC over
LTE/LTE-A. Our proposed model basically resolves the preamble collisions
instead of avoidance, and targets to manage massive and bursty access attempts.
Simulations of our proposed model show huge improvements in random access
success rate compared to the standard slotted-Aloha-based models. The new model
can also coexist with existing LTE/LTE-A Medium Access Control (MAC) protocol,
and ensure high reliability and time-efficient network access.

本篇论文旨在回顾控制 LTE/LTE-A 网络中的大规模机器类型通信 (Massive Machine-Type Communications，MTC) 设备的随机接入的现状和最新提案，提出一种碰撞解决方案的随机接入模型来解决泊松分布访问竞争问题，并相比于标准的基于分时 Aloha 协议的模型，在整体访问成功率和功率效率上取得了显著改进。

智慧城市中大规模机器通信的 LTE/LTE-A 随机接入

LTE/LTE-A Random Access for Massive Machine-Type Communications in Smart  Cities

The Massive MIMO (multiple-input multiple-output) technology has great
potential to manage the rapid growth of wireless data traffic. Massive MIMO
achieves tremendous spectral efficiency by spatial multiplexing of many tens of
user equipments (UEs). These gains are only achieved in practice if many more
UEs can connect efficiently to the network than today. As the number of UEs
increases, while each UE intermittently accesses the network, the random access
functionality becomes essential to share the limited number of pilots among the
UEs. In this paper, we revisit the random access problem in the Massive MIMO
context and develop a reengineered protocol, termed strongest-user collision
resolution (SUCRe). An accessing UE asks for a dedicated pilot by sending an
uncoordinated random access pilot, with a risk that other UEs send the same
pilot. The favorable propagation of Massive MIMO channels is utilized to enable
distributed collision detection at each UE, thereby determining the strength of
the contenders' signals and deciding to repeat the pilot if the UE judges that
its signal at the receiver is the strongest. The SUCRe protocol resolves the
vast majority of all pilot collisions in crowded urban scenarios and continues
to admit UEs efficiently in overloaded networks.

本文介绍了如何在大规模天线阵列 (Massive MIMO) 中优化随机接入问题，并提出了强用户碰撞分辨协议 (SUCRe)，可以在拥挤的城市场景中解决大多数资源冲突，以及在过载网络中继续高效地接收用户。