Introduction

A generally desirable feature in autonomous systems is to perform tasks with minimal information. For feedback systems, such information is captured in the form of sensing data and a control law: a system completes a loop by taking in sensing data, estimating its state, making a control decision, and executing the control. Often, however, the information being minimized is limited to only sensing or only control. Sacrificing good state estimation usually demands compensation from more precise control and vise versa. The seemingly inescapable trade-off between sensing and control capabilities prompts the question: Is any interesting task achievable with both coarse sensing and quantized control?

In this paper, we investigate multi-agent rendezvous with an emphasis on minimalism in both sensing and control. The agents are Dubins car vehicles [9,20] equipped with sensors of limited field-of-view and bounded range. We show that the vehicles, each operating independently under a three-level feedback quantized control law, will rendezvous without ever obtaining coordinate data or performing state estimation. This result is based on three temporary assumptions:

• Every agent is initially assigned at most one target to form a connected assignment graph;
• An agent can track its target with its sensor, even in the presence of occlusion;
• Any agent without a target will stop moving;

and one standing assumption:

• An agent and its target ``merge'' into a single agent when they are sufficiently close by.

The merging assumption, which can be satisfied with stronger sensing and control in near-range only, is due to the Dubins car dynamics and the simple control law considered. Upon establishing that identical agents can achieve guaranteed rendezvous in finite time, results of similar flavor are obtained for agents with bounded, possibly different forward velocities. We then continue to show that, with a slightly stronger quantized control law, the three temporary assumptions are not necessary for identical agents. As an interesting side note, we also show (in Appendix C) that our problem and results match those of the classic cyclic pursuit when agents can change headings instantly.

The rendezvous problem in the control context catches our attention as an actively pursued problem during the past decade. An early formulation and algorithmic solution of the multi-agent rendezvous problem is introduced in [1], in which agents have limited range sensing capabilities. Stop-and-go strategies extending the algorithm in [1] are proposed in [22] and [23], which cover various synchronous and asynchronous formulations. An $n$ -dimensional rendezvous problem was approached via proximity graphs in [6]. A research area that is closely related to rendezvous is cyclic pursuit or the n-bug problem, in which each agent pursues on a directed cycle its reachable neighboring agent. The mathematical study of pursuit curves and pursuit polygons with differential constraints originated this line of research [2,5], with the focus being whether, when, where, and how the participating agents meet each other. Stable pursuit polygons in cyclic pursuit are also investigated in [34]. In the past few years, due partly to the realization that state estimation (sensing and computation) and control are both key but distinct components in practical systems, cyclic pursuit problems with feedback control have been further explored [25,28,37,38], with [28] giving a history and review on cyclic pursuit.

In control theory, the problem of controlling a plant using coarse quantized measurements of its state (or output) has received much attention in recent years. Quantized control, an active branch of control theory, focuses particularly on minimal data rate control laws. The motivation for studying such control problems comes from situations in which the rate of information flow between the plant and the controller has to be minimized due to communication bandwidth constraints, shared network resources, security concerns, or other considerations. For some classes of systems, most notably linear ones, precise conditions have been obtained on how much information is needed for control; see, e.g., [4,8,10,14,15,21,30,32,39,42]. However, in minimizing data rate, quantized control bases the control decisions on estimation of state coordinates, which requires significant computational resources as well as sophisticated analysis tools.

Minimalism also appears in robotics research that vies for simple abstract sensors. Some earlier efforts are bug algorithms for navigation in environments with obstacles [19,27] and algorithms for manipulating convex polygonal parts using sensorless robots [11,13]. Recently, gap navigation trees for optimal navigation were introduced in [40]. In assuming weak sensors, these works typically equip the robots with sophisticated control laws. For example, [40] requires the robot to reliably move toward depth-map discontinuities.

In contrast to the aforementioned studies, our work has the distinguishing feature that we engage quantized control without assuming the availability of perfect coordinate information within sensing range. This aspect of our study promotes the understanding of the least amount of information or data rate required for a given task, which in turn offers insights into the task's inherent complexity. From a practical standpoint, minimalism in sensing or control leads to less complicated system design, improved robustness, lower production cost, and reduced energy consumption. Moreover, when physical size of agents is constrained, for instance in swarm robotics, sensing and computation become very limited, requiring a minimal design. To the best of our knowledge, there has been no attempt to reduce sensing and control, to the extremely limited combination considered in our paper, to complete tasks of broad research interest, such as rendezvous.

A central element of our approach is the Lyapunov function that we use, which assumes an unusual linear form (in distance) that simplifies the analysis. Lyapunov analysis has also been applied to study autonomous group coordination over graphs in [16], but that paper's approach requires the agents' full awareness of their local environments. Besides [16], distributed consensus has also been the focus of [29,33,12,7]. Our study is partly inspired by work on planning for a differential drive with a limited field-of-view [3], which does not, however, consider minimalism. This paper extends the results found in the conference version [43]. In particular, finer rendezvous guarantee is achieved in some cases, sometimes with relaxed requirements on vehicle model and/or sensing capability. The results presented in the paper are also demonstrated with simulation (see Fig. 1 and Section 7).

Figure 1: Screen captures from simulation program of a seven agent cyclic pursuit with one agent running after another. a) - d) Four snapshots of the rendezvous process. e) Plot of the Lyapunov function over time during the rendezvous process. The seven lower valued curves are individual distances between agents and their targets; the higher valued curve is the sum of the seven distances (the Lyapunov function), with $a$ -$d$ on the plot corresponding to the times when the four snapshots are taken.

The paper is organized as follows. Section 2 gives a detailed formulation of the rendezvous problem that we solve. Section 3 introduces a graph structure with a connectivity condition as the first ingredient of the sufficient conditions for rendezvous. Section 4 defines the candidate Lyapunov function and gives the second ingredient of the sufficient conditions, the windshield angle requirement, for agents moving at a single constant speed. The result is then generalized to agents with bounded, varying speeds in Section 5. In Section 6, we provide the remaining condition on the angular velocity requirement, followed by extensions that remove the aforementioned temporary assumptions. In Appendix C, we show how our results specialize to the classic cyclic pursuit problem. Simulation results are presented in Section 7, after which we conclude with Section 8.