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

Robot-Task Suitability in Heterogeneous Multi-Robot Task Allocation
Oct 20, 2026Daniel Weiner, Raj KorpanMulti-Robot Task Allocation
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
Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots
Sep 20, 2026Animesh Maiti, Prakhar Shukla, Subhash BhagatMulti-Robot Formation Control Mobile Robotics
Department of Mathematics, Indian Institute of Technology Jodhpur Jodhpur, Rajasthan, India
Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs
Mar 19, 2026Tsuri Farhana, Omrit Filtser, Shalev GoldshteinMulti-Robot Motion Planning Approximation Algorithms
Department of Computer Science, Ben Gurion University, Beer Sheva, Israel. · Department of Mathematics and Computer Science, The Open University of Israel, Ra’anana, Israel

Oct 20, 2026J/K move · Enter open · S save

Robot-Task Suitability in Heterogeneous Multi-Robot Task 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

Open paper AskPDF arXiv

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.

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