A Minimum Exact Disjunctive Basis for Two-Robot Solvability Profiles

Tsukasa Ninomiya; Shota Naito; Naoki Kitamura; Yuichi Sudo; Koichi Wada

cs.DCOct 13, 2026

A Minimum Exact Disjunctive Basis for Two-Robot Solvability Profiles

Authors: Tsukasa Ninomiya, Shota Naito, Naoki Kitamura, Yuichi Sudo, Koichi Wada

Organizations: Hosei University, Tokyo, Japan · The University of Osaka, Osaka, Japan

Abstract

We completely characterize the solvability profiles of tasks for two autonomous mobile robots in the plane under variable disorientation, chirality, and rigid movements. The four standard capability models and the schedulers considered here have a known quotient order Q of thirteen computational classes. A task's solvability profile is the set of classes in which it is solvable, and is necessarily an upset of Q. We prove that every upset is realizable and construct a minimum exact disjunctive basis of thirteen concrete tasks. The basis contains one task for each principal upset. For every antichain of Q, the disjunction of the corresponding tasks has profile exactly equal to the union of their profiles. This exactness is not implied by the individual profiles: an algorithm may satisfy different disjuncts in different executions. We establish it by constructing, for every algorithm in each maximal class outside the target union, a single admissible fair execution violating all selected predicates simultaneously. Consequently, the realizable profiles form the entire finite distributive lattice Up(Q): there are exactly 54 profiles, counted by the antichain polynomial 1 + 13z + 24z^2 + 16z^3, and each has a canonical disjunctive representation using at most three principal tasks. We also identify six tasks whose solvability signatures recover every inclusion and incomparability in Q, and prove that six is minimum even among arbitrary separating tasks. Their profiles are precisely the principal upsets generated by the join-irreducible elements of Q. In contrast, any task family generating every profile by exact disjunctions must contain all thirteen principal profiles. Thus our exact disjunctive basis has minimum size and is unique at the profile level.

Figures & tables

Representative	$\mathrm{EPG}^{*}$	$\mathrm{SRO}$	$\mathrm{MCv}$	CFSM	VSS	DMSD
$\mathrm{LUMI}^{F}$	1	1	1	1	1	1
$\mathrm{OBLOT}^{F}$	1	1	1	0	0	1
$\mathrm{LUMI}^{R}$	0	1	1	1	1	1
$\mathrm{FSTA}^{R}$	0	1	1	1	0	1
$\mathrm{OBLOT}^{R}$	0	1	1	0	0	1
$\mathrm{FCOM}^{S}$	0	0	1	0	1	1

Table 1: Six-task solvability signatures of the thirteen computational classes. Each row gives the six-bit signature with respect to

\mathcal{B}_{6}

. An entry

1

indicates solvability and

0

indicates impossibility. Each representative denotes its entire computational equivalence class.

Minimal profile class $X$	Principal task $B_{X}$	$\operatorname{Max}(\mathcal{Q}\setminus\uparrow X)$	Proof reference
$\mathcal{LUMI}^{F}$	EPG	$\{\mathcal{OBLOT}^{F},\allowbreak\mathcal{LUMI}^{R}\}$	Cor. D.7
$\mathcal{OBLOT}^{F}$	$\mathrm{EPG}^{*}$	$\{\mathcal{LUMI}^{R}\}$	Thm. 3.6
$\mathcal{LUMI}^{R}$	HET	$\{\mathcal{OBLOT}^{F},\allowbreak\mathcal{FST\!A}^{R},\allowbreak\mathcal{FCOM}^{S}\}$	[ NNW26 ]
$\mathcal{FST\!A}^{R}$	OSPO	$\{\mathcal{OBLOT}^{F},\allowbreak\mathcal{FCOM}^{S},\allowbreak\mathcal{FST\!A}^{S}\}$	Lem. 4.1
$\mathcal{OBLOT}^{R}$	SRO	$\{\mathcal{FCOM}^{S},\allowbreak\mathcal{FST\!A}^{S}\}$	Thm. 3.6
$\mathcal{FCOM}^{S}$	S-RDV	$\{\mathcal{OBLOT}^{F},\allowbreak\mathcal{FST\!A}^{R},\allowbreak\mathcal{FCOM}^{A}\}$	Lem. 4.2

Table 2: Thirteen principal tasks and their boundary proof obligations. The third column lists the maximal classes outside

\uparrow X

$\|A\|$	Disjunction family	No. of $A$	No. of $(A,Y)$
2	$\mathrm{EPG}^{*}\vee P$ , $P\in\mathcal{C}_{\mathrm{exp}}$	7	16
2	$\mathrm{SRO}\vee P$ , $P\in\mathcal{E}\cup\mathcal{P}_{3}$	5	8
2	$E\vee P$ , $E\in\mathcal{E}$ , $P\in\mathcal{P}_{4}$	8	18
2	$\mathrm{MCv}\vee P$ , $P\in\{\textnormal{\text{VSS}},\mathrm{VEC},\textnormal{\text{CFSM}}\}$	3	4
2	$\textnormal{\text{DMSD}}\vee\textnormal{\text{CFSM}}$	1	1
	Two-element total	24	47

Table 3: Coverage of nonprincipal profiles by construction family. The last column counts the boundary obligations

(A,Y)

, namely

\sum_{A}|\mathcal{N}_{A}|

within the corresponding row. Full boundaries and construction references are listed in Tables 4 and 5 .

Panel of Figure 1 — Figure 1: Complete solvability-profile diagram for the thirteen classes. Colors distinguish principal, two-minimal, and three-minimal profiles; labels give their canonical principal-task representations (e.g., EO and EOS). The task codes are $E=\mathrm{EPG}^{*}$ , $R=\mathrm{SRO}$ , $M=\mathrm{MCv}$ , $C=\mathrm{CFSM}$ , $V=\mathrm{VSS}$ , $D=\mathrm{DMSD}$ , $G=\mathrm{EPG}$ , $H=\mathrm{HET}$ , $O=\mathrm{OSPO}$ , $S=\mathrm{S\text{-}RDV}$ , $Z=\mathrm{ZCC}$ , $X=\mathrm{VEC}$ , and $Q=\mathrm{Cv}$ .

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: The initial configuration $\gamma_{0}$ and the three exchange configurations $C_{1}$ – $C_{3}$ admitted in the first phase.

Representative $\mu$	$\mathcal{C}_{\sigma}(\mu)$
$\mathcal{LUMI}^{F}$	$\{\mathcal{OBLOT}^{F},\mathcal{LUMI}^{R}\}$
$\mathcal{OBLOT}^{F}$	$\{\mathcal{OBLOT}^{R}\}$
$\mathcal{LUMI}^{R}$	$\{\mathcal{FST\!A}^{R},\mathcal{FCOM}^{S}\}$
$\mathcal{FST\!A}^{R}$	$\{\mathcal{OBLOT}^{R},\mathcal{FST\!A}^{S}\}$
$\mathcal{OBLOT}^{R}$	$\{\mathcal{OBLOT}^{S}\}$
$\mathcal{FCOM}^{S}$	$\{\mathcal{FCOM}^{A},\mathcal{OBLOT}^{S}\}$

Appendix

Table 6: The eighteen covering pairs of the signature-inclusion order. Each pair

\mu,\nu

in a row satisfies

\mu\geq\nu

by previously established inclusions and equivalences.

$X$	$Y$	$X\wedge_{\mathcal{Q}}Y$	$X\vee_{\mathcal{Q}}Y$
$\mathcal{OBLOT}^{F}$	$\mathcal{LUMI}^{R}$	$\mathcal{OBLOT}^{R}$	$\mathcal{LUMI}^{F}$
$\mathcal{OBLOT}^{F}$	$\mathcal{FST\!A}^{R}$	$\mathcal{OBLOT}^{R}$	$\mathcal{LUMI}^{F}$
$\mathcal{OBLOT}^{F}$	$\mathcal{FCOM}^{S}$	$\mathcal{OBLOT}^{S}$	$\mathcal{LUMI}^{F}$
$\mathcal{OBLOT}^{F}$	$\mathcal{FCOM}^{A}$	$\mathcal{OBLOT}^{A_{M}}$	$\mathcal{LUMI}^{F}$
$\mathcal{OBLOT}^{F}$	$\mathcal{FST\!A}^{S}$	$\mathcal{OBLOT}^{S}$	$\mathcal{LUMI}^{F}$
$\mathcal{OBLOT}^{F}$	$\mathcal{FST\!A}^{A_{M}}$	$\mathcal{OBLOT}^{A_{M}}$	$\mathcal{LUMI}^{F}$

Appendix

Table 7: Meet and join for all twenty-four incomparable pairs. The order and signatures are those already established in the main text.

$j$	$j_{*}$	Task with profile $\mathord{\uparrow}j$
$\mathcal{OBLOT}^{F}$	$\mathcal{OBLOT}^{R}$	$\mathrm{EPG}^{*}$
$\mathcal{OBLOT}^{R}$	$\mathcal{OBLOT}^{S}$	$\mathrm{SRO}$
$\mathcal{OBLOT}^{S}$	$\mathcal{OBLOT}^{A_{M}}$	$\mathrm{MCv}$
$\mathcal{FST\!A}^{A}$	$\mathcal{OBLOT}^{A}$	CFSM
$\mathcal{FCOM}^{A}$	$\mathcal{OBLOT}^{A_{M}}$	VSS
$\mathcal{OBLOT}^{A_{M}}$	$\mathcal{OBLOT}^{A}$	DMSD

Appendix

Table 8: Join-irreducible model classes, their unique lower covers, and the principal tasks already established at those classes.

$i$	$q_{i}$	$a_{2}(i)$	$a_{3}(i)$	$b_{2}(i)$	$b_{3}(i)$
2	$\mathcal{OBLOT}^{F}$	7	8	16	18
4	$\mathcal{FST\!A}^{R}$	2	0	5	0
5	$\mathcal{OBLOT}^{R}$	5	6	8	13
6	$\mathcal{FCOM}^{S}$	3	0	8	0
7	$\mathcal{FCOM}^{A}$	4	2	6	3
9	$\mathcal{FST\!A}^{A_{M}}$	1	0	2	0

Appendix

Table 9: Finite enumeration certificate, grouped by the smallest row index. The omitted row indices have zero in all four columns.

Multi-Robot Systems

Multi-robot systems coordinate teams of robots to plan, perceive, communicate, and act together in shared tasks and environments.

See all 205 papers

Oct 20, 2026

Robot-Task Suitability in Heterogeneous Multi-Robot Task Allocation

Heterogeneous multi-robot task allocation depends on estimates of how suitable individual robots are for candidate tasks, yet suitability can be defined in substantially different ways. We compare ten deterministic methods and two LLM-based variants spanning rule-based, similarity-based, requirement-oriented, fuzzy, and semantic approaches. Using common robot and task profiles, we compare how the methods score and rank candidate robots, identify feasibility, and select a top robot, while examining how these outcomes change with team composition, scale, spatial context, capability uncertainty, and task representation. The methods frequently disagree despite operating on identical scenarios. Generic similarity measures can violate properties expected under a one-sided requirement-satisfaction interpretation of suitability, while LLM-based scoring introduces additional stochastic and linguistic sensitivity. These results show that robot--task suitability should be treated as an explicit modeling choice whose assumptions, robustness, and decision-level consequences should be considered before allocation.

Daniel Weiner, Raj Korpan

The Graduate Center, City University of New York (CUNY), New York, NY, USA · Hunter College and The Graduate Center, City University of New York (CUNY), New York, NY, USA

Multi-Robot Task Allocation

Ask PDF

Sep 20, 2026

Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots

Two groups of autonomous, anonymous, and oblivious mobile robots are deployed in the two-dimensional Euclidean plane, each assigned a distinct task. We study a setting where the two groups must simultaneously solve two conflicting pattern formation problems: the gathering problem, where robots gather at a point not known to them a priori, and the circle formation problem, where robots occupy distinct positions on the boundary of a circle. Although each robot knows its own task, it cannot identify other members of its group. A prior solution~\cite{Conflict-1} addressed this problem for asynchronous robots having {\it direction-only axis agreement} and {\it global weak multiplicity detection} capability available to all robots in both groups. In contrast, in this work, we consider fully {\it disoriented robots} without any axis agreement or common chirality. We study the feasibility of a solution to this problem for {\it disoriented robots}. We propose a distributed algorithm that solves the problem for semi-synchronous disoriented robots with non-rigid movements. Our proposed algorithm assumes global weak multiplicity detection only for the gathering group, while for the circle formation group, it requires local weak multiplicity detection.

Animesh Maiti, Prakhar Shukla, Subhash Bhagat

Department of Mathematics, Indian Institute of Technology Jodhpur Jodhpur, Rajasthan, India

Multi-Robot Formation Control Mobile Robotics Robotics

Ask PDF

Mar 19, 2026

Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs

We study unlabeled MRMP for unit-disk robots in a polygonal environment. Although the problem is hard in general, polynomial-time solutions exist under appropriate separation assumptions on start and target positions. Banyassady et al.(SoCG'22) guarantee feasibility in simple polygons under start--start and target--target distances of at least

4

, and start--target distances of at least

3

, but without optimality guarantees. Solovey et al.(RSS'15) provide a near-optimal solution in general polygonal domains, under stricter conditions: start/target positions must have pairwise distance at least

4

, and at least

\sqrt{5}\approx2.236

from obstacles. This raises the question of whether polynomial-time algorithms can be obtained in even more densely packed environments. In this paper we present a generalized algorithm that achieve different tradeoffs on the robots-separation

ρ

and obstacles-separation

ω

, all significantly improving upon the state of the art. Specifically, we obtain polynomial-time constant-approximation algorithms to minimize the total path length when (i)

ρ=2\frac{2}{3}

and

ω=1\frac{2}{3}

, or (ii)

ρ\approx3.291

and

ω\approx1.354

. These solutions are weakly-monotone; we also provide a monotone solution requiring

ω=\approx1.614

and

ρ=4

. We prove that monotone plans may not exist when

ω<1.614

, and weakly-monotone plans may not exist when

ω<1.354

. We then present tradeoffs between the separation bounds and the approximation factor, specifically achieving an (almost) optimal bound of

ρ=2

at the cost of a linear approximation factor and requiring

ω=2

. This applies also for the labeled variant of MRMP, in which case we show a tight bound on

ω

. Finally, we show that without any robots-separation assumption, obstacles-separation of at least

1.5

may be necessary for a solution to exist.

Tsuri Farhana, Omrit Filtser, Shalev Goldshtein

Department of Computer Science, Ben Gurion University, Beer Sheva, Israel. · Department of Mathematics and Computer Science, The Open University of Israel, Ra’anana, Israel

Multi-Robot Motion Planning Approximation Algorithms

Ask PDF

Abstract

Multi-Robot Systems

Explore similar work

Robot-Task Suitability in Heterogeneous Multi-Robot Task Allocation

Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots

Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs