# Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for
More Efficient Multi-Agent Path Finding Plan Execution

Yifan Su, Rishi Veerapaneni, Jiaoyang Li

###### Abstract

The Multi-Agent Path Finding (MAPF) problem involves planning collision-free
paths for multiple agents in a shared environment. The majority of MAPF
solvers rely on the assumption that an agent can arrive at a specific location
at a specific timestep. However, real-world execution uncertainties can cause
agents to deviate from this assumption, leading to collisions and deadlocks.
Prior research solves this problem by having agents follow a Temporal Plan
Graph (TPG), enforcing a consistent passing order at every location as defined
in the MAPF plan. However, we show that TPGs are overly strict because, in
some circumstances, satisfying the passing order requires agents to wait
unnecessarily, leading to longer execution time. To overcome this issue, we
introduce a new graphical representation called a Bidirectional Temporal Plan
Graph (BTPG), which allows switching passing orders during execution to avoid
unnecessary waiting time. We design two anytime algorithms for constructing a
BTPG: BTPG-naïve and BTPG-optimized. Experimental results show that following
BTPGs consistently outperforms following TPGs, reducing unnecessary waits by
8-20%.

##  1 Introduction

The Multi-Agent Path Finding (MAPF) problem involves finding paths for
multiple agents to reach their respective destinations from their starting
points in a shared environment without collisions (Stern et al. 2019). The
importance of solving the MAPF problem is reflected in its wide range of
applications, such as warehouse automation (Varambally, Li, and Koenig 2022),
traffic management (Li et al. 2021a), and drone swarm coordination (Honig et
al. 2018).

The MAPF problem discretizes time into unit timesteps, assuming that an agent
can reach a particular location at a particular timestep. However, in
practice, agents face challenges such as communication delays, physical
constraints, or hardware failures that prevent them from meeting this
assumption. When an agent is unable to reach a location required by the MAPF
plan at a specific timestep, it may result in deadlocks or collisions with
other agents.

To address this issue, Ma, Kumar, and Koenig (2017) proposed a MAPF with Delay
Probability (MAPF-DP) model where, at each timestep, each agent has a certain
probability of stopping in place, leading to delays. Both Ma, Kumar, and
Koenig (2017) and Hoenig et al. (2016) show that as long as the agents adhere
to the inter-agent dependencies required by the MAPF plan, they can complete
their respective paths without collisions or deadlocks. These dependencies
ensure that the order in which the agents pass through _every_ location is
consistent with the planned path. Both studies capture these dependencies by
defining a graph representation, called the _Temporal Plan Graph_ (TPG).
Requiring agents to execute according to the dependencies in the TPG ensures
completion of the MAPF plan without collisions and deadlocks, even if agents
reach some locations at different timesteps than specified in the MAPF plan.

((a)) Scenario 1.

((b)) Scenario 2.

((c)) TPG for Scenario 2.

Figure 1: Motivating examples. In Scenario 1 (2), the MAPF plan requries the
agents to follow the arrows with the green agent passing through location F
(E) before the blue agent.

In Figure 1(a), the MAPF plan specifies that the green agent should pass
location F before the blue agent. If they follow the corresponding TPG, the
green agent will pass F first. Switching this order would lead to a deadlock,
with the blue agent trying to move from F to E and the green agent from E to
F. In contrast, Figure 1(b) shows a different scenario. Here, the green agent
is supposed to pass location E first. If the green agent is delayed at D, the
TPG makes the blue agent wait at B until the green agent passes E. However, if
the green agent is delayed, the blue agent can safely pass E first without
causing a deadlock. This flexibility in switching the order of passing can
reduce unnecessary waiting and shorten the overall execution time.

The goal of this paper is to determine when the dependencies can be switched,
allowing agents to pass such locations in a “first-come-first-served” manner
in execution to minimize unnecessary waiting time. Our main contributions are:

  1. 1.

Defining a new graphical representation called the _Bidirectional Temporal
Planning Graph_ (BTPG) for capturing all such switchable dependencies in a
MAPF plan;

  2. 2.

Introducing sufficient conditions for a BTPG to be provably collision-free and
deadlock-free;

  3. 3.

Proposing two anytime algorithms for constructing a BTPG, namely BTPG-naïve
and BTPG-optimized, and showing that following BTPGs consistently outperforms
following TPGs, reducing unnecessary waits by 8-20%.

##  2 Preliminaries

###  2.1 Problem Definition

The input of the MAPF problem (Stern et al. 2019) contains an undirected graph
and a set of $n$ agents, each with a start location and a target location. Its
output is a MAPF plan, which is a set of conflict-free paths for $n$ agents
that move them from their respective start locations to their respective
target locations. Time is discretized into unit timesteps. At every timestep,
an agent either moves to a neighboring location or waits at its current
location. The $i$th element in an agent’s path represents the location of that
agent at timestep $i$. An agent that finishes its path rests at its target
location forever. There are two ways in which the paths of two agents can
create a conflict: A _vertex conflict_ occurs when two agents occupy the same
location at the same timestep, and a _edge conflict_ occurs when two agents
traverse the same edge at the same timestep.

To enable the “first-come-first-served” mechanism, we assume that, during
execution, every agent has an onboard collision-avoidance mechanism that can
stop automatically when there is an obstacle (such as another agent) in front
of it, a common function for modern robots.

In order to reflect the execution uncertainty in real applications, we use the
MAPF with Delay Probabilities (MAPF-DP) model (Ma, Kumar, and Koenig 2017).
That is, during execution, an agent may get stuck at its current location for
a period of time instead of following its path to move to its next location.
In addition to the two types of conflicts defined above, the original MAPF-DP
model also disallows _following conflicts_ , where one agent enters a vertex
that was occupied by another agent in the previous timestep. Their concern is
that if the front agent suddenly stops, the following agent may run into the
front agent. However, we allow the following conflicts in this paper for three
reasons. First, the onboard collision-avoidance mechanism can easily guarantee
collision-freeness in the above-mentioned situation because the following
agent will stop when the front agent stops. Second, allowing following
conflicts makes MAPF plans shorter and thus potentially leads to better
execution times. Third, most modern MAPF planners, such as CBS-based (Sharon
et al. 2015; Gange, Harabor, and Stuckey 2019; Li, Ruml, and Koenig 2021),
priority-based (Erdmann and Lozano-Perez 1986; Ma et al. 2019), and rule-based
(Sajid, Luna, and Bekris 2012; Okumura et al. 2019) planners allow for
following conflicts, so we can directly use these off-the-shelf MAPF planners
without changes.

###  2.2 Temporal Plan Graph (TPG)

We now introduce the definition of TPGs along with its properties established
in prior research. In line with previous work, we assume that following
conflicts are disallowed here. In the next section, we will demonstrate how we
modify the definition and properties of TPGs to accommodate scenarios where
such following conflicts are indeed allowed.

######  Definition 1 (TPG).

TPG (Ma, Kumar, and Koenig 2017) is a directed acyclic graph $G=(V,E)$. Each
vertex $v_{i}^{m}\in V$ represents a state of agent $m$ being at location
$loc(v_{i}^{m})$. Here, $i$ indicates that $loc(v_{i}^{m})$ is the $i$th
element in the path of agent $m$. Each edge establishes a precedence
dependency between two states. We divide the edges $E$ into type-1 edges
$E_{1}$ and type-2 edges $E_{2}$. A type-1 edge $(v_{i}^{m},v_{i+1}^{m})\in
E_{1}$ forces agent $m$ to enter $loc(v_{i+1}^{m})$ only after it has entered
$loc(v_{i}^{m})$; A type-2 edge $(v_{i}^{m},v_{j}^{n})\in E_{2}$ forces agent
$n$ to enter $loc(v_{j}^{n})$ only after agent $m$ has entered
$loc(v_{i}^{m})$.

##### TPG Construction

To construct a TPG from a given MAPF plan, for every agent, we introduce a
vertex for every element in its path that is different from the previous one,
i.e., we omit states indicating waits. We add a type-1 edge for each pair of
successive elements in the path of every agent. We add a type-2 edge if one
agent visits a location before another. More specifically, if there is a
_conflict location_ $loc(v_{i}^{m})=loc(v_{j}^{n})$, and agent $m$ visits it
before agent $n$ in the MAPF plan, we introduce a type-2 edge
$(v_{i+1}^{m},v_{j}^{n})$, indicating that only after agent $m$ left
$loc(v_{i}^{m})$ and enters its next location $loc(v_{i+1}^{m})$, agent $n$ is
allowed to enter $loc(v_{j}^{n})$. Figure 1(c) illustrates the TPG derived
from the MAPF plan depicted in Figure 1(b). For simplicity, we use
$loc(v_{i}^{m})$ to denote a vertex $v_{i}^{m}$. The arrow FE is a type-2 edge
indicating that the green agent needs to pass through location E before the
blue agent. Other arrows represent type-1 edges.

##### TPG Execution Policy

At each timestep during execution, each agent $m$ is allowed to move to its
next state $v_{i}^{m}$ only if, $\forall(v_{j}^{n},v_{i}^{m})\in E_{2}$, agent
$n$ has already visited state $v_{j}^{n}$; otherwise, it must wait (Ma, Kumar,
and Koenig 2017).

######  Property 1 (Cycle-free $\Leftrightarrow$ valid TPG).

If and only if a TPG is cycle-free, TPG execution is guaranteed to succeed,
i.e., agents are assured to reach their target locations without collisions or
deadlocks (Berndt et al. 2020; Coskun, O’Kane, and Valtorta 2021). We refer to
such a TPG as a _valid_ TPG.

Figure 2: TPG for the scenario where 3 agents rotate in a cycle
simultaneously.

Figure 3: BTPG for the example depicted in Figure 1(b).

###  2.3 Related Work

The TPG execution policy asks agents to coordinate their passing orders at
conflict locations, which sometimes leads to unnecessary waits. One way to
reduce such unnecessary waits is to find MAPF plans that explicitly minimize
coordination, such as SL-CBS (Wagner, Veerapaneni, and Likhachev 2022) and DBS
(Okumura et al. 2023). However, these models usually impose overly strict
coordination constraints, making them more challenging to solve than regular
MAPF and resulting in longer execution times.

Another way is to generate MAPF plans that consider potential delays during
planning (Ma, Kumar, and Koenig 2017; Atzmon et al. 2018), which, however,
demand prior knowledge of delays and are sometimes overly conservative.

A third way is to replan, for example, by checking if a particular passing
order can be switched when delays happen during execution (Berndt et al. 2020;
Paul, Feng, and Li 2023; Pecora et al. 2018; Coskun, O’Kane, and Valtorta
2021). However, these methods require additional computation during execution,
potentially introducing further delays.

In contrast, our proposed BTPG idea generates a MAPF plan using regular MAPF
planners and post-processing it by exploring all potential switchable
dependencies during the planning phase. By doing so, we avoid increasing the
complexity of solving MAPF, eliminate the need for prior knowledge of delay
distribution, and eradicate the necessity for additional computation during
execution.

##  3 TPG that Allows Following

In the TPG shown in Figure 1(c), suppose at timestep $t$, the blue and green
agents are at B and E, respectively. However, at timestep $t+1$, the blue
agent cannot reach E even if the green agent departs E at the same timestep.
This is because the original definition of type-2 edges was predicated on
disallowing following conflicts, which requires the blue agent to reach E only
_after_ the green agent reaches F.

However, since we allow such following actions, we propose a refined
definition for type-2 edges $(v_{i}^{m},v_{j}^{n})$. The revised definition
specifies that agent $n$ can enter $loc(v_{j}^{n})$ _no earlier than_ agent
$m$ enters $loc(v_{i}^{m})$. With this adjustment, in Figure 1(c), the blue
agent can enter E simultaneously with the green agent departing E for F.

It is worth noting that this change is orthogonal to our proposed BTPG
techniques. Our techniques are applicable to both TPGs that allow following
and those that do not.

###  3.1 Rotation Cycle

Since agents can follow each other, they can rotate simultaneously, which was
not allowed before in the original TPG definition. Figure 3 shows an example,
where, at the same timestep, agent 1 goes from A to B, agent 2 goes from B to
C, and agent 3 goes from C to A. This leads to a cycle ($B\rightarrow
A\rightarrow C\rightarrow B$) in the TPG but not a deadlock. We thus need to
update the definition of valid TPGs.

######  Definition 2 (Rotation Cycle).

A _rotation cycle_ is a cycle in a TPG consisting of only type-2 edges, with
the cycle containing more than two edges. Note that if a cycle contains only
two edges, it leads to a deadlock, since rotating the corresponding two agents
is an edge conflict.

######  Property 2 (Valid TPG with rotations).

A TPG (that allows following) is valid if it has no non-rotation cycles.

##  4 Bidirectional TPG

Figure 1(c) depicts the TPG for Scenario 2 (Figure 1(b)) where the green agent
enters E before the blue agent. If we switch the passing order, letting the
blue agent enter E first, then we must change the type-2 edge from $(F,E)$ to
$(H,E)$. We refer to these two type-2 edges as a bidirectional pair.

######  Definition 3 (Bidirectional pair).

A _bidirectional pair_ $(e,\tilde{e})$ consists of two type-2 edges
$e=(v_{i+1}^{m},v_{j}^{n})$ and $\tilde{e}=(v_{j+1}^{n},v_{i}^{m})$ with
conflict location $loc(v_{j}^{n})=loc(v_{i}^{m})$. We refer to one such edge
as the _reversed edge_ of the other.

######  Definition 4 (BTPG).

A _Bidirectional TPG_ (BTPG) is a TPG that contains bidirectional pairs. We
use $E_{pair}$ to represent the set of type-2 edges that are in bidirectional
pairs.

##### BTPG Execution Policy

The BTPG execution policy follows the TPG execution policy except that, for
each bidirectional pair, only one edge is selected during execution based on a
“first-come-first-served” manner. Specifically, either agent in the pair is
allowed to enter the conflict location first. But when the first agent
arrives, the type-2 edge that enables this agent to enter first is selected,
while the other edge is discarded. In other words, edge
$(v_{i+1}^{m},v_{j}^{n})$ is selected when agent $m$ reaches $v_{i}^{m}$, and
edge $(v_{j+1}^{n},v_{i}^{m})$ is selected when agent $n$ reaches $v_{j}^{n}$.
Figure 3 displays the BTPG for Scenario 2. Edges $(F,E)$ and $(H,E)$ are a
bidirectional pair, indicating that both agents can pass through location E
first. If, for example, the green agent reaches E first, then $(F,E)$ is
selected, and $(H,E)$ is discarded.

Figure 4: In our 3,900 simulations, BTPG never performed worse than TPG. Thus
ideally we could prove that BTPGs are strictly superior to TPGs. However, here
we show a hand-crafted adversarial example where a BTPG leads to longer
execution time than a TPG under a specific set of delays.

##### Execution Time of TPG vs BTPG

While we introduce BTPG to reduce unnecessary waits caused by certain type-2
edges in TPG, the execution time of following the BTPG policy can be longer
than that of following the TPG policy in adversarial cases. We provide an
example in Figure 4, even though we have not observed any such cases among the
3,900 simulations tested in our experiments.

##  5 Construct BTPG from TPG

To construct a BTPG, we first run a MAPF planner to obtain a MAPF plan and
convert it to a valid TPG. We then check one by one whether each type-2 edge
can be transformed into a bidirectional pair without resulting in an invalid
BTPG. We terminate the algorithm when we reach the runtime limit or when all
type-2 edges have been evaluated. We develop two such algorithms: BTPG-n and
BTPG-o.

###  5.1 BTPG-naïve (BTPG-n)

Since exactly one edge within each bidirectional pair will be selected during
execution, a BTPG with $k$ bidirectional pairs can be conceptualized as
comprising a collection of $2^{k}$ TPGs, each of which represents a different
combination of edges in bidirectional pairs. Depending on the order in which
the agents pass through the conflict location of each bidirectional pair, one
of these TPGs will eventually be executed. Therefore, when all $2^{k}$ TPGs
are valid, namely none of them contains any non-rotation cycles (according to
Property 2), the corresponding BTPG is guaranteed to be valid. Concurrently,
not viewing a BTPG as $2^{k}$ TPGs but viewing it as a single graph with
bidirectional pairs, a BTPG is valid if it contains only rotation cycles and
self cycles, where a _self cycle_ is a cycle that involves both edges in a
bidirectional pair, like $E\rightarrow H\rightarrow E\rightarrow F\rightarrow
E$ shown in Figure 3. A valid BTPG can have self cycles because a self cycle
can never appear in one TPG as a TPG cannot contain both edges in a
bidirectional pair.

######  Property 3 (Valid BTPG-naïve).

A BTPG is valid if it does not contain any Non-Rotation and Non-Self (NRNS)
cycles.

Based on Property 3, our first proposed algorithm BTPG-naïve (BTPG-n) (see
Algorithm 1) examines type-2 edges one by one to detect NRNS cycles and change
an edge to bidireticonal pairs if no NRNS cycles are found. As $\mathcal{G}$
is guaranteed to have no NRNS cycles at the beginning of each “for” iteration
(Algorithm 1), our focus is solely on checking for NRNS cycles involving the
newly added edge $\tilde{e}$ at Algorithm 1. This verification is carried out
by running a Depth First Search (DFS) (see Algorithm 2) from $v_{i}^{m}$ to
determine if we can reach $v_{j+1}^{n}$ through NRNS cycles. Note that
Algorithms 1 and 1 indicate that $v_{i+1}^{m}$ is not the first state of agent
$m$, and $v_{j}^{n}$ is not the last state of agent $n$. We do not examine
type-2 edges pointing from the first state of an agent because it starts at
its first state, so no other agents can visit the corresponding conflict
location before it. Similarly, we do not examine those pointing to the last
state of an agent because it stays there without leaving, so no other agents
can visit the corresponding conflict location after it.

Input: TPG $G=(V,E_{1}\cup E_{2})$

Output: BTPG $\mathcal{G}$

$E_{pair}\leftarrow\emptyset$;

_//__set of edges in bidirectional pairs_

1 while $E_{pair}$ has been updated do  __

2 for  _$e=(v_{i+1}^{m},v_{j}^{n})$ in $E_{2}$ (or until TimeOut)_ do

$\tilde{e}\leftarrow(v_{j+1}^{n},v_{i}^{m})$;

_//__reversed edge_

3 $E_{pair}\leftarrow E_{pair}\cup\\{e,\tilde{e}\\}$, $E_{2}\leftarrow
E_{2}\setminus\\{e\\}$;

4 $\mathcal{G}\leftarrow(V,E_{1}\cup E_{2}\cup E_{pair})$;

5 if
_hasCycle($\mathcal{G},v_{i}^{m},v_{j+1}^{n},\framebox{$\\{v_{i}^{m}\\},$}\\{e\\}$)_
then

6 $E_{pair}\leftarrow E_{pair}\setminus\\{e,\tilde{e}\\}$, $E_{2}\leftarrow
E_{2}\cup\\{e\\}$;

7

8

9

10

11return $\mathcal{G}=(V,E_{1}\cup E_{2}\cup E_{pair})$;

Algorithm 1 BTPG-naïve/optimized. The boxed code is only for BTPG-optimized.

Input: (1) BTPG $\mathcal{G}=(V,E_{1}\cup E_{2}\cup E_{pair})$, (2) current
vertex for expansion $v_{i}^{m}$, (3) origin vertex $v_{o}$, and (4) set(s) of
visited vertices $V_{vis}$ and edges $E_{vis}$ along the current DFS branch.

Output: true or false

if  _$v_{i}^{m}=v_{o}$_ then

if  _$E_{vis}\subset E_{2}\cup E_{pair}$ and $|E_{vis}|>2$_ then

return false;

_//__rotation cycle_

1

2 else return true;

3

4for  _$v_{j}^{n}$ in $\\{v_{j}^{n}\in V\mid(v_{i}^{m},v_{j}^{n})\in E_{1}\cup
E_{2}\cup E_{pair}$}_ do

5 $e\leftarrow(v_{i}^{m},v_{j}^{n})$;

6

7 if  _$e\in E_{pair}$_ then

8 if  _$(v_{j+1}^{n},v_{i-1}^{m})\in E_{vis}$ or $\exists
v_{i^{\prime}}^{m}\in V_{vis}:i^{\prime}<i$_ then continue;

9

10

11 if  _hasCycle($\mathcal{G}$, $v_{j}^{n}$, $v_{o}$,
$V_{vis}\cup\\{v_{j}^{n}\\}$, $E_{vis}\cup\\{e\\}$)_ then return true;

12

13return false;

14

Algorithm 2 hasCycle. The boxed code is only for BTPG-optimized.

Algorithm 2 returns true if and only if it detects a NRNS cycle. It makes two
key changes to regular DFS to exclude rotation and self cycles. First, since
only one edge within each bidirectional pair can be selected during execution,
our DFS must avoid visiting both edges in a bidirectional pair along one DFS
branch. To do so, we use $E_{vis}$ to store the edges that our DFS has visited
along the current branch and prune a child node if the reversed edge of the
current type-2 edge is in $E_{vis}$ (Algorithms 2 and 2). Second, when our DFS
finds a cycle (Algorithm 2), we return false if it is a rotation cycle
(Algorithms 2 and 2) and true otherwise (Algorithm 2). Here, $E_{vis}$ to
store the edges that our DFS has visited along the current branch.An
additional implementation detail not explicitly outlined in this pseudo-code
is that, to speed up our DFS, we maintain a set of visited vertices to prevent
the algorithm from re-expanding the same vertex.

#### Grouping

Figure 5: Two cases of grouping: The left case is when one agent follows
another agent; the right one is when two agents move along the same path in
opposite directions. Red arrows depict the reversed edges of edge $(C,B)$.

Motivated by (Berndt et al. 2020), we find two common cases in which BTPG-n
cannot change the type-2 edges to bidirectional pairs shown in Figure 5. They
are the cases where two agents visit the same sequence of locations in the
same or reversed order, which have consecutive type-2 edges in corresponding
TPGs. As adding the reserved edge of any type-2 edge can form a NRNS cycle,
BTPG-n cannot change any type-2 edges in such cases to bidirectional pairs.
Therefore, at Algorithm 1 of Algorithm 1, we merge such type-2 edges into
groups and examine only type-2 edges that cannot form a group to reduce the
runtime.

###  5.2 BTPG-optimized (BTPG-o)

((a)) MAPF instance.

((b)) Corresponding BTPG. We use $X_{i}^{m}$ to depict vertex $v_{i}^{m}$ with
$loc(v_{i}^{m})=X$.

Figure 6: Example where some $2^{k}$ TPGs may never occur.

Examining all $2^{k}$ TPGs is overly conservative as we find that not all
$2^{k}$ TPGs can occur in practice. Consider the example in Figure 6. If we
add bidirectional pairs for all three type-2 edges, the resulting BTPG admits
a TPG with type-2 edges $(E^{3}_{3},C_{3}^{2})$, $(C_{3}^{2},A_{2}^{1})$, and
$(F^{1}_{4},E^{3}_{3})$. BTPG-n would regard this BTPG as invalid as it
contains a NRNS cycle $E^{3}_{3}\rightarrow C^{2}_{3}\rightarrow
A^{1}_{2}\rightarrow E^{1}_{3}\rightarrow F^{1}_{4}\rightarrow E^{3}_{3}$.

If we analyze this TPG, it leads to a deadlock where agent 1 is at location I,
awaiting agent 2 to enter location C, agent 2 is at location A, awaiting agent
3 to enter E, and agent 3 is at location C, awaiting agent 1 to enter F.
However, since agent 1 and 3 are at I and C, respectively, according to the
BTPG execution policy, edge $(G_{4}^{3},E_{3}^{1})$ rather than edge
$(F_{4}^{1},E_{3}^{3})$ would be selected. Thus, this TPG would never be
encountered during execution. Next, we will go through several lemmas to
formally reason about such cases.

Figure 7: Performance of TPG, BTPG-naïve, and BTPG-optimized. The shaded area
represents the interquartile range (25%-75%) of the data distribution. The
runtime of BTPG-n and BTPG-o is the time for the two algorithms to finish
finding their respective bidirectional pairs. Even though BTPG-o takes longer
to finish finding bidirectional pairs, it finds around 2x more bidirectional
pairs than BTPG-n, so it is actually more efficient than BTPG-n (see Figure
9).

######  Lemma 1.

When agents face a deadlock caused by a cycle in a BTPG, no agents have
visited any states in the cycle.

###### Proof.

Suppose one state $v_{i}^{m}$ in the cycle is visited, then the edge
$(v_{i}^{m},u_{j}^{n})$ in the cycle that points from this state is satisfied.
This indicates that the agent $j$ can move to state $u_{j}^{n}$. We can
similarly propagate the logic and show all states in the cycles can be
visited, which is a contradiction to a deadlock. Therefore, all states in the
cycle have not been visited. ∎

######  Lemma 2.

If edge $(v_{i}^{n},v_{j}^{m})\in E_{pair}$ is selected during execution, then
agent $n$ has already visited state $v_{i-1}^{n}$.

###### Proof.

This can be proved directly from the BTPG execution policy. ∎

######  Corollary 1.

When agents face a deadlock caused by a cycle involving edge
$(v_{i}^{n},v_{j}^{m})\in E_{pair}$, agent $n$ is at state $v_{i-1}^{n}$.

###### Proof.

From Lemma 1, agent $n$ must be before state $v_{i}^{n}$. From Lemma 2, agent
$n$ is at or after state $v_{i-1}^{n}$. Thus, agent $n$ must be at state
$v_{i-1}^{n}$. ∎

######  Theorem 1.

If a cycle contains a vertex $v_{i}^{n}$ and an edge in $E_{pair}$ that points
from $v_{j}^{n},j>i$, then this cycle will not lead to a deadlock.

###### Proof.

Suppose that this cycle will lead to a deadlock. When the deadlock occurs, by
Corollary 1, agent $n$ is at state $v_{j-1}^{n}$. By Lemma 1, agent $n$ has
not visited state $v_{i}^{n}$. Thus, state $v_{i}^{n}$ should be after state
$v_{j-1}^{n}$, contradicting the assumption of $j>i$. Thus, the theorem holds.
∎

We denote the cycles described in Theorem 1 as _non-deadlock cycles_. The
cycle in Figure 6(b) is a non-deadlock cycle as it contains both vertex
$A^{1}_{2}$ and edge $(F^{1}_{4},E^{3}_{3})$.

######  Property 4 (Valid BTPG-optimized).

A BTPG is valid if it does not contain any cycles apart from rotation cycles,
self cycles, and non-deadlock cycles.

Therefore, our second algorithm BTPG-o extends BTPG-n by considering non-
deadlock cycles. Specifically, in Algorithm 2, we use $V_{vis}$ to record all
vertices that have been visited along the current DFS branch and skip edge
$(v_{i}^{m},v_{j}^{n})\in E_{pair}$ if the current DFS branch contains a state
$v_{i^{\prime}}^{m},i^{\prime}<i$ (Algorithm 2). Furthermore, in Algorithm 1,
we repeat the examining process of type-2 edges until no new bidirectional
pair is discovered (Algorithm 1) for the following reason.

Let us consider the example in Figure 6(b). If we examine
$(D^{2}_{4},C^{3}_{2})$ before $(F^{1}_{4},E^{3}_{3})$, then
$(D^{2}_{4},C^{3}_{2})$ is not added into $E_{pair}$ because, based on the
available information at that point, cycle $E^{3}_{3}\rightarrow
C^{2}_{3}\rightarrow A^{1}_{2}\rightarrow E^{1}_{3}\rightarrow
F^{1}_{4}\rightarrow E^{3}_{3}$ is considered a cycle that leads to a
deadlock. However, after $(F^{1}_{4},E^{3}_{3})$ is examined and added into
$E_{pair}$, this cycle becomes a non-deadlock cycle, and thus,
$(D^{2}_{4},C^{3}_{2})$ and $(E^{3}_{3},C^{2}_{3})$ are then added into
$E_{pair}$. Thus, to maximize the size of $E_{pair}$, we repeat the examining
process until no new bidirectional pair is discovered. This is unique to
BTPG-o, where the validity condition becomes “easier” to satisfy as more
bidirectional pairs are added since our DFS skips some edges in bidirectional
pairs (see Algorithm 2 in Algorithm 2).

##  6 Empirical Evaluation

| den520 | warehouse | Paris | random | empty | Berlin
---|---|---|---|---|---|---
| BTPG-n | BTPG-o | BTPG-n | BTPG-o | BTPG-n | BTPG-o | BTPG-n | BTPG-o | BTPG-n | BTPG-o | BTPG-n | BTPG-o
Mean imp. | 5.9% |  8.9% | 12.1% |  17.9% | 10.6% |  14.6% | 12.9% |  15.2% | 14.5% |  20.9% | 9.6% |  14.6%
Median imp. | 5.7% | 8.1% | 12.3% | 17.8% | 10.5% | 14.2% | 10.3% | 12.2% | 14.0% | 20.0% | 9.2% | 14.2%
Max imp. | 14.0% | 19.3% | 25.0% | 35.3% | 20.7% | 25.4% | 50.0% | 63.6% | 37.5% | 42.9% | 21.3% | 24.7%
Min imp. | 1.1% |  2.9% | 2.7% |  6.7% | 4.1% |  7.0% | 0.0% | 0.0% | 3.3% |  7.4% | 3.2% |  7.6%
# Type-2 edges | 26,738 | 15,084 | 24,401 | 1,151 | 2,898 | 27,922
# Singleton edges | 2,172 | 1,051 | 2,688 | 146 | 817 | 2,265
# Bi-Pairs found | 663 | 1,008 | 368 | 532 | 1,254 | 1,725 | 60 | 76 | 248 | 360 | 1018 | 1,409
# Used Bi-Pairs | 38 | 68 | 36 | 57 | 82 | 125 | 6 | 6 | 25 | 40 | 68 | 112
BTPG runtime (s) | 23.72 | 161.88 | 6.31 | 8.72 | 58.12 | 181.33 | 0.03 | 0.04 | 0.69 | 1.06 | 43.32 | 72.87
MAPF runtime (s) | 1.93 | 9.44 | 1.12 | 19.80 | 1.11 | 9.90

Table 1: Statistics of BTPG-naïve/optimized. The number of agents for the six
maps selected for the statistics are 100, 120, 150, 50, 100, and 150,
respectively. All data in the second block are averages of 10 scenarios for
each map; Bi-Pairs: bidirectional pairs; imp.: improvement; Singleton edges:
type-2 edges that cannot be grouped.

Our experiments work as follows. First, we use the optimal MAPF solver
CBSH2-RTC (Li et al. 2021b) to obtain the MAPF plan for each given MAPF
instance. We have in total 3,900 simulations, consisting of six different
benchmark maps from (Stern et al. 2019), as shown in Figure 7, each map with
five to eight different numbers of agents, and each number of agents with ten
random instances. The largest number of agents for each map is determined by
the largest number of agents CBSH2-RTC can solve within 2 minutes. Then, we
convert each MAPF plan into a TPG (for which the runtime is negligible). Next,
we construct BTPG using our proposed algorithms BTPG-naive and BTPG-optimized.
Last, we simulate the TPG and BTPG execution policies with 10% agents having a
30% chance of being delayed by 5 timesteps at each non-delayed timestep. Each
instance is simulated with 10 random seeds, resulting in 3,900 simulations per
algorithm. All algorithms were implemented in C++
111https://github.com/YifanSu1301/BTPG, and all experiments were run on a PC
with a 3.60 GHz Intel i7-12700KF CPU and 32 GB of RAM.

##### Execution Time

Figure 7 reports the _mean execution timesteps_ , namely the average number of
timesteps that each agent takes to reach its target location during execution.
We include a lower bound called _Ideal_ , which is the sum of timesteps in the
original MAPF plan plus the total delay timesteps of the delayed agents, then
divided by the number of agents. Essentially, _Ideal_ represents an overly
optimistic scenario where delayed agents do not cause any additional waits for
other agents. As shown, BTPG-o consistently outperforms BTPG-n, which in turn
consistently outperforms TPG, across all maps and all numbers of agents.

To quantify the execution time improvement of BTPG over TPG, we define
_improvement_ as $\frac{T_{TPG}-T_{BTPG}}{T_{TPG}-T_{Ideal}}$, where
$T_{TPG}$, $T_{BTPG}$, and $T_{Ideal}$ are the mean execution timesteps of
TPG, BTPG, and Ideal, respectively. Figure 8 shows that our improvement is
always non-negative over 3,900 simulations, even though, as mentioned in
Section 4, we could have negative improvements in theory. The top block of
Table 1 further provides detailed numbers on the improvements over the
instances with the largest number of agents for each map. The median
improvement of BTPG-o is in the range of 8-20%, with maximum values around
19-64%.

Figure 8: Improvement of BTPG over TPG per instance. We find no instances with
negative improvements and 3.6%, 23.3%, 41.9%, and 31.2% of instances with no
improvement, 0-10% improvement, 10-20% improvement, and $>$20% improvement
across all simulations, respectively.

##### Bidirectional Pairs

The middle block of Table 1 reports how many bidirectional pairs that our
algorithms find and that are useful. While the TPG has thousands or even ten
thousands of type-2 edges, only about 10% of these edges are not grouped and
have the chance to be changed to bidirectional pairs. After BTPG-o evaluates
these singleton type-2 edges, about 50% are changed to bidirectional pairs. We
define a bidirectional pair as _used_ if the agents select the reversed edge
rather than the original TPG type-2 edge during execution. We see that roughly
10% of bidirectional pairs are used. Although this is a small percentage over
the total number of type-2 edges, these used bidirectional pairs are the
contributors to the significant reduction in execution time that we reported
above.

Figure 9: Anytime behavior of BTPG-n/o on warehouse with 120 agents. Scenes 1
and 2 are scenarios with the longest and shortest BTPG-o runtimes,
respectively. The appendix has similar results on other maps.

##### Runtime

Both Figure 7 and the bottom block of Table 1 report the CPU runtime of our
algorithms. As expected, BTPG-o is slower than BTPG-n. However, we find that
the longer runtime of BTPG-o is due to finding more bidirectional pairs rather
than inefficiency. Figure 9 plots the anytime behavior of both algorithms. For
any given cut-off time, BTPG-o finds more bidirectional pairs and thus leads
to better improvement than BTPG-n. BTPG-o is more efficient because its DFS
can skip over more edges than BTPG-n.

##  7 Conclusion

We constructed a new graphical representation of passing orders in the MAPF
plan, BTPG, by proposing the concept of bidirectional pairs. The main
difference between BTPG and TPG lies in the fact that agents can switch the
order of passing certain locations during execution. Two algorithms, BTPG-n
and BTPG-o, are proposed to construct a BTPG. The results indicate that
following BTPGs consistently outperform following TPGs by 8-20% when agents
get delayed. Also, we show our proposed algorithms are anytime, and given a
fixed time budget, BTPG-o outperforms BTPG-n. Overall, we convincingly show
that allowing switching dependencies in a MAPF plan allows us to improve
execution time without replanning.

## Acknowledgments

The research is supported by the National Science Foundation (NSF) under grant
number 2328671. The views and conclusions contained in this document are those
of the authors and should not be interpreted as representing the official
policies, either expressed or implied, of the sponsoring organizations,
agencies, or the U.S. government.

## References

  * Atzmon et al. (2018) Atzmon, D.; Stern, R.; Felner, A.; Wagner, G.; Bartak, R.; and Zhou, N.-F. 2018.  Robust Multi-Agent Path Finding.  In _Proceedings of the International Symposium on Combinatorial Search_ , volume 9, 2–9.
  * Berndt et al. (2020) Berndt, A.; Duijkeren, N. V.; Palmieri, L.; and Keviczky, T. 2020.  A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph.  In _ICAPS workshop on Distributed and Multi-Agent Planning_.
  * Coskun, O’Kane, and Valtorta (2021) Coskun, A.; O’Kane, J.; and Valtorta, M. 2021.  Deadlock-Free Online Plan Repair in Multi-Robot Coordination with Disturbances.  In _Proceedings of the International FLAIRS Conference_ , volume 34.
  * Erdmann and Lozano-Perez (1986) Erdmann, M.; and Lozano-Perez, T. 1986.  On Multiple Moving Objects.  In _Proceedings of the IEEE International Conference on Robotics and Automation_ , volume 3, 1419–1424.
  * Gange, Harabor, and Stuckey (2019) Gange, G.; Harabor, D.; and Stuckey, P. J. 2019.  Lazy CBS: Implicit Conflict-Based Search Using Lazy Clause Generation.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , volume 29, 155–162.
  * Hoenig et al. (2016) Hoenig, W.; Kumar, T. K.; Cohen, L.; Ma, H.; Xu, H.; Ayanian, N.; and Koenig, S. 2016.  Multi-Agent Path Finding with Kinematic Constraints.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , volume 26, 477–485.
  * Honig et al. (2018) Honig, W.; Preiss, J. A.; Kumar, T. K. S.; Sukhatme, G. S.; and Ayanian, N. 2018.  Trajectory Planning for Quadrotor Swarms.  _IEEE Transactions on Robotics_ , 34(4): 856–869.
  * Li et al. (2021a) Li, J.; Chen, Z.; Zheng, Y.; Chan, S.-H.; Harabor, D.; Stuckey, P. J.; Ma, H.; and Koenig, S. 2021a.  Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , volume 31, 477–485.
  * Li et al. (2021b) Li, J.; Harabor, D.; Stuckey, P. J.; Ma, H.; Gange, G.; and Koenig, S. 2021b.  Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search.  _Artificial Intelligence_ , 301: 103574.
  * Li, Ruml, and Koenig (2021) Li, J.; Ruml, W.; and Koenig, S. 2021.  EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, 12353–12362.
  * Ma et al. (2019) Ma, H.; Harabor, D.; Stuckey, P. J.; Li, J.; and Koenig, S. 2019.  Searching with Consistent Prioritization for Multi-Agent Path Finding.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, 7643–7650.
  * Ma, Kumar, and Koenig (2017) Ma, H.; Kumar, T. K. S.; and Koenig, S. 2017.  Multi-Agent Path Finding with Delay Probabilities.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 31, 3605–3612.
  * Okumura et al. (2023) Okumura, K.; Bonnet, F.; Tamura, Y.; and Défago, X. 2023.  Offline Time-Independent Multiagent Path Planning.  _IEEE Transactions on Robotics_ , 39(4): 2720–2737.
  * Okumura et al. (2019) Okumura, K.; Machida, M.; Défago, X.; and Tamura, Y. 2019.  Priority Inheritance with Backtracking for Iterative Multi-Agent Path Finding.  In _Proceedings of the International Joint Conference on Artificial Intelligence_ , 535–542.
  * Paul, Feng, and Li (2023) Paul, A.; Feng, Y.; and Li, J. 2023.  A Fast Rescheduling Algorithm for Real-Time Multi-Robot Coordination [Extended Abstract].  In _Proceedings of the International Symposium on Combinatorial Search_ , volume 16, 175–176.
  * Pecora et al. (2018) Pecora, F.; Andreasson, H.; Mansouri, M.; and Petkov, V. 2018.  A Loosely-Coupled Approach for Multi-Robot Coordination, Motion Planning and Control.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , volume 28, 485–493.
  * Sajid, Luna, and Bekris (2012) Sajid, Q.; Luna, R.; and Bekris, K. 2012.  Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives.  In _Proceedings of the International Symposium on Combinatorial Search_ , volume 3, 88–96.
  * Sharon et al. (2015) Sharon, G.; Stern, R.; Felner, A.; and Sturtevant, N. R. 2015.  Conflict-Based Search for Optimal Multi-Agent Pathfinding.  _Artificial Intelligence_ , 219: 40–66.
  * Stern et al. (2019) Stern, R.; Sturtevant, N.; Felner, A.; Koenig, S.; Ma, H.; Walker, T.; Li, J.; Atzmon, D.; Cohen, L.; Kumar, T. K.; Barták, R.; and Boyarski, E. 2019.  Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks.  In _Proceedings of the International Symposium on Combinatorial Search_ , volume 10, 151–158.
  * Varambally, Li, and Koenig (2022) Varambally, S.; Li, J.; and Koenig, S. 2022.  Which MAPF Model Works Best for Automated Warehousing?  In _Proceedings of the International Symposium on Combinatorial Search_ , volume 15, 190–198.
  * Wagner, Veerapaneni, and Likhachev (2022) Wagner, A.; Veerapaneni, R.; and Likhachev, M. 2022.  Minimizing Coordination in Multi-Agent Path Finding with Dynamic Execution.  In _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , volume 18, 61–69.

##  Appendix A More Results of the Anytime Behavior

In the paper, we plot the anytime behavior of BTPG-n and BTPG-o on map
warehouse. Here, we provide the results on other maps. Again, Scenes 1 and 2
are the instances with the longest and shortest runtime of BTPG-o in the
experiments for that map, respectively.

Figure A1: den520 Figure A2: Paris Figure A3: random Figure A4: empty Figure
A5: Berlin


# Super-resolution Method for Coherent DOA Estimation of Multiple Wideband
Sources

Milad Javadzadeh Jirhandeh  Mohammad Hossein Kahaei The authors are with the
School of Electrical Engineering, Iran University of Science & Technology,
Tehran 16846-13114, Iran (e-mail<EMAIL_ADDRESS>kahaei@iust.ac.ir).

###### Abstract

We focus on coherent direction of arrival estimation of wideband sources based
on spatial sparsity. This area of research is encountered in many applications
such as passive radar, sonar, mining, and communication problems, in which an
increasing attention has been devoted to improving the estimation accuracy and
robustness to noise. By the development of super-resolution algorithms,
narrowband direction of arrival estimation based on gridless sparse algorithms
and atomic norm minimization has already been addressed. In this paper, a
superresolution based method is proposed for coherent direction of arrival
estimation of multiple wideband sources. We introduce an atomic norm problem
by deﬁning a new set of atoms and exploiting the signal joint sparsity of
different frequency subbands in a continuous spatial domain. This problem is
then cast as a semideﬁnite program, which leads to implementing a new coherent
direction of arrival estimation method with higher resolution and more
robustness to noise. Numerical simulations show the outperformance of the
proposed method compared to the conventional ones.

###### Index Terms:

Atomic norm, gridless sparse, super-resolution, direction of arrival, coherent
estimation, wideband sources.

##  I Introduction

Wideband Direction of Arrival (DOA) estimation is popular due to its
application in many fields like sonar, radar, and wireless communications. In
these cases, the direction information is repeated in different frequency
bands, which can be exploited to improve the estimation precision. A
conventional approach is to decompose widebands into narrowbands using
specific filter banks or the Discrete Fourier Transformation (DFT) and use the
joint information of narrowband signals for DOA estimation. These techniques
can be classified into Incoherent Signal Subspace Methods (ISSM) and Coherent
Signal Subspace Methods (CSSM).

In the ISSM, widebands are first divided into narrowbands and a DOA estimation
method is applied to each band. The final DOA estimate is then calculated by
incoherently averaging the respective results [1, 2]. This approach, however,
suffers from a weak robustness concerning the noise and also loses its final
precision when high-magnitude errors take place in narrowband DOA estimates.
In the CSSM, on the other hand, using a focusing matrix all the center
frequencies of narrowband signals are mapped into a reference frequency to
which a narrowband DOA estimator is applied [3, 4]. For instance, the
Rotational Signal Subspace (RSS)[4] may be mentioned. However, a major
drawback to these methods is the need for an initial DOA estimate, which is
required for designing the focusing matrix. Motivated by this deficiency, a
coherent subspace method has been addressed based on interpolation in [5].
Moreover, to fill the gap between coherent and incoherent methods, some
methods have been developed by using the signal and noise subspaces in
different narrowband signals. For example, the Test of Orthogonality of
Projected Subspaces (TOPS) [6], and Weighted Squared TOPS (WS-TOPS) [7] have
been introduced. The main shortage of the aforementioned methods is the need
for a large number of snapshots for each narrowband signal. Also, the number
of DOAs should be known, a priori.

In contrast, sparse DOA estimation methods are more practical thanks to their
acceptable accuracy despite using a smaller number of snapshots. In [8, 9],
some sparse DOA estimation methods are developed for wideband sources based on
compressive sensing, in which the DOA space is discretized by a grid for the
likely values of DOAs. Then, the joint sparsity of the narrowband signals is
utilized for DOA estimation by only incorporating one snapshot of the signals.
However, the main difficulty with these methods occurs for the grid mismatch
where the actual position of DOAs does not exactly lie on the grid steps.
This, as a result, leads to effectively reducing the resolution of DOA
estimates.

To overcome such a difficulty in Compressed Sensing (CS), Cand$\grave{e}$s and
Fernandez-Granda extended the discrete CS to the continuous case by
introducing the super-resolution concept, which directly incorporates the
sparsity property in continuous domain [10]. Tang et al. [11] used the super-
resolution notion as a gridless sparse method for line spectral estimation by
atomic norm minimization. Afterwards, gridless DOA estimation has been
developed based on super-resolution for narrowband sources [12, 13], which can
also be applied for incoherent DOA estimation of wideband sources. However,
such approaches exhibit inherent disadvantages of conventional incoherent DOA
estimation techniques.

In this paper, by defining a new atomic norm, we propose a coherent gridless
sparse method for wideband DOA estimation based on super-resolution. The use
of coherency in this method guarantees more robustness to the noise. In
addition, by using only one snapshot of narrowband signals, a higher accuracy
is achieved compared to the classical methods. Also, no information is
required about the number of sources.

The paper is organized as follows. In Section II, the signal model is defined.
In Section III, we introduce a new atomic norm and propose the respective
gridless sparse recovery problem. The performance of our method is compared to
some well-known methods in Section IV and Section V concludes the results.

The following notations are respectively used in this work. Matrices and
vectors are represented by uppercase and lowercase bold letters,
${\left(\cdot\right)^{T}}$ and ${\left(\cdot\right)^{H}}$ denote transpose and
conjugate transpose operators, ${\left\|{\cdot}\right\|_{F}}$,
${\left\|{\cdot}\right\|_{\cal A}}$, and $\left\|{\cdot}\right\|_{\cal
A}^{*}\;$ show the Frobenius norm, atomic norm, and dual norm of atomic norm
for a matrix, $\mathop{\left\|{\cdot}\right\|}\nolimits_{2}$ is the $\ell_{2}$
norm of a vector. $conv({\cdot})$ and $Tr({\cdot})$ represent the convex hull
and trace operator, respectively, and $\bm{I}_{m}$ is an identity matrix of
size $m$.

##  II Data model

We consider a Uniform Linear Array (ULA) composed of $M$ omnidirectional
sensors with inter-spacing $d$. The number of sources is $K$ with the angles
${\theta_{k}}$, $k=1,\ldots,K$, which are constant during the observation
time. By applying the DFT, the array signal output is divided into $J$
narrowband signals from ${\omega_{L}}$ to ${\omega_{H}}$. Mathematically, we
can show the array output vector in ${\omega_{j}}$ as

${\bm{y}}\left({{\omega_{j}}}\right)={\bm{\Phi}}\left({{\omega_{j}},{\bm{\theta}}}\right){\bm{s}}\left({{\omega_{j}}}\right)+{\bm{n}}\left({{\omega_{j}}}\right)\;\;\;\;,\;\;j=1,\ldots,J,$
(1)

where
${\bm{y}}\left({{\omega_{j}}}\right)={\left[{{y_{1}}\left({{\omega_{j}}}\right),\;\ldots,{y_{M}}\left({{\omega_{j}}}\right)}\right]^{T}}\in\mathbb{C}^{M\times
1}$ with ${y_{m}}\left({{\omega_{j}}}\right)$, $m=1,\ldots,M$, representing
the DFT of the $m$th sensor output in
${\omega_{L}}\leq{\omega_{j}}\leq{\omega_{H}}$,
${\bm{s}}\left({{\omega_{j}}}\right)={\left[{{s_{1}}\left({{\omega_{j}}}\right)\;\ldots,{s_{K}}\left({{\omega_{j}}}\right)}\right]^{T}}\in\mathbb{C}^{K\times
1}$ with ${s_{k}}\left({{\omega_{j}}}\right)$ denoting the DFT of the $k$th
source, ${\bm{n}}\left({{\omega_{j}}}\right)\in\mathbb{C}^{M\times 1}$ is the
corresponding noise, and
${\bm{\Phi}}\left({{\omega_{j}},{\bm{\theta}}}\right)={\left[{{\bm{\phi}}\left({{\omega_{j}},{\theta_{1}}}\right),\;\ldots,{\bm{\phi}}\left({{\omega_{j}},{\theta_{K}}}\right)}\right]}\in\mathbb{C}^{M\times
K}$ shows the steering matrix for the DOA vector
${\bm{\theta}}={\left[{{\theta_{1}},\;\ldots,{\theta_{K}}}\right]^{T}}$ in
${\omega_{j}}$ whose columns are given by

$\begin{array}[]{l}{\bm{\phi}}\left({{\omega_{j}},{\theta_{k}}}\right)={\left[{\exp\left({-i{\omega_{j}}{\tau_{1,k}}}\right)\;,\ldots\;,\exp\left({-i{\omega_{j}}{\tau_{M,k}}}\right)\;}\right]^{T}},\end{array}$
(2)

where ${\tau_{m,k}}$ is the delay of the $k$th source with the arrival angle
${\theta_{k}}$ in the $m$th sensor defined as

$\begin{array}[]{l}{\tau_{m,k}}=\frac{{\left({m-1}\right)d\sin\left({{\theta_{k}}}\right)}}{c},\end{array}$
(3)

with $c$ showing the wave propagation speed. We assume that
${\omega_{1}}>{\omega_{2}}>\ldots>{\omega_{J}}$ and in order to avoid
ambiguity, $d$ is equal to the half of the minimum wavelength corresponding to
the maximum frequency ${\omega_{1}}$ [14], that is,

$d=\frac{{{\pi c}}}{\omega_{1}}.$ (4)

Using (3) and (4) in (2), we obtain

$\begin{array}[]{*{20}{l}}{{\bm{\phi}}\left({{\omega_{j}},{\theta_{k}}}\right)=\left[{\begin{array}[]{*{20}{c}}{\begin{array}[]{*{20}{c}}1\\\
{\exp\left({-i\frac{{{\omega_{j}}}}{{{\omega_{1}}}}\pi\sin\left({{\theta_{k}}}\right)}\right)}\end{array}}\\\
{\begin{array}[]{*{20}{c}}\vdots\\\
{\exp\left({-i\left({M-1}\right)\frac{{{\omega_{j}}}}{{{\omega_{1}}}}\pi\sin\left({{\theta_{k}}}\right)}\right)}\end{array}}\end{array}}\right].}\end{array}$
(5)

Next, by defining

$\begin{array}[]{l}{{\rm{\alpha}}_{j}}\triangleq\frac{{{\omega_{j}}}}{{{\omega_{1}}}},\\\
{f_{k}}\triangleq\frac{1}{2}\cos\left({{\theta_{k}}}\right),\end{array}$ (6)

where ${{\rm{\alpha}}_{j}}\leq 1$, ${{\rm{\alpha}}_{1}}=1$ and
${\bm{f}}={\left[{{f_{1}},\;\ldots,{f_{K}}}\right]^{T}}\in{\left[{-\frac{1}{2},\frac{1}{2}}\right]}$
as the spatial frequencies of the DOAs, we can show

${\bm{\phi}}\left({{\omega_{j}},{\theta_{k}}}\right)={\bm{a}}\left({f}\right),$
(7)

where

$\begin{array}[]{*{20}{l}}{{\bm{a}}\left({f}\right)=\left[1,{\exp\left({-i2\pi{f}}\right)\;},\ldots,{\exp\left({-i\left({M-1}\right)2\pi{f}}\right)\;}\right]^{T}}\end{array}$
(8)

and $f={\alpha_{j}}{f_{k}}$. According to (8), we can reformulate (1) as

${\bm{y}}\left({{\omega_{j}}}\right)={\left[{\bm{a}}\left({{\alpha_{j}}{f_{1}}}\right),\;\ldots,{\bm{a}}\left({{\alpha_{j}}{f_{K}}}\right)\right]}{\bm{s}}\left({{\omega_{j}}}\right)+{\bm{n}}\left({{\omega_{j}}}\right),$
(9)

from which our gridless sparse method for estimating ${\bm{f}}$ and
subsequently the DOAs of wideband sources can be derived.

##  III Proposed gridless sparse method for wideband DOA estimation

We assume that the focusing matrices ${{\bm{T}}_{j}}\in\mathbb{C}^{M\times
M}$, $j=1,\ldots,J$, satisfy the following properties,

$\begin{array}[]{l}{\bm{a}}\left({{{\rm{\alpha}}_{j}}f}\right)={{\bm{T}}_{j}}{\bm{a}}\left({{{\rm{\alpha}}_{1}}f}\right)+{{\bm{e}}_{j}}\left(f\right)\\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;={{\bm{T}}_{j}}{\bm{a}}\left(f\right)+{{\bm{e}}_{j}}\left(f\right),\end{array}$
(10)

in which ${{\bm{e}}_{j}}\left(f\right)$ is the focusing error vector in
${\omega_{j}}$ for the DOA spatial frequency
$f\in\left[{-\frac{1}{2},\frac{1}{2}}\right]$. This model shows that
${\bm{a}}\left({{{\rm{\alpha}}_{j}}f}\right)$ can linearly be approximated by
${\bm{a}}\left(f\right)$ and ${{\bm{T}}_{j}}$, in the sense that
${\bm{a}}\left(f\right)$ with the spatial frequency $f$ can be focused on the
lower frequencies, ${{\alpha}_{j}}f$. This lets us to design a more accurate
and efficient focusing matrix as follows.
To generate the focusing matrices ${{\bm{T}}_{j}}$, we use the method
developed in [5] to get

$\begin{array}[]{l}{{\bm{T}}_{j}}=\left[{\begin{array}[]{*{20}{c}}{{{\bm{T}}_{j}}\left({1,1}\right)}&\ldots&{{{\bm{T}}_{j}}\left({1,M}\right)}\\\
\vdots&\ddots&\vdots\\\
{{{\bm{T}}_{j}}\left({M,1}\right)}&\ldots&{{{\bm{T}}_{j}}\left({M,M}\right)}\end{array}}\right],\\\
\end{array}$ (11)

where
${{\bm{T}}_{j}}\left({m,m^{\prime}}\right)=sinc\left({{{\rm{\alpha}}_{j}}\left({m-1}\right)-\left({m^{\prime}-1}\right)}\right)$,
and $m,m^{\prime}=1,\ldots,M.$ Note that for ${\alpha_{1}}=1$, we get
${{\bm{T}}_{1}}={{\bm{I}}_{M}}$.

Using the output vectors of adjacent sensors given by (9) and using (10), the
array output matrix
${\bm{Y}}=\left[{{\bm{y}}\left({{\omega_{1}}}\right),\ldots,{\bm{y}}\left({{\omega_{J}}}\right)}\right]\in\mathbb{C}^{M\times
J}$ is obtained as

${\bm{Y}}=\mathop{\sum}\limits_{k=1}^{K}{\beta_{k}}{\bm{A}}\left({{f_{k}},{{\bm{c}}_{k}}}\right)+{\bm{N}}+{\bm{E}},$
(12)

where
${\bm{A}}\left({f_{k},{\bm{c}_{k}}}\right)=\left[{{{\bm{T}}_{1}}{\bm{a}}\left(f_{k}\right),\ldots,{{\bm{T}}_{J}}{\bm{a}}\left(f_{k}\right)}\right]\times
diag\left({\bm{c}_{k}}\right)$, ${\beta_{k}}$ and ${{\bf{c}}_{k}}$ are defined
according to (9) as

$\begin{array}[]{l}{\beta_{k}}=\;\mathop{\left\|{\left[{\begin{array}[]{*{20}{c}}{{s_{k}}\left({{\omega_{1}}}\right)}\\\
\vdots\\\
{{s_{k}}\left({{\omega_{J}}}\right)}\end{array}}\right]}\right\|}\nolimits_{2},\;\;{{\bm{c}}_{k}}={\left[{\begin{array}[]{*{20}{c}}{{s_{k}}\left({{\omega_{1}}}\right)}\\\
\vdots\\\
{{s_{k}}\left({{\omega_{J}}}\right)}\end{array}}\right]}/{\beta_{k}},\\\
\end{array}$

and the noise and focusing error matrices ${\bm{N}}$ and ${\bm{E}}$ are
respectively given by

$\begin{array}[]{l}{\bm{N}}=\left[{{\bm{n}}\left({{\omega_{1}}}\right),\ldots,{\bm{n}}\left({{\omega_{J}}}\right)}\right]\in\mathbb{C}^{M\times
J},\\\
\;{\bm{E}}=\left[{{{\bm{\acute{e}}}_{1}},\ldots,{{\bm{\acute{e}}}_{J}}}\right]\in\mathbb{C}^{M\times
J},\\\
\;{{\bm{\acute{e}}}_{j}}=\left[{{{\bm{e}}_{j}}\left({{f_{1}}}\right),\;\ldots,{{\bm{e}}_{j}}\left({{f_{K}}}\right)}\right]\times{\bm{s}}\left({{\omega_{j}}}\right).\end{array}$

In this way, the noiseless array output matrix is
${\bm{X^{\star}}}=\mathop{\sum}\nolimits_{k=1}^{K}{\beta_{k}}{\bm{A}}\left({{f_{k}},{{\bm{c}}_{k}}}\right),$
which can be recovered from the array output matrix in order to estimate the
DOA spatial frequencies vector $\bm{f}$. For this purpose, we define the set
of atoms as

$\begin{array}[]{l}{\cal
A}=\\{{\bm{A}}\left({f,{\bm{c}}}\right)=\left[{{{\bm{T}}_{1}}{\bm{a}}\left(f\right),\ldots,{{\bm{T}}_{J}}{\bm{a}}\left(f\right)}\right]\times
diag\left({\bm{c}}\right){\rm{|}}\\\
\;\;\;\;\;\;\;\;\;\;f\in\left[{-\frac{1}{2},\frac{1}{2}}\right],{\bm{c}}\in\mathbb{C}^{J\times
1},\;{\left\|{\bm{c}}\right\|_{2}}=1\\},\end{array}$

by which the atomic norm is defined for ${\bm{X}}$ as

$\begin{array}[]{l}{{\left\|{\bm{X}}\right\|}_{\cal
A}}={\rm{inf}}\\{t>0{\rm{\;}}:{\bm{X}}\in t\;conv\left({\cal A}\right)\\}\\\
\begin{array}[]{l}\;\;\;\;\;\;\;\;\;=\mathop{\inf}\limits_{{f_{k}},{\beta_{k}},{{\bm{c}}_{k}}}\\{\mathop{\sum}\nolimits_{k}{\beta_{k}}\;:{\bm{X}}=\mathop{\sum}\nolimits_{k}{\beta_{k}}{\bm{A}}\left({{f_{k}},{{\bm{c}}_{k}}}\right),\\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{f_{k}}\in\left[{-\frac{1}{2},\frac{1}{2}}\right],\;\left\|{{\bm{c}}_{k}}\right\|_{2}=1,{\beta_{k}}>0\\}.\end{array}\end{array}$
(13)

Assuming that the sum of the noise power and focusing error power is equal to
$\left\|{\bm{N}}\right\|_{F}^{2}+\left\|{\bm{E}}\right\|_{F}^{2}=\gamma$ and
that the number of sources is small, we propose the following sparse problem
for coherent estimation of wideband DOAs,

$\begin{array}[]{l}\mathop{\min}\limits_{{\bm{X}}}\;{\left\|{{\bm{X}}}\right\|_{\cal
A}}\\\
subject\;to\;\;{\left\|{{\bm{X}}-{\bm{Y}}}\right\|_{F}}\leq\;\sqrt{\gamma}.\end{array}$
(14)

The optimum matrix ${{\bm{X}}_{opt}}$ resulted from (14); which is an estimate
of the noiseless data matrix ${\bm{X^{\star}}}$, can be described by its atoms
as

${{\bm{X}}_{opt}}=\mathop{\sum}\limits_{k=1}^{\widehat{K}}{\widehat{\beta}_{k}}{\bm{A}}\left({{{\widehat{f}}_{k}},{{\widehat{\bm{c}}}_{k}}}\right),$
(15)

where ${\widehat{\beta}_{k}}$ ,${{\widehat{f}}_{k}}$, and
${{\widehat{\bm{c}}}_{k}}$ are the estimates of true
${\beta_{k}}$,${{f}_{k}}$, and ${{\bm{c}}_{k}}$, respectively, and
${\widehat{K}}$ is an estimate of real source numbers ${K}$.

To solve the primal problem in (14) and estimate the DOAs from the atoms of
${\bm{X}}_{opt}$, we present its Lagrangian dual problem as

$\begin{array}[]{l}\mathop{{\rm{m}}ax}\limits_{\bm{H}}Re\left\\{{Tr\left({{{\bm{Y}}^{H}}{\bm{H}}}\right)}\right\\}-\sqrt{\gamma}{\left\|{\bm{H}}\right\|_{F}}\\\
subject\;to\;\;\left\|{\bm{H}}\right\|_{\cal A}^{*}\leq 1\end{array},$ (16)

where $\left\|\cdot\right\|_{\cal A}^{*}\;$ shows the dual atomic norm. Since
${\bm{X}}={\bm{Y}}$ is a feasible solution for (14), strong duality holds
according to Slater’s condition [15].

With the assumption of
${\bm{H}}=\left[{{{\bm{h}}_{1}},\ldots,{{\bm{h}}_{J}}}\right]\in\mathbb{C}^{M\times
J}$, the dual atomic norm $\left\|{\bm{H}}\right\|_{\cal A}^{*}$ in (16) is
defined as

$\begin{array}[]{l}\left\|{\bm{H}}\right\|_{\cal
A}^{*}=\mathop{\sup}\limits_{\;{{\left\|{\bm{X}}\right\|}_{\cal A}}\leq
1}Re\left\\{{Tr\left({{{\bm{H}}^{H}}{\bm{X}}}\right)}\right\\}\\\
\;\;\;\;\;\;\;\;\;\;\;=\mathop{\sup}\limits_{f\in\left[{-\frac{1}{2},\frac{1}{2}}\right]\;,\;\;\;\left\|{{\bm{c}}_{k}}\right\|_{2}=1}Re\left\\{{Tr\left({{{\bm{H}}^{H}}{\bm{A}}\left({f,{\bm{c}}}\right)}\right)}\right\\}\\\
\;\;\;\;\;\;\;\;\;\;\;=\mathop{\sup}\limits_{f\in\left[{-\frac{1}{2},\frac{1}{2}}\right]\;,\;\;\;\left\|{{\bm{c}}_{k}}\right\|_{2}=1}Re\left\\{{{{\bm{c}}^{T}}\left[{\begin{array}[]{*{20}{c}}{{{({\bm{T}}_{1}^{H}{{\bm{h}}_{1}})}^{H}}{\bm{a}}\left(f\right)}\\\
\vdots\\\
{{{({\bm{T}}_{J}^{H}{{\bm{h}}_{J}})}^{H}}{\bm{a}}\left(f\right)}\end{array}}\right]}\right\\}\\\
\;\;\;\;\;\;\;\;\;\;\;=\mathop{\max}\limits_{f\in\left[{-\frac{1}{2},\frac{1}{2}}\right]\;}{\left\|{\left[{\begin{array}[]{*{20}{c}}{{{({\bm{T}}_{1}^{H}{{\bm{h}}_{1}})}^{H}}{\bm{a}}\left(f\right)}\\\
\vdots\\\
{{{({\bm{T}}_{J}^{H}{{\bm{h}}_{J}})}^{H}}{\bm{a}}\left(f\right)}\end{array}}\right]}\right\|_{2}},\end{array}$
(17)

where for the last expression, we have used the Cauchy-Schwarz inequality
$\begin{array}[]{l}Re\left\\{{{{\bm{p}}^{H}}{{\bm{q}}}}\right\\}\leq{\left\|\bm{p}\right\|_{2}}{\left\|\bm{q}\right\|_{2}},\\\
\end{array}$ which is held for any vectors $\bm{p}$ and $\bm{q}$ of the same
size. Next, we describe the primal in (16) in the form of a Semidefinite
Programming (SDP). For this purpose, the condition
$\left\|{\bm{H}}\right\|_{\cal A}^{*}\leq 1$ should be expressed in the form
of an SDP condition, for which we present the following proposition.

######  Proposition 1.

For matrices
${\bm{H}}=\left[{{{\bm{h}}_{1}},\ldots,{{\bm{h}}_{J}}}\right]\in\mathbb{C}^{M\times
J}$,
$\overline{\bm{H}}=\left[{{\bm{T}}_{1}^{H}{{\bm{h}}_{1}},\ldots,{\bm{T}}_{J}^{H}{{\bm{h}}_{J}}}\right]\in\mathbb{C}^{M\times
J}$, and ${{\bm{T}}_{j}}\in\mathbb{C}^{M\times M}$, $j=1,\ldots,J$, if there
exists a Hermitian matrix ${\bm{Q}}\in\mathbb{C}^{M\times M}$ with the
condition

$\begin{array}[]{l}\left[{\begin{array}[]{*{20}{c}}{\bm{Q}}&{\overline{\bm{H}}}\\\
{{{\overline{\bm{H}}}^{H}}}&{{{\bm{I}}_{J}}}\end{array}}\right]\succeq 0\\\
\\\ \end{array}$ (18)

and

$\sum\limits_{n=1}^{M-m}{\mathop{Q}\nolimits_{n,n+m}}=\begin{cases}1,&m=0\\\
0,&m=1,...,M-1,\end{cases}$ (19)

the inequality

$\left\|{\bf{H}}\right\|_{\cal
A}^{*}=\mathop{\max}\limits_{f\in\left[{-\frac{1}{2},\frac{1}{2}}\right]\;}{\left\|{{{{\overline{\bf{H}}}^{H}}{\bm{a}}(f)}}\right\|_{2}}\leq
1$ (20)

is satisfied. Reciprocally, the relationship (20) implies (18) and (19).

###### Proof.

With the Schur complement, (18) holds, if and only if,

${\bm{Q}}\succeq 0$

and

${\bm{Q}}-{\overline{\bm{H}}}\;{{\overline{\bm{H}}}^{H}}\succeq 0.$

Thus, for any ${\bm{a}}(f)$ and
$f\in{\left[{-\frac{1}{2},\frac{1}{2}}\right]}$, we get

$\mathop{\left\|{{{\overline{\bm{H}}}^{H}}{\bm{a}}(f)}\right\|}\nolimits_{2}^{2}\leq{{\bm{a}}(f)^{H}}{\bm{Q}}{\bm{a}}(f).$

But from (19), we have ${{\bm{a}}(f)^{H}}{\bm{Q}}{\bm{a}}(f)=1$ and
subsequently (20) is proved. The reciprocal proof is derived by backward
reasoning.
∎

Now, using Proposition 1, the optimisation problem in (16) can be represented
by the following SDP problem,

$\begin{array}[]{l}\mathop{\max}\limits_{\bm{H,Q}}Re\left\\{{Tr\left({{{\bm{Y}}^{H}}{\bm{H}}}\right)}\right\\}-\sqrt{\gamma}{\left\|{\bm{H}}\right\|_{F}}\\\
\\\
subject\;to\;\;\;\left[{\begin{array}[]{*{20}{c}}{\bm{Q}}&{\overline{\bm{H}}}\\\
\\\ {{{\overline{\bm{H}}}^{H}}}&{{{\bm{I}}_{J}}}\end{array}}\right]\succeq
0,\\\ \\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\overline{\bm{H}}=\left[{{\bm{T}}_{1}^{H}{{\bm{h}}_{1}},\ldots,{\bm{T}}_{J}^{H}{{\bm{h}}_{J}}}\right],\\\
\\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\sum\limits_{n=1}^{M-m}{\mathop{Q}\nolimits_{n,n+m}}=\begin{cases}1,&m=0,\\\
0,&m=1,...,M-1,\end{cases}\\\ \\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\bm{Q}}\;is\;Hermitian.\end{array}$
(21)

From (21), the optimum solutions
${{\bm{H}}_{opt}}=\left[{{{\bm{h}}_{{\rm{}}{1_{opt}}}},\ldots,{{\bm{h}}_{{\rm{}}{J_{opt}}}}}\right]$
and
${\overline{\bm{H}}_{opt}}=\left[{{\bm{T}}_{1}^{H}\mathop{\bm{h}}\nolimits_{\mathop{1}\nolimits_{opt}},\ldots,{\bm{T}}_{J}^{H}\mathop{\bm{h}}\nolimits_{\mathop{J}\nolimits_{opt}}}\right]$
are obtained and DOAs are subsequently estimated based on Theorem 1.

######  Theorem 1.

If ${{\bm{X}}_{opt}}$ and ${\overline{\bm{H}}_{opt}}$ are the solutions of the
primal and dual problems in (14) and (21), respectively, then the estimates of
DOA frequencies in (15), ${\widehat{f}_{k}}$, and $k=1,\ldots,\widehat{K}$
will satisfy,

${\left\|{\left[{\mathop{\mathop{\overline{\bm{h}}}\nolimits_{1}^{H}}\nolimits_{opt}{\bm{a}}\left({{{\widehat{f}}_{k}}}\right)},\ldots,{\mathop{\mathop{\overline{\bm{h}}}\nolimits_{J}^{H}}\nolimits_{opt}{\bm{a}}\left({{{\widehat{f}}_{k}}}\right)}\right]^{T}}\right\|_{2}}=1,$
(22)

and

${\widehat{\bm{c}}_{k}}={\left[{\overline{\bm{h}}{{{}_{1}^{H}}_{opt}}{\bm{a}}\left({{{\hat{f}}_{k}}}\right),\ldots,\overline{\bm{h}}{{{}_{J}^{H}}_{opt}}{\bm{a}}\left({{{\hat{f}}_{k}}}\right)}\right]^{H}}.$
(23)

The proof of Theorem 1 is given in Appendix A.

In this way, by estimating ${{\bm{X}}_{opt}}$, its atoms are used to compute
${{{\widehat{f}}_{k}}}$, as the estimates of $f_{k}$, and afterwards the DOAs
of wideband sources are found.

##  IV Numerical simulations

We consider an underwater scenario with a ULA composed of $M=16$ hydrophones
and $c=1500m/s$. Source signals are random waves with 512 samples, whose
bandwidths in discrete frequency domain lie in $[\pi/3,2\pi/3]$. Also, a
60-point DFT is applied to the received signals, where the number of the
selected frequency bins is $J=10$, and the measuring noise in (6) is zero mean
white Gaussian with variance ${{\sigma_{noise}^{2}}}$.

The performance of the WGS algorithm is compared to that of the RSS and WS-
TOPS methods.

The initial values for the RSS are the true DOAs added up with some errors
within $\pm\mathop{2}\nolimits^{\circ}$ randomly chosen from a uniform
distribution. Moreover, as a required information, we provide the true number
of sources for both RSS and WS-TOPS methods. Simulation results are presented
by averaging $100$ independent trials of each experiment.

In the first experiment, we consider three sources located at
${\bm{\theta}}=[{-5}^{\circ},15^{\circ},40^{\circ}]^{T}$. The results are
compared in Fig. 1 in RootMean-Squared Error (RMSE) sense at different SNRs.
As seen, the RSS generates the largest RMSE, mainly due to the impact of error
on the initial values which could dominate the noise effect. Furthermore, WS-
TOPS achieves a better performance and WGS offers the least RMSE.

Figure 1: RMSEs for WGS, RSS, and WS-TOPS methods for three sources at
${\bm{\theta}}=[{-5}^{\circ},15^{\circ},40^{\circ}]^{T}$ and different SNRs.

In the next experiment, we investigate the resolution of the estimators for
different DOA angles at 10 dB SNR. The first DOA is fixed at
${\theta_{1}}=\mathop{40}\nolimits^{\circ}$ and the second DOA varies between
${\theta_{2}}=\left[{\mathop{28}\nolimits^{\circ},\mathop{37}\nolimits^{\circ}}\right]$.
The RMSEs are shown for $\Delta\theta={\theta_{1}}-{\theta_{2}}$ in Table I.
One can see that the WS-TOPS is unable to estimate the DOAs for
$\Delta\theta<\mathop{11}\nolimits^{\circ}$, which is due to needing more
snapshots for a better performance. These values are less than
$\mathop{6}\nolimits^{\circ}$ and $\mathop{3}\nolimits^{\circ}$ for the RSS
and WGS, respectively.

TABLE I: RMSEs for WGS, RSS, and WS-TOPS methods for different resolutions. $\Delta\theta$ (Degree) | 12 | 11 | 10 | 9 | 8
---|---|---|---|---|---
WGS (Proposed) | 0.5662 | 0.5460 | 0.6209 | 0.7315 | 0.7490
WS-TOPS [7] | 0.6768 | 0.6256 | Failed | Failed | Failed
RSS [4] | 1.0631 | 1.0838 | 1.1266 | 1.1666 | 1.1066
$\Delta\theta$ (Degree) | 7 | 6 | 5 | 4 | 3
WGS (Proposed) | 0.7510 | 0.8984 | 1.1119 | 1.1117 | 1.2242
WS-TOPS [7] | Failed | Failed | Failed | Failed | Failed
RSS [4] | 1.0526 | 1.0728 | Failed | Failed | Failed

##  V Conclusion

We proposed a coherent gridless sparse method for wideband DOA estimation by
defining a new atomic norm and solving the corresponding SDP. Simulations
results demonstrate that this method is more robustness to noise with a better
resolution compared to the RSS and WS-TOPS methods. Moreover, this super-
resolution based method needs no knowledge about the number of sources.

###  -A Proof of Theorem 1

From the strong duality theorem for the optimal solutions of primal and dual
problems, ${\bm{X}_{opt}}$ and ${\bm{H}_{opt}}$ in (14) and (21),
respectively, we get

$\begin{array}[]{l}\mathop{\left\|{\mathop{{\bm{X}}}\nolimits_{opt}}\right\|}\nolimits_{\cal
A}\;=Re\left\\{{Tr\left({{{\bm{Y}}^{H}}{{\bm{H}}_{opt}}}\right)}\right\\}-\sqrt{\gamma}{\left\|{\bm{H}_{opt}}\right\|_{F}}\\\
=Re\left\\{{Tr\left({\mathop{{\bm{X}}}\nolimits_{opt}^{H}{{\bm{H}}_{opt}}}\right)}\right\\}\\\
+Re\left\\{{Tr\left({{{\left({{\bm{Y}}-\mathop{{\bm{X}}}\nolimits_{opt}}\right)}^{H}}{{\bm{H}}_{opt}}}\right)}\right\\}-\sqrt{\gamma}{\left\|{\bm{H}_{opt}}\right\|_{F}}\\\
\leq
Re\left\\{{Tr\left({\mathop{{\bm{X}}}\nolimits_{opt}^{H}{{\bm{H}}_{opt}}}\right)}\right\\}.\end{array}$
(-A.1)

The last inequality has been written using the constraint in (14), where we
have
${\left\|{{\left({{\bm{Y}}-\mathop{{\bm{X}}}\nolimits_{opt}}\right)}}\right\|_{F}}\leq\sqrt{\gamma}$,
and incorporating the following Cauchy-–Schwarz inequality,

$Re\left\\{{Tr\left({{{\left({{\bm{Y}}-\mathop{{\bm{X}}}\nolimits_{opt}}\right)}^{H}}{{\bm{H}}_{opt}}}\right)}\right\\}\leq{\left\|{{\left({{\bm{Y}}-\mathop{{\bm{X}}}\nolimits_{opt}}\right)}}\right\|_{F}}{\left\|{\bm{H}_{opt}}\right\|_{F}}.$

On the other hand, from the dual norm definition, we can write,

$\begin{array}[]{l}Re\left\\{{Tr\left({\mathop{{\bm{X}}}\nolimits_{opt}^{H}{{\bm{H}}_{opt}}}\right)}\right\\}\leq\;\mathop{\left\|{\mathop{{\bm{X}}}\nolimits_{opt}}\right\|}\nolimits_{\cal
A}\mathop{\left\|{{{\bm{H}}_{opt}}}\right\|}\nolimits_{\;{\cal A}}^{*}\\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\leq\;\mathop{\left\|{\mathop{{\bm{X}}}\nolimits_{opt}}\right\|}\nolimits_{\cal
A},\end{array}$ (-A.2)

and thus from (-A.1) and (-A.2), the relationship

$\mathop{\left\|{\mathop{{\bm{X}}}\nolimits_{opt}}\right\|}\nolimits_{\cal
A}=Re\left\\{{Tr\left({\mathop{{\bm{X}}}\nolimits_{opt}^{H}{{\bm{H}}_{opt}}}\right)}\right\\},$

holds. Using (15) and the Cauchy–-Schwarz inequality, the latter expression
leads to

$\begin{array}[]{l}{\left\|{{{{\bm{X}}}_{opt}}}\right\|_{A}}\\\
=Re\left\\{Tr\left(\mathop{\bm{H}}\nolimits_{opt}^{H}\sum\limits_{k=1}^{\hat{K}}{{{\hat{\beta}}_{k}}}[{\hat{c}_{1}}\mathop{T}\nolimits_{1}{\bm{a}}({\hat{f}_{k}}),...,{\hat{c}_{J}}\mathop{T}\nolimits_{J}{\bm{a}}({\hat{f}_{k}})]\right)\right\\}\\\
=\mathop{\sum}\limits_{k=1}^{\widehat{K}}{\widehat{\beta}_{k}}Re\left\\{{\widehat{\bm{c}}_{k}^{T}\left[{\begin{array}[]{*{20}{c}}{{{({\bm{T}}_{1}^{H}\mathop{\bm{h}}\nolimits_{\mathop{1}\nolimits_{opt}})}^{H}}{\bm{a}}\left({{{\widehat{f}}_{k}}}\right)}\\\
\vdots\\\
{{{({\bm{T}}_{J}^{H}\mathop{\bm{h}}\nolimits_{\mathop{J}\nolimits_{opt}})}^{H}}{\bm{a}}\left({{{\widehat{f}}_{k}}}\right)}\end{array}}\right]}\right\\}\leq\mathop{\sum}\limits_{k=1}^{\widehat{K}}{\widehat{\beta}_{k}},\end{array}$
(-A.3)

in which we incorporated (16 and (17) to show that,

$\left\|{\left[{{{({\bm{T}}_{1}^{H}\mathop{\bm{h}}\nolimits_{\mathop{1}\nolimits_{opt}})}^{H}}{\bm{a}}\left({{{\widehat{f}}_{k}}}\right)},\ldots,{{{({\bm{T}}_{J}^{H}\mathop{\bm{h}}\nolimits_{\mathop{J}\nolimits_{opt}})}^{H}}{\bm{a}}\left({{{\widehat{f}}_{k}}}\right)}\right]^{T}}\right\|_{2}\leq
1.$

Since from (15), we obtain
${\left\|{{{{\bm{X}}}_{opt}}}\right\|_{A}}=\mathop{\sum}\limits_{k=1}^{\widehat{K}}{\widehat{\beta}_{k}}$,
(-A.3) is only satisfied for the equalities (22, and (23, which complete the
proof.

## References

  * [1] G. Su and M. Morf, “The signal subspace approach for multiple wide-band emitter location,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 31, no. 6, pp. 1502–1522, 1983.
  * [2] T. N. Ferreira, S. L. Netto, and P. S. Diniz, “Direction-of-arrival estimation using a low-complexity covariance-based approach,” IEEE Transactions on Aerospace and Electronic Systems, vol. 48, no. 3, pp. 1924–1934, 2012.
  * [3] Y. H. Choi, “Repeated blocking based robust beamforming for coherent interference cancellation,” Digital Signal Processing, vol. 36, pp. 39–45, 2015.
  * [4] H. Hung and M. Kaveh, “Focussing matrices for coherent signal-subspace processing,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 36, no. 8, pp. 1272–1281, 1988.
  * [5] M. Javadzadeh Jirhandeh, H. Hezaveh, and M. H. Kahaei, “Efficient design of focusing matrix for fast coherent DOA estimation of wideband sources,” Electronics Letters, 2020, Submitted.
  * [6] Y. S. Yoon, L. M. Kaplan, and J. H. McClellan, “TOPS: New DOA estimator for wideband signals,” IEEE Transactions on Signal processing, vol. 54, no. 6, pp. 1977–1989, 2006.
  * [7] H. Hayashi and T. Ohtsuki, “DOA estimation for wideband signals based on weighted squared TOPS,” EURASIP Journal on Wireless Communications and Networking, vol. 2016, no. 1, p. 243, 2016.
  * [8] C. Liu, Y. V. Zakharov, and T. Chen, “Broadband underwater localization of multiple sources using basis pursuit de-noising,” IEEE Transactions on Signal Processing, vol. 60, no. 4, pp. 1708–1717, 2011.
  * [9] N. Hu, X. Xu, and Z. Ye, “DOA estimation for wideband signals based on sparse signal reconstruction using prolate spheroidal wave functions,” Signal Processing, vol. 96, pp. 395–400, 2014.
  * [10] E. J. Candès and C. Fernandez-Granda, “Towards a mathematical theory of super-resolution,” Communications on pure and applied Mathematics, vol. 67, no. 6, pp. 906–956, 2014.
  * [11] G. Tang, B. N. Bhaskar, P. Shah, and B. Recht, “Compressed sensing off the grid,” IEEE transactions on information theory, vol. 59, no. 11, pp. 7465–7490, 2013.
  * [12] A. G. Raj and J. H. McClellan, “Single snapshot super-resolution DOA estimation for arbitrary array geometries,” IEEE Signal Processing Letters, vol. 26, no. 1, pp. 119–123, 2018.
  * [13] D. Castanheira and A. Gameiro, “Low complexity and high-resolution line spectral estimation using cyclic minimization,” IEEE Transactions on Signal Processing, vol. 67, no. 24, pp. 6285–6300, 2019.
  * [14] F. Sellone, “Robust auto-focusing wideband DOA estimation,” Signal Processing, vol. 86, no. 1, pp. 17–37, 2006.
  * [15] S. Boyd and L. Vandenberghe, Convex optimization.  Cambridge university press, 2004.


# Fibonacci-Lucas Spinors Obtained from Hybrid Numbers

Selime Beyza Özçevik  Department of Mathematics,Ondokuz Mayıs
University,55139, Samsun,Turkey<EMAIL_ADDRESS>Abdullah Dertli
Department of Mathematics,Ondokuz Mayıs University,55139, Samsun,Turkey
<EMAIL_ADDRESS>Savaş Karaahmetoğlu  Akpınar Science High School,
55760, Samsun
Turkey<EMAIL_ADDRESS>
(Date: January 1, 2004)

###### Abstract.

The aim of this work is to provide the contributors to journals or Hybrid
numbers, akin to spinors, possess a broad range of applications in
mathematical physics, geometry, and mathematics. In this study, these two
significant topics were collectively addressed, introducing a new perspective
to spinors and defining hybrid spinors, from which several basic properties
were derived. Furthermore, by considering the Fibonacci and Lucas number
sequences, subjects widely explored in number theory, the study defined hybrid
Fibonacci and Lucas spinor sequences, examining some of their properties.
Lastly, hybrid Fibonacci and Lucas polynomial spinor sequences have been
introduced through the utilization of the polynomials associated with these
number sequences.

###### Key words and phrases:

Fibonacci numbers, Hybrid numbers, Spinors

###### 1991 Mathematics Subject Classification:

Primary 15A66; Secondary 11R09, 11Y55

##  1\. Introduction

Complex, hyperbolic, and dual numbers represent established two-dimensional
number systems that have garnered considerable attention from researchers,
particularly in the past century. Numerous scholars have explored the
geometric and physical applications inherent in these numerical constructs.
Much like how complex numbers facilitate the description of Euclidean plane
geometry, hyperbolic numbers find application in characterizing the geometry
of the Minkowski plane, while dual numbers are employed to articulate the
geometry of the Galilean plane [8]. n scholarly discourse, hyperbolic numbers
are denoted by various terms such as ’spacetime,’ ’double,’ ’perplex,’ and
’split-complex numbers,’ as indicated in the literature [1, 2, 6, 7]. This
number system constitutes a generalization encompassing the characteristics of
complex, hyperbolic, and dual number systems. These mathematical structures,
utilized in diverse disciplines, exhibit various relationships among
themselves, underscoring the significance of understanding and applying
mathematical diversity.Hybrid numbers are a mathematical structure that
typically combines real numbers with complex numbers, exhibiting broad
applications in mathematics. This structure provides an extended version of
the complex plane. Simultaneously, spinors are mathematical objects playing a
crucial role in quantum mechanics and theoretical physics. Represented often
by complex numbers or matrices, spinors are utilized to model the rotational
motion of particles around their own axis. Hybrid numbers and spinors are
structural elements of critical importance in mathematical physics and
theoretical physics, serving to comprehend the fundamental properties of the
universe and explain the behaviors of fundamental particles.

##  2\. Preliminaries

Hybrid numbers were initially introduced in [5]. Drawing upon this study, we
have incorporated essential concepts necessary for our own research, as
outlined below. Further information on hybrid numbers can be found in [5].

The set of hybrid numbers, denoted by $\mathbb{K}$, is defined as

$\mathbb{K}=\left\\{a+bi+c\varepsilon+dh;a,b,c,d\in\mathbb{R},i^{2}=-1,\varepsilon^{2}=0,h^{2}=1,ih=-hi=\varepsilon+i^{2}\right\\}.$

This set of numbers can be thought as a set of quadruplet. And a real,
complex, dual and hyperbolic units are defined as

$1\longleftrightarrow(1,0,0,0),i\leftrightarrow(0,1,0,0),\varepsilon\leftrightarrow(0,0,1,0),h\longleftrightarrow(0,0,0,1)$

respectively.

Let $Z,W\in\mathbb{K}$ be two hybrid numbers. The sum of two hybrid numbers is
defined by summing their components. The Hybridian product

$ZW=\left(a_{1}+b_{1}i+c_{1}\varepsilon+d_{1}h\right)\left(a_{2}+b_{2}i+c_{2}\varepsilon+d_{2}h\right)$

is obtained by distributing the terms on the right.

The conjugate of a hybrid number $Z=a+bi+c\varepsilon+dh$, denoted by
$\bar{Z}$, is defined as

$\bar{Z}=a-bi-c\varepsilon-dh.$

The scalar product in the hybrid numbers is defined as follows

$\displaystyle g(p,q):K\times K\longrightarrow\mathbb{R}$ $\displaystyle
g\left(Z_{1},Z_{2}\right)=\frac{Z_{1}\overline{Z_{2}}+Z_{2}\overline{Z_{1}}}{2}$
$\displaystyle=a_{1}a_{2}+b_{1}b_{2}-b_{1}c_{2}-b_{2}c_{1}-d_{1}d_{2}$

where $Z_{1}=a_{1}+b_{1}i+c_{1}\varepsilon+d_{1}h$ and
$Z_{2}=a_{2}+b_{2}i+c_{2}\varepsilon+d_{2}h$. On the other hand, the vector
product of two hybrid numbers $Z_{1}$ and $Z_{2}$ defined as

$\displaystyle x:K\times K\longrightarrow K$ $\displaystyle Z_{1}\times
Z_{2}=\frac{Z_{1}\overline{Z_{2}}-Z_{2}\overline{Z_{1}}}{2}.$

##  3\. Hybrid Spinors

In this section, we will introduce a new relationship between hybrid numbers
and spinors. Let the set of Hybrid numbers be $\mathbb{K}$. Let us define the
transformation that gives the relation between spinors and hybrid numbers as
follows

$\chi:\mathbb{K}\to\mathbb{HS}$
$\chi\left({a+bi+c\varepsilon+dh}\right)=\left[{\begin{array}[]{*{20}{c}}{a+hc}\\\
{\left({c-b}\right)+hd}\end{array}}\right].$

If we take that conjugate of the hybrid number $z$ is
$z^{*}=a-bi-c\varepsilon-dh$, the hybrid spinor corresponding to conjugate
hybrid number can be written as

$\chi\left({a-bi-c\varepsilon-
dh}\right)=\left[{\begin{array}[]{*{20}{c}}{a-hc}\\\
{\left({b-c}\right)-hd}\end{array}}\right]\equiv\overline{SH}.$

We associated to the product of two hybrid numbers $p\times q$, which is equal
to the hybrid number -matrix product $L(p)q$, with a spinor matrix product as
follows

$p\times q\rightarrow L(p)q\rightarrow-h\hat{Q}H$

where

$\hat{Q}=\left[\begin{array}[]{cc}a+hc&(b-c)+hd\\\
(c-b)+hd&a-hc\end{array}\right],$

and

$H=\left[\begin{array}[]{cc}1&0\\\ 0&-1\end{array}\right].$

##  4\. Hybrid Fibonacci and Lucas Spinors

In this section, we will present the hybrid Fibonacci and Lucas spinors using
a similar methodology. Additionally, we will investigate the characteristics
of hybrid Fibonacci and Lucas spinors, deriving theorems and formulas that
define these spinors.

The Fibonacci sequence [4] is defined by the recurrence relation

$F_{n+1}=F_{n}+F_{n-1}$

with initial conditions $F_{0}=0,F_{1}=1$.

The Lucas sequence [4] is defined by the recurrence relation

$L_{n+1}=L_{n}+L_{n-1}$

with initial conditions $L_{0}=2,L_{1}=1$.

$z=F_{n}+F_{n+1}i+F_{n+2}\varepsilon+F_{n+3}h$ be a hybrid Fibonacci number
Let us define the transformation that gives the relation between hybrid
Fibonacci numbers and hybrid spinous as follows

$\chi:\mathbb{F}\longrightarrow\mathbb{HS}$
$\displaystyle\chi\left({{F_{n}}+{F_{n+1}}i+{F_{n+2}}\varepsilon+{F_{n+3}}h}\right)=\left[{\begin{array}[]{*{20}{c}}{{F_{n}}+h{F_{n+2}}}\\\
{\left({{F_{n+2}}-{F_{n+1}}}\right)+h{F_{n+3}}}\end{array}}\right]\equiv\overline{FSH_{n}}.$

We say that a new sequence is hybrid Fibonacci spinor sequence. Note that for
$n\geq 0$,

$FSH_{n+2}=FSH_{n+1}+FSH_{n}$

can be written.

######  Definition 4.1.

Let the conjugate of the hybrid Fibonacci number $HF_{n}$ be
$\overline{H{F_{n}}}={F_{n}}-i{F_{n+1}}-\varepsilon{F_{n+2}}-h{F_{n+3}}$.
Furthermore from the correspondence, the hybrid Fibonacci spinor
$\overline{FSH_{n}}$ corresponding to the conjugate of the hybrid Fibonacci
number is written by

$\chi\left({\overline{H{F_{n}}}}\right)=\left[{\begin{array}[]{*{20}{c}}{{F_{n}}-h{F_{n+2}}}\\\
{\left({{F_{n+1}}-{F_{n+2}}}\right)-h{F_{n+3}}}\end{array}}\right]=\overline{FS{H_{n}}}.$

Additionally, utilizing the conjugate definitions provided in the second
section, we can provide the following conjugate definitions. The hyperbolic
conjugate of hybrid Fibonacci spinor $FS{H_{n}}$ is

$FSH_{n}^{*}=\left[{\begin{array}[]{*{20}{c}}{{F_{n}}-h{F_{n+2}}}\\\
{\left({{F_{n+2}}-{F_{n+1}}}\right)-h{F_{n+3}}}\end{array}}\right].$

Hybrid Fibonacci spinor conjugate $F\tilde{S}{H_{n}}=hH\overline{FS{H_{n}}}$
of hybrid Fibonacci spinor $FS{H_{n}}$ is

$F\tilde{S}{H_{n}}=\left[{\begin{array}[]{*{20}{c}}{-{F_{n+2}}+h{F_{n}}}\\\
{{F_{n+3}}+h\left({{F_{n+1}}-{F_{n+2}}}\right)}\end{array}}\right].$

The mate of hybrid Fibonacci spinor
$F\mathop{S}\limits^{\vee}{H_{n}}=-H\overline{FS{H_{n}}}$ is

$F\mathop{S}\limits^{\vee}{H_{n}}=\left[{\begin{array}[]{*{20}{c}}{-{F_{n}}+h{F_{n+2}}}\\\
{\left({{F_{n+2}}-{F_{n+1}}}\right)-h{F_{n+3}}}\end{array}}\right]$

where $H=\left[\begin{array}[]{cc}1&0\\\ 0&-1\end{array}\right]$.

######  Corollary 4.2.

For the hybrid Fibonacci spinor $FSH_{n}$ and its conjugates, following
formulas are valid

  * •

$FS{H_{n}}+\overline{FS{H_{n}}}=2\left[{\begin{array}[]{*{20}{c}}{{F_{n}}}\\\
0\end{array}}\right]$,

  * •

$FS{H_{n}}+FS{H_{n}}^{*}=2\left[{\begin{array}[]{*{20}{c}}{{F_{n}}}\\\
{{F_{n}}}\end{array}}\right]=2{F_{n}}\left[{\begin{array}[]{*{20}{c}}1\\\
1\end{array}}\right]$,

  * •

$FS{H_{n}}+F\mathop{S}\limits^{\vee}{H_{n}}=2\left[{\begin{array}[]{*{20}{c}}{h{F_{n+2}}}\\\
{{F_{n}}}\end{array}}\right]$,

  * •

$hF\widetilde{S}{H_{n}}=-F\mathop{S}\limits^{\vee}{H_{n}}$.

######  Theorem 4.3.

The Binet formula for hybrid Fibonacci spinor sequence is as follows:

$FSH_{n}=\left[\begin{array}[]{l}\frac{1}{\sqrt{5}}+h\left(\frac{3+\sqrt{5}}{2\sqrt{5}}\right)\\\
\frac{1}{\sqrt{5}}+h\left(\frac{2+\sqrt{5}}{\sqrt{5}}\right)\end{array}\right]\alpha^{n}+\left[\begin{array}[]{l}-\frac{1}{\sqrt{5}}-h\left(\frac{3-\sqrt{5}}{2\sqrt{5}}\right)\\\
-\frac{1}{\sqrt{5}}-h\left(\frac{2-\sqrt{5}}{\sqrt{5}}\right)\end{array}\right]\beta^{n}$

where $\alpha=\frac{{1+\sqrt{5}}}{2}$ and $\beta=\frac{{1-\sqrt{5}}}{2}$.

###### Proof.

The characteristic equation of the recurrence relation of hybrid Fibonacci
spinor sequence is $x^{2}-x-1=0$. The roots of are this equation are
$\alpha=\frac{1+\sqrt{5}}{2},\beta=\frac{1-\sqrt{5}}{2}$. The Binet’s formula
for hybrid Fibonacci spinor is as follows

$FSH_{n}=SH_{A}\alpha^{n}+SH_{B}\beta^{n}$

where $SH_{A}=\left[\begin{array}[]{l}a_{1}\\\
a_{2}\end{array}\right],\mathrm{SH}_{B}=\left[\begin{array}[]{l}b_{1}\\\
b_{2}\end{array}\right]\quad 2\times 1$ matrices. If we write this equation
for $n=0$ and $n=1$, we obtain the Binet formula as

$FSH_{n}=\frac{1}{2\sqrt{5}}\left(\left[\begin{array}[]{l}2+(3\sqrt{5})h\\\
2+(4+2\sqrt{5})h\end{array}\right]\alpha^{n}-\left[\begin{array}[]{c}2+(3-\sqrt{5})h\\\
2+(4-2\sqrt{5})h\end{array}\right]\beta^{n}\right)\text{. }$

∎

######  Theorem 4.4.

The generating function for hybrid Fibonacci spinor $FSH_{n}$ is

${G_{FS{H_{n}}}}\left(x\right)=\frac{1}{{1-x-{x^{2}}}}\left[{\begin{array}[]{*{20}{c}}{1+h\left({3-x}\right)}\\\
{1+h\left({5-2x}\right)}\end{array}}\right].$

###### Proof.

The generating function $h(x)$ for hybrid Fibonacci spinor can be writer as
follows:

$h(x)=\sum_{n=0}^{\infty}FSH_{n}x^{n}$

If the recurrence relation of hybrid Fibonacci spinor sequence is considered,
we have

$\sum_{n=0}^{\infty}FSH_{n+2}x^{n}=\sum_{n=0}^{\infty}FSH_{n+1}x^{n}+\sum_{n=0}^{\infty}FSH_{n}x^{n}.$

Then, we can write

$\sum_{n=2}^{\infty}FSH_{n}x^{n-2}=\sum_{n=1}^{\infty}FSH_{n}x^{n-1}+\sum_{n=0}^{\infty}FSH_{n}x^{n}$
$\frac{1}{x^{2}}\left(-FSH_{0}-FSH_{1}+h(x)\right)=\frac{1}{x}\left(-FSH_{0}+h(x)\right)+h(x).$

Since the first two terms of hybrid Fibonacci spinor sequence are

$\mathrm{FSH}_{0}=\left[\begin{array}[]{c}h\\\
2h\end{array}\right],\mathrm{FSH}_{1}=\left[\begin{array}[]{l}1+2h\\\
1+3h\end{array}\right]$

we get,

$h(x)=\frac{1}{1-x-x^{2}}\left[\begin{array}[]{l}1+h(3-x)\\\
1+h(5-2x)\end{array}\right].$

∎

The hybrid Fibonacci spinor matrix is defined as follows

$Q_{h}=\left[\begin{array}[]{lr}F_{n}+hF_{n+2}&\left(F_{n+1}-F_{n+2}\right)+hF_{n+3}\\\
\left(F_{n+2}-F_{n+1}\right)+hF_{n+3}&F_{n}-hF_{n+2}\end{array}\right].$

######  Theorem 4.5.

For $n\geq 1$, we have Cassini formula for hybrid Fibonacci spinous

$\operatorname{det}\left(Q_{n}\right)=-F_{2n+5}+2F_{n}^{2}.$

Now, we express hybrid Lucas spinous. Let
$z_{n}^{\prime}=L_{n}+L_{n+1}i+L_{n+2}\varepsilon+L_{n+3}h$ be the $nth$ Lucas
hybrid number where $L_{n}$ nth Lucas number.

Hybrid Lucas spinor$LSH_{n}$ corresponding to $nth$ hybrid Lucas number
$z_{n}^{\prime}$ is

$\displaystyle z_{n}^{\prime}\rightarrow
f\left(L_{n}+L_{n+1}i+L_{n+2}\varepsilon+L_{n+3}h\right)$
$\displaystyle=\left[\begin{array}[]{l}L_{n}+hL_{n+2}\\\
L_{n}+hL_{n+3}\end{array}\right]$ $\displaystyle\equiv LSH_{n}.$

######  Theorem 4.6.

For $n\geq 0$, the Binet formula for $n$th hybrid Lucas spinor $LSH_{n}$ is

$LSH_{n}=A\alpha^{n}+B\beta^{n},$

where

$A=\left[\begin{array}[]{c}\frac{2+h(3\sqrt{5})}{2}\\\
1+(2+\sqrt{5})h\end{array}\right],\quad
B=\left[\begin{array}[]{l}\frac{3-\sqrt{5}h}{2}\\\
1+(2-\sqrt{5})h\end{array}\right].$

######  Theorem 4.7.

The generating function for hybrid Lucas spinor $LSH_{n}$ is

$g^{\prime}(x)=\frac{1}{1-x-x^{2}}\left(\left[\begin{array}[]{l}3+7h\\\
3+11h\end{array}\right]-x\left[\begin{array}[]{l}2+3h\\\
2+4h\end{array}\right]\right)$

.

######  Theorem 4.8.

For $n\geq 2$, we have

i:

$FSH_{n+2}-FSH_{n-2}=LSH_{n}$,

ii:

$5FSH_{n}+LSH_{n}=2LSH_{n+1}$.

###### Proof.

$\displaystyle(i)\operatorname{FSH}$
$\displaystyle=\frac{1}{\sqrt{5}}\left(A\alpha^{n}-B\beta^{n}\right)$
$\displaystyle FSH_{n+2}-FSH_{n-2}$
$\displaystyle=\frac{1}{\sqrt{5}}\left(A\alpha^{n}\left(\alpha^{2}+\alpha^{-2}\right)-B\beta^{n}\left(\beta^{2}-\beta^{-2}\right)\right)$
$\displaystyle=\frac{1}{\sqrt{5}}\left(A\alpha^{n}\left(\frac{3+\sqrt{5}}{2}-\frac{3-\sqrt{5}}{2}\right)-B\beta^{n}\left(\frac{3-\sqrt{5}}{2}-\frac{3+\sqrt{5}}{2}\right)\right)$
$\displaystyle=\frac{1}{\sqrt{5}}\left(A\alpha^{n}-\sqrt{5}+B\beta^{n}\sqrt{5}\right)=A\alpha^{n}+B\beta^{n}=LSH_{n}.$

The second identity is proved in a similar way as the frst. ∎

######  Theorem 4.9.

For $n\geq 1$, we have

i:

$L_{n+1}FSH_{n}+L_{n}FSH_{n-1}=LSH_{2n}$,

ii:

$F_{n+1}FSH_{n}+F_{n}FSH_{n-1}=FSH_{2n}$.

###### Proof.

(i) The Binet formula for Lucas sequence is $L_{n}=\alpha^{n}+\beta^{n}$. We
can write

$\displaystyle LSH_{2n}$ $\displaystyle=$
$\displaystyle\frac{A\left(\alpha^{2n+1}-\beta\alpha^{2n}\right)+B(\alpha\beta^{2n}-\beta^{2n+1})}{\alpha-\beta}$
$\displaystyle=$
$\displaystyle\frac{\left(A\alpha^{n}-B\beta^{n}\right)(\alpha^{n}\alpha+\beta^{n}\beta)}{2\left(\alpha-\beta\right)}+\frac{\left(A\alpha^{n-1}-B\beta^{n-1}\right)(\alpha^{n}+\beta^{n})}{2\left(\alpha-\beta\right)}$
$\displaystyle=$
$\displaystyle(\alpha^{n+1}+\beta^{n+1})\left(\frac{1}{2(\alpha-\beta)}\left(A\alpha^{n}-B\beta^{n}\right)\right)$
$\displaystyle+\left(\alpha^{n}+\beta^{n}\right)\left(\frac{1}{2(\alpha-\beta)}\left(A\alpha^{n-1}-B\beta^{n-1}\right)\right)$
$\displaystyle=$ $\displaystyle L_{n+1}FSH_{n}+L_{n}FSH_{n-1}.$

(ii) The Binet formula for Fibonacci sequence is

$F_{n}=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta},$

where $\alpha=\frac{1+\sqrt{5}}{2},\beta=\frac{1-\sqrt{5}}{2}$. Then, $we$ can
write

$\displaystyle F_{n+1}FSH_{n}+F_{n}FSH_{n-1}=$
$\displaystyle\frac{\alpha^{n+1}-\beta^{n+1}}{\alpha-\beta}\cdot\frac{1}{\sqrt{5}}\left(A\alpha^{n}-B\beta^{n}\right)+\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta}\cdot\frac{1}{\sqrt{5}}\cdot\left(A\alpha^{n-1}-B\beta^{n-1}\right)\cdot$
$\displaystyle=\frac{\left(\alpha^{n+1}-\beta^{n+1}\right)\left(A\alpha^{n}-B\beta^{n}\right)}{(\alpha-\beta)^{2}}+\frac{\left(\alpha^{n}-\beta^{n}\right)\left(A\alpha^{n-1}-B\beta^{n-1}\right)}{(\alpha-\beta)^{2}}$
$\displaystyle=\frac{(\alpha-\beta)\left(A\alpha^{2n}-B\beta^{2n}\right)}{(\alpha-\beta)^{2}}$
$\displaystyle=FSH_{2n}.$

∎

##  5\. The hybrid Fibonacci polynomial spinor

Hoggatt, Philips and Leonard defined the Fibonacci and Lucas Polynomials and
they have obtained some more identities involving these polynomials, [3].

Fibonacci polynomial sequence is defined by the recurrence relation

$F_{n+1}(x)=xF_{n}(x)+F_{n-1}(x)$

with initial conditions $F_{0}(x)=0,F_{1}(x)=1$. The first few terms of
Fibonacci polynomial sequence are as follows

$0,1,x,x^{2}+1,x^{3}+2x,x^{4}+3x^{2}+1,\ldots.$

The characteristic equation of this sequence

$F_{n}(t)=t^{2}-xt-1$

Lucas polynomial sequence is defined by the recurrence relation

$L_{n+1}(x)=xL_{n}(x)+L_{n-1}(x)$

with initial conditions $L_{0}(x)=2,L_{1}(x)=1$. The first few terms of Lucas
polynomial sequence are as follows.

$2,x,x^{2}+2,x^{3}+3x,x^{4}+4x^{2}+2,\ldots.$

We define hybrid Fibonacci polynomial and transformation of hybrid Fibonacci
polynomial spinor.

$Z(x)=F_{n}(x)+F_{n+1}(x)i+F_{n+2}(x)\varepsilon+F_{n+3}(x)h,$

$\begin{array}[]{r}FSH_{n}(x)=\left[\begin{array}[]{l}F_{n}(x)+hF_{n+2}(x)\\\
\left(F_{n+2}(x)-F_{n+1}(x)\right)+hF_{n+3}(x)\end{array}\right].\end{array}$

The Fibonacci hybrid polynomial spinor sequence is defined by the recurrence
relation

${FSH}_{n+2}(x)={FSH}_{n+1}(x)+{FSH}_{n}(x).$

The following theorems can be proved in a similar way as presented in Section
4.

######  Theorem 5.1.

The Binet formula for hybrid Fibonacci polynomial sequence

$\quad\text{ FSH n
}(x)=\frac{1}{2}\left(A(x)\alpha(x)^{n}-B(x)\beta(x)^{n}\right),\\\ $

where

$A(x)=\left[\begin{array}[]{l}\frac{2+2h+hx^{2}}{\sqrt{x^{2}+4}}+hx\\\
\frac{1+xh}{\sqrt{x^{2}+4}}+hx^{2}+h\end{array}\right],B(x)=\left[\begin{array}[]{l}\frac{2+2h+2hx^{2}}{\sqrt{x^{2}+4}}-hx\\\
\frac{1+xh}{\sqrt{x^{2}+4}}-hx^{2}-h\end{array}\right].$

######  Theorem 5.2.

The generating function for hybrid Fibonacci polynomial spinor

$g(t)=\frac{1}{1-xt-t^{2}}\left[\begin{array}[]{l}1+h\left(x^{2}+x^{2}t+x+1\right)\\\
1+h\left(x^{3}+x^{3}t+x^{2}+2x+xt+1\right)\end{array}\right]$

Now, we define hybrid Lucas polynomial and transformation of hybrid Lucas
polynomial spinor.

$\begin{array}[]{r}z^{\prime}(x)=L_{n}(x)+L_{n+1}(x)i+L_{n+2}(x)\varepsilon+L_{n+3}(x)h,\\\
LSH_{n}(x)=\left[\begin{array}[]{l}LSH_{n}(x)+hLSH_{n+2}(x)\\\
LSH_{n}(x)+hLSH_{n+3}(x)\end{array}\right].\\\ \end{array}$

The hybrid Lucas polynomial spinor sequence is defined by the recurrence
relation

${LSH}_{n+2}(x)={LSH}_{n+1}(x)+LSH_{n}(x).$

######  Theorem 5.3.

The Binet formula for hybrid Lucas polynomial spinor

$\displaystyle
LSH_{n}(x)=\frac{1}{2c}\left(\left[\begin{array}[]{l}p(x)+2c+h\left(cx^{2}+2c\right)\\\
q(x)+2c+h\left(cx^{3}+3xc\right)\end{array}\right]\alpha^{n}+\right.$
$\displaystyle{\left[\begin{array}[]{l}-p(x)+2c+h\left(cx^{2}+2c\right)\\\
-q(x)+2c+h\left(cx^{3}+3xc\right)\end{array}\right]\beta^{n},}$

where $c=\sqrt{x^{2}+4},p(x)=hx^{3}-2hx+bx$, $q(x)=hx^{4}+5x^{2}h+4h$.

######  Theorem 5.4.

The generating function for hybrid Lucas polynomial spinor as follows:

$g^{\prime}(t)=\frac{1}{1-xt-t^{2}}\left(\left[\begin{array}[]{l}2+x+h\left(x^{3}+x^{2}+3x+2\right.\\\
2+x+h\left(x^{4}+x^{3}+4x^{2}+3x+2\right.\end{array}\right]-xt\left[\begin{array}[]{l}2+h\left(x^{2}+2\right)\\\
2+h\left(x^{3}+3x\right)\end{array}\right].\right.$

######  Theorem 5.5.

For $n\geq 1$, we have

  * •

$LSH_{n}(x)=FSH_{n+1}(x)+FSH_{n-1}(x)$,

  * •

$LSH_{n}(x)=2FSH_{n+1}(x)-x\cdot FSH_{n}(x)$,

  * •

$(a-b)^{2}FSH_{n}(x)=LSH_{n+1}(x)+(-1)^{n+1}LSH_{n-1}(x)$.

##  6\. Conclusion

In this study, hybrid spinors were defined using the concept of hybrid
numbers. Subsequently, hybrid Fibonacci and hybrid Lucas spinor sequences were
defined by employing terms and polynomials of Fibonacci and Lucas number
sequences. Fundamental properties such as generator functions, Binet formula,
and others were derived for these hybrid sequences. Finally, utilizing the
polynomials associated with these sequences, hybrid Fibonacci and hybrid Lucas
polynomial spinors were introduced, and similar equations were provided. As a
result, this study presents a new perspective for future research by
amalgamating concepts crucial in algebra, number theory, and related fields,
along with mathematical entities like hybrid numbers and spinors, commonly
utilized in areas such as geometry and mathematical physics.

## Declaration of competing interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## References

  * [1] Borota, N. A., Flores, E., Osler, T. J. (2000). Spacetime numbers the easy way. Mathematics and Computer Education, 34(2).
  * [2] Fjelstad, P. (1986). Extending special relativity via the perplex numbers. American Journal of Physics, 54(5), 416-422.
  * [3] Hoggatt Jr, V. E., Phillips, J. W., Leonard Jr, H. T. (1971). Twenty-four master identities. The Fibonacci Quarterly, 9(1), 1-17.
  * [4] Koshy, T. (2019). Fibonacci and Lucas Numbers with Applications, Volume 2. John Wiley and Sons.
  * [5] Özdemir, M. (2018). Introduction to hybrid numbers. Advances in applied Clifford algebras, 28, 1-32.
  * [6] Poodiack, R. D., LeClair, K. J. (2009). Fundamental theorems of algebra for the perplexes. The College Mathematics Journal, 40(5), 322-336.
  * [7] Rochon, D., Shapiro, M. (2004). On algebraic properties of bicomplex and hyperbolic numbers. Anal. Univ. Oradea, fasc. math, 11(71), 110.
  * [8] Yaglom, I. M. (2012). A simple non-Euclidean geometry and its physical basis: An elementary account of Galilean geometry and the Galilean principle of relativity. Springer Science and Business Media.