# AMCO: Adaptive Multimodal Coupling of Vision and Proprioception for
Quadruped Robot Navigation in Outdoor Environments

Mohamed Elnoor, Kasun Weerakoon, Adarsh Jagan Sathyamoorthy, Tianrui Guan,
Vignesh Rajagopal,
and Dinesh Manocha
Technical report and video can be found at http://gamma.umd.edu/amco/

###### Abstract

We present AMCO, a novel navigation method for quadruped robots that
adaptively combines vision-based and proprioception-based perception
capabilities. Our approach uses three cost maps: general knowledge map;
traversability history map; and current proprioception map; which are derived
from a robot’s vision and proprioception data, and couples them to obtain a
coupled traversability cost map for navigation. The general knowledge map
encodes terrains semantically segmented from visual sensing, and represents a
terrain’s typically expected traversability. The traversability history map
encodes the robot’s recent proprioceptive measurements on a terrain and its
semantic segmentation as a cost map. Further, the robot’s present
proprioceptive measurement is encoded as a cost map in the current
proprioception map. As the general knowledge map and traversability history
map rely on semantic segmentation, we evaluate the reliability of the visual
sensory data by estimating the brightness and motion blur of input RGB images
and accordingly combine the three cost maps to obtain the coupled
traversability cost map used for navigation. Leveraging this adaptive
coupling, the robot can depend on the most reliable input modality available.
Finally, we present a novel planner that selects appropriate gaits and
velocities for traversing challenging outdoor environments using the coupled
traversability cost map. We demonstrate AMCO’s navigation performance in
different real-world outdoor environments and observe 10.8%-34.9% reduction
w.r.t. two stability metrics, and up to 50% improvement in terms of success
rate compared to current navigation methods.

##  I Introduction

Quadruped robots have been used for autonomous navigation due to their
superior dynamics, which enables them to traverse diverse and challenging
terrains in outdoor settings [1, 2]. They can be used in applications
including agriculture [3], planetary exploration [4], surveillance [5], and
disaster response missions [6]. However, guiding these robots across such
complex environments requires a comprehensive understanding of the scene,
which encompasses how the terrain visually appears using vision-based sensors
and how it physically feels under the robot’s feet using proprioception.

Traditionally, terrain traversability has been assessed using
exteroceptive/visual sensors such as cameras [7, 8] and LiDARs [9, 10], which
provide valuable information about the environment. Yet, these approaches
often fall short in complex terrains where visual features do not provide
sufficient information about the terrain, or when the visual characterization
is incorrect. For instance, a terrain that appears to be solid and stable
(like soil) but deforms (is actually mud) under the robot’s weight. This
leaves the robot vulnerable to sinkages, slips, and entrapments [4, 11, 12].

On the other hand, proprioception, which can be captured from a legged robot’s
internal joint encoders [13, 14], odometry errors [1], robot states [15],and
contact vibrations [16], effectively measures the terrain traversability
characteristics (softness, bumpiness, etc) at the robot’s present location
[17]. Proprioception has previously been used to learn traversability costs
for visual navigation [1, 15]. However, it can not be used to predict the
terrain traversability ahead of the robot [14] without exteroceptive sensing.

Figure 1: The navigation trajectories generated by our method, AMCO (trot:
brown, crawl: red, amble: pink), ProNav [14] (trot: blue, crawl: purple,
amble: light blue), GaNav [8] (orange), Spot’s Inbuilt (yellow), and RFC [18]
(trot: green, crawl: light green, amble: light beige) in scenario 4, which
contains different types of deformable terrains: (A) water puddle, (B) mud,
(C) granular. AMCO, ProNav, and RFC can switch between three gaits (trot,
crawl, and amble) during navigation as presented in three different colors.
Our method AMCO updates its trajectory as traversing the terrain and uses the
coupled vision and proprioception to avoid extremely deformable regions such
as A and B. It balances between the trajectory length and maintaining
stability to reduce potential robot failures on terrains with varying
deformability. Conversely, GaNav [8] takes a longer path by avoiding mud and
grass altogether. The other methods takes a straight path towards the goal
which leads to sinkage and failures.

To this end, many approaches have combined proprioceptive and visual inputs
using self-supervised learning [1, 13, 15, 19, 20]. Those methods estimate
traversability cost maps which only represent terrains’ typical
traversability. However, they do not account for the potential changes in
terrains’ physical properties, such as deformability [21] and trafficability
[22], due to weather or other factors. This limitation restricts previous
methods from adapting to traversability changes, potentially leading to
failures. To create a generalizable traversability estimation approach for
stable navigation, the robot must also consider both the recent proprioceptive
history, and the current instant’s proprioceptive feedback from the terrain
along with its typical traversability obtained from visual inputs.

Main Contributions: To this end, we present AMCO (Adaptive Multimodal COupling
of vision and proprioception for stable robot navigation), a novel approach
that adaptively integrates semantic segmentation and proprioceptive feedback
of terrain into a traversability cost map. This multi-modal perception
representation is integrated with a local planner to select a stable gait and
velocity combination for robot navigation. Our approach is inspired by how
humans navigate through deformable, and occluded terrains like sand, muddy
grass, and bushes, using: 1. our general knowledge of the terrain (e.g. soil
is usually stable to walk on), 2. recent traversability history (e.g. soil was
wet and felt deformable a few time steps ago in a nearby location), 3. current
experience (e.g. soil feels more deformable and non-traversable). Here, both
visual features and proprioception information inform our understanding of the
terrain and guide our movement. The novel components of our work are:

  * •

We introduce novel formulations of three traversability cost maps using vision
and proprioception perception capabilities. A general knowledge map that uses
semantic segmentation from an RGB camera to represent the terrain’s
traversability ahead of the robot. Next, we use the recent history of
proprioception signals, which are measured from the robot’s joint positions,
forces, and current consumption from the battery. We captured the recent
duration of this prospective-informed traversability and its consistency with
its semantic traversability class toto build a history map. Also, we present a
proprioceptive-based traversability cost map, which extrapolates the current
robot proprioception to future time steps to robustly predict the
traversability along the robot’s trajectory.

  * •

An adaptive multi-modal coupling of the three cost maps according to the
vision-based sensor reliability. To do that, we incorporate a reliability
estimation method that assesses the quality of RGB images and weighs the
vision-based representations on the coupled maptraversability cost map. This
ensures that the navigation decisions are based on the most reliable input
modality available. We demonstrate that our adaptive coupling leads to
improvements in navigating different types of deformable terrains.

  * •

A navigation algorithm that adapts gait selection and dynamically calculates
feasible velocities in real-time based on multi-modal sensory input (coupled
map) to ensure stable navigation. We demonstrate our method on Boston dynamic
spot and evaluate its performance in four unstructured outdoor environments.
We observe 10.8%-34.9% reduction in IMU Energy density [23] and up to 50%
improvement in navigation success rate.

##  II Related Works

In this section, we discuss the traversability estimation methods for both
exteroception and proprioception sensors. After that, we briefly discuss the
existing methods for outdoor navigation.

###  II-A Traversability Estimation

Traversability estimation tends to incorporate vision-based approaches that
use external sensors and proprioception-based approaches. We review both
perception methods in the following sections.

####  II-A1 Exteropercption-based perception

Exteroception has been widely used to estimate traversability in outdoor
settings [10, 24, 25]. Many methods leverage semantic segmentation to classify
different types of terrains in outdoor settings [8, 26, 27]. For instance,
ViTAL [28] leverages vision-based techniques for terrain-aware locomotion,
which optimizes path planning across varied terrains with a focus on quadured
robots. Another noteworthy approach by Agarwal et al.[29], utilizes an
egocentric camera to facilitate legged locomotion on rugged terrains through
an end-to-end locomotion system. These methodologies predominantly utilize
vision-based sensors, whose performance can degrade under various conditions
such as light changes, motion blur, and occlusions [30].

####  II-A2 Proprioception-based Perception

Proprioception, the internal sense of movement and position, plays a crucial
role in quadruped robot navigation, as described in [1, 13, 31]. It is defined
as the robot’s internal sense of movement and position [17]. While effective
in terrain interaction, its limitations in predicting unencountered terrain
necessitate external sensor integration for improved navigation. Wisth et
al.’s development of a method combining proprioceptive feedback with visual,
inertial, lidar, and odometry data exemplifies advancements in multi-modal
sensor fusion [19]. This approach, further refined by cross-modal learning
techniques by Loquercio et al. [32], enhances environmental understanding and
adaptability. Moreover, studies by García et al. [33] and Karnan et al. [31,
34] illustrate the benefits of using proprioceptive data for gait adjustments
and incorporating human preferences into navigation systems, showcasing the
potential of learning-based methods for better terrain adaptation. This
collective research shows the significance of integrating proprioceptive
feedback with external sensors for advanced robotic navigation and terrain
adaptability.

Other works include fused proprioception with visual data in particular to
improve navigation. As highlighted by Fu et al. [13], integrating these
sensory inputs improves spatial awareness and movement strategies. This
approach is crucial for navigating adverse conditions, with Teng et al. [35]
and Jin et al. [36] showcasing the importance of proprioception in maintaining
balance and enhancing resilience. Assessing terrain supportiveness through
proprioceptive data is essential for safe and effective navigation. Homberger
et al. [37] discuss the role of proprioception in evaluating surface
stability. Recently, Dey et al. [11] introduced a predictive method that
utilizes proprioceptive signals to foresee and counteract potential navigation
failures, emphasizing the need for anticipation in challenging terrains. While
these methods integrate proprioception with exteroception, many of them assume
the consistency between the two sensory modalities which is reasonable for
some terrains. In our case, we consider terrains that could have different
traversability under different weather conditions such as sand, mud, grass,
and covered grounds.

###  II-B Outdoor Navigation

Recent advancements in outdoor navigation for autonomous systems have
showcased the integration of several methods and hardware designs [4, 28, 38,
39]. For instance, [40] works on path optimization for ground vehicles in off-
road terrains uses vehicle kinematic constraints and advanced algorithms for
improved efficiency. On the other hand, [41] developed robust navigation
systems for legged robots, employing reachability-based methods and neural
network-based learned motion costs to navigate unpredictable terrains in term
of traversability. Miki et al. [42] advanced sensory integration techniques,
employing attention-based recurrent encoders and lidar intensity maps for
enhanced environmental interaction. Additionally, [4] investigated the
potential of quadruped robots for haptic inspection of planetary soils. Also,
Kolvenbach et al. in [43] have developed a terrain-aware locomotion
controller. This controller combines proprioceptive and exteroceptive inputs
using a recurrent encoder, which enables the legged robots to navigate
challenging terrains. Our navigation approach is different from these methods.
We compute the best gait and velocity pairs based on the semantic
traversability class and proprioception. This helps the robot to maintain
stability as well as heading toward the goal.

##  III Background

In this section, we explain symbols, notations, and the preliminary concepts
used in our work.

###  III-A Symbols and Notations

We highlight the symbols of images and cost maps we use in Table (I).

Symbols | Definitions
---|---
$I_{RGB}^{t}$ | Input RGB image.
$I_{SD}^{t}$ | Image after applying semantic segmentation.
$\mathcal{C}_{g}^{t}$ | A general knowledge map based on vision . IV-A
$\mathcal{C}_{h}^{t}$ | A history map that’s based on vision and proprioception. IV-B
$\mathcal{C}_{p}^{t}$ | A proprioception map that’s based on proprioception. IV-D
$\mathcal{C}_{coupled}^{t}$ | A coupled map that’s computed after the adaptive coupling. IV-E
Table I:  List of symbols used in our approach. $I_{RGB}^{t}$ and $I_{S}^{t}$
are three-channel images of size $H\times W$. All the cost maps are grayscale
of size $H\times W$ where $H,W$ are the height and width of the images and the
cost maps.

###  III-B Setup and Conventions

The quadruped robot in our formulation has a coordinate frame attached to its
center of mass with X, Y, and Z directions facing forward, leftward, and
upward, respectively. The robot is equipped with sensors to measure the
positions, velocities and forces exerted at each joint in the $i^{th}$ leg
along each axis. Additionally, the robot measures the current
$\mathcal{I}^{t}$ consumed from the battery. At every time instant $t$, these
quantities are used as raw proprioceptive signals to feel the terrain and
estimate its traversability (section III-C). The robot is also equipped with
an RGB camera that provides an image $I_{RGB}^{t}$ to view the terrains ahead,
and a 3D lidar to detect obstacles. The robot can execute three kinds of
gaits: 1\. trot, where two of the robot’s feet make contact with the ground
while walking, 2\. crawl, where three feet touch the ground for enhanced
stability but with a restricted maximum velocity, and 3\. amble: a gait
similar to crawl but with unrestricted maximum speed.

We categorize the various terrains that the robot navigates into the following
types: 1. stable, 2. granular (e.g. sand, snow), 3. poor foothold (e.g.
rocks), 4. high resistance (e.g. dense vegetation). We use $i,j$ to indicate
grid locations in costmaps.

###  III-C Proprioception-based Terrain Analysis

We utilize the approach proposed in [14] to estimate a terrain $\tau$’s
traversability by processing the raw proprioceptive signals (defined in
Section III-B) from a legged robot and transforming them into two dimensional
point $\mathbf{p}^{t}_{\tau}$ using Principal Component Analysis [44]. [14]
shows that the L-2 norm ($|\mathbf{p}^{t}_{\tau}|_{2}$) indicates a terrain’s
traversability. After estimating a terrain’s traversability, [14] empirically
demonstrates that using a certain gait $g$ to traverse a terrain type $\tau$
(III-B) results in a bounded distribution of points in the PCA space, that can
be modeled as a 2D Gaussian ellipse $\mathcal{E}(\tau,g)$. [14] also shows
that the area of a gait-terrain ellipse is directly proportional to the level
of stability the robot experiences while traversing the terrain using the gait
(see Fig. 2).

Figure 2:  The gaussian ellipses for the PCA components of four different
terrains [14]. For each terrain, three types of gait data are shown using
different ellipse boundaries. The solid line denotes trot, the dashed line
denotes amble, and the dash-dot line is for crawl.

###  III-D Vision-based Traversability Types

As a preliminary for our vision module, we use a terrain semantic segmentation
method to classify the terrain type. Particularly, we incorporate [8], a
semantic segmentation method that uses group-wise attention to differentiate
the traversability of the terrains and provides a segmentation image. We train
this segmentation method using RUGD dataset [45] using 4 terrain groups as
presented in Table II.

Semantic Categories | Terrain Type
---|---
Concrete, Asphalt | Stable
Sand, Dirt, Gravel, Mulch | Granular
Rocks, Rockbed | Poor Foothold/Rocky
Grass, Bush | High Resistance/Vegetation
Table II: Semantic categories and their corresponding terrain type $\tau$.

##  IV Our Approach

In this section, we discuss how we construct our adaptive multimodal cost map
using semantic segmentation and proprioception. We highlight the symbols and
notation of our approach in table I.

###  IV-A General Knowledge Map

Given an RGB image $I_{RGB}^{t}$, we process it through a semantic
segmentation model (III-D) to output a segmented image $I_{S}^{t}$. Each pixel
in $I_{S}^{t}$ categorizes the terrain $\tau$ into the four terrain classes
defined in Section III-B. Next, we create a general knowledge map that
represents the typical traversability of the terrains ahead of the robot as a
costmap. It is constructed by assigning a traversability cost to each
segmented terrain class $\tau$ based on the smallest-area ellipse [14]
corresponding to it. This ellipse represents the distribution of points
obtained when using the most stable gait for $\tau$ (see Fig. 2).

To create general knowledge map, we first discretize $I^{t}_{S}$ into grids of
$n\times n$ pixels as shown in Fig. 5.c to obtain $I^{t}_{SD}$. Each grid in
the general knowledge map is assigned a cost value based on the terrain
classes that the pixels in the corresponding grid in $I^{t}_{SD}$ belong to.
Consequently, ($\mathcal{C}_{g}^{t}$) is constructed as,

$\mathcal{C}_{g}^{t}(i,j)=\frac{\gamma}{n^{2}}\sum_{(a,b)\in
I^{t}_{SD}(i,j)}\underset{\forall
g\in\mathcal{G}}{\mathrm{min}}\big{(}\mathbf{Ar}(\mathcal{E}^{t}(\tau_{a,b},g)\big{)},$
(1)

where, $C_{g}^{t}(i,j)$ denotes the traversability cost for the $(i,j)^{th}$
grid in the general knowledge map at time t. $\gamma$ is a scaling factor.
$\mathcal{G}$ represents the set of all gaits, and
$\mathbf{Ar}(\mathcal{E}^{t}(\tau_{a,b},g))$ refers to the area of the ellipse
associated with using gait $g$ in terrain type $\tau_{a,b}$ present at pixel
$(a,b)$.

Additionally, by detecting the predominant terrain $\tau_{pred}$ in a $1\times
1$ square meter area in front of the robot in $I^{t}_{SD}$, we can choose the
most stable gait to traverse it. This is done based on the gait $g$ that leads
to the smallest area for the ellipse $\mathcal{E}^{t}(\tau_{pred},g)$. That
is,

$g^{*}=\underset{g\in\mathcal{G}}{\mathrm{argmin}}\,\mathbf{Ar}(\mathcal{E}^{t}(\tau_{pred},g)).$
(2)

Figure 3: The overall system architecture AMCO that couples vision and
proprioception perception modules. We use the robot’s joint position, forces,
and battery current to compute our traversability measure. We also use a
semantic segmentation module to classify the terrains. After that, three
traversability cost maps are created: general knowledge map (vision-based),
history map (vision and proprioception), and proprioception map . All of them
are coupled based on the reliability of the input RGB images to create a
coupled cost map for the local planner.

###  IV-B Recent Traversability History Map

We define traversability history of a terrain type $\tau$ as a list of its
traversability ($|\mathbf{p}^{t}_{\tau}|_{2}$) accumulated over a duration
$T_{\tau}$ by the robot. The intuition behind $T_{\tau}$ is that the longer
the robot has traversed a terrain $\tau$, the more reliable its traversability
cost estimate becomes. This history is then coupled with the general knowledge
map $C_{g}^{t}$. This is because, intuitively, if soil is particularly muddy
and unstable on a given day—indicating low stability—it is justified to
reflect this observation in the traversability cost for all the soil regions
ahead of the robot, even if typically soil is perceived to be more stable by
the costs in $\mathcal{C}^{t}_{g}$. Building on this intuition, we formulate
the recent traversability history as a costmap $\mathcal{C}_{h}^{t}$ for a
terrain $\tau$ as,

$\mathcal{C}_{h}^{t}(i,j)=\begin{cases}\\!\begin{aligned}
&\alpha\cdot\sum_{l=0}^{T_{\tau_{a,b}}}(\left(\left\lvert\mathbf{p}^{l}_{\tau}\right\rvert_{2}-\mathcal{C}_{g}^{l}(i,j)\right)),\\\
&\qquad\quad\text{if }(a,b)\in
I^{t}_{SD}(i,j)\,\,\text{and}\,\,\tau_{a,b}\in\Gamma,\end{aligned}\\\
0,\qquad\qquad\text{otherwise}.\end{cases}$ (3)

Here, $\Gamma$ is the set of terrains that the robot has traversed in the
past, and $T_{\tau_{a,b}}$ is the time the robot spent traversing terrain
$\tau_{a,b}$. $\mathcal{C}_{h}^{t}(i,j)$ represents the adjusted
traversability cost at grid $(i,j)$ and time $t$, and similarly for
$\mathcal{C}_{g}^{t}(i,j)$. $\alpha$ is an adjustable factor. Equation 3
ensures that a traversability history cost is applied only to the regions with
previously traversed terrains in front of the robot.

###  IV-C Reliability Estimation of RGB images

Assessing the reliability of RGB images is essential for vision-based sensing.
The image’s brightness and its blurriness can affect the semantic segmentation
(see figure 4) and consequently the reliability of our general knowledge map
(IV-A) and history map (IV-B) . Here, we discuss how we evaluate those two
visual phenomena:

####  IV-C1 Brightness Percentage

We use two methods to calculate the brightness of an image. The first computes
the mean brightness ($r_{m}ean$) of an image as the average of the RGB values
for each pixel, normalized to a
percentage:$r_{mean}=\frac{1}{N}\sum_{i=1}^{N}\left(\frac{R_{i}+G_{i}+B_{i}}{3}\right)$,
Where N denotes the number of pixels in the image. $R_{i}$, $G_{i}$, and
$B_{i}$ represent the red, green, and blue color values of the $i^{th}$ pixel,
respectively. The arithmetic mean is widely used to estimate the brightness,
however, it can be misleading in outdoor environments as it treats all the RGB
pixels uniformly. To improve the brightness estimation, we additionally use
[46] to compute the luminance (luma) of an image as:
$r_{luma}=\frac{1}{N}\sum_{i=1}^{N}\left(\rho_{1}\cdot R_{i}+\rho_{2}\cdot
G_{i}+\rho_{3}\cdot B_{i})\right)$. Similar to $r_{mean}$ but with scalar
weights: $\rho_{1}$, $\rho_{2}$, $\rho_{3}$.

Figure 4: Reliability Estimation of RGB images: we estimate the reliability of
RGB images (top row) by measuring two factors, the image’s brightness, and
blurriness as both affect semantic segmentation (bottom row). (a) and (b) show
two brightness levels for an RGB image. (c) shows a sharp image (with almost
no blur). (d) shows how rocky terrains could lead to blurriness in the image.

####  IV-C2 Blurriness

An image that is perceived as sharp (not blurry) is typically associated with
high fidelity and clear detail representation, which affects semantic
segmentation (see figure 4). To quantify the sharpness/blurriness of an image,
we use two methods. The first method employs the Haar wavelet transform [47]
to derive an energy map $E_{map}$ which can be used to estimate a blurriness
score ($r_{hwt}$)of an image. Deep-learning methods were used previously to
detect motion blur [48, 49]. However, the datasets for motion blur in outdoor
settings are limited. Therefore, we create a dataset with images from
unstructured outdoor environments with different degrees of motion blur
corruption, and the $\%$ of corruption as their labels. Then, we train a
ResNet50 [50] model on our dataset. We represent the output of the model as,
$O=\Phi(I^{t}_{RGB})$. We use both methods together to improve blurriness
detection.
Overall, we formulate the reliability score $\xi$ as follows:

$\xi=\lambda_{1}\cdot r_{mean}+\lambda_{2}\cdot r_{luma}+\lambda_{3}\cdot
r_{hwt}+\lambda_{4}\cdot O$ (4)

Here, $\lambda_{1}$, $\lambda_{2}$, $\lambda_{3}$, and $\lambda_{4}$ are
coefficients that balance the contributions of brightness and blur to the
overall reliability score.

Figure 5: Traversability cost maps of our method. (a) The input RGB image, (b)
The segmented image with the color labels as (stable: green, vegetation: red,
granular: yellow and poor foothold: orange), (c) The general knowledge map
(vision-based), (d) The history map, (e) The proprioception map . (f) The
coupled map . Dark blue reflects low traversability cost in (c-d) maps and
conversely red indicates high traversability cost. As shown in the figure,
concrete shows low cost in the general knowledge map and particularly evident
in the proprioception-based cost map as the robots captured the terrain
stability using proprioception.

###  IV-D Current Proprioception Map

Apart from the general knowledge map and history map , we also use the robot’s
current proprioceptive sensing $|\mathbf{p}^{t}_{\tau}|_{2}$ to estimate
terrain traversability due to its reliability in indicating how the terrain
feels regardless of the vision-based sensing. We construct a current
proprioception map $\mathcal{C}_{p}$ by extrapolating
$|\mathbf{p}^{t}_{\tau}|_{2}$ based on the distance $d_{i,j}$ from the robot’s
location without using the terrain segmentation (unlike $\mathcal{C}^{t}_{g}$
and $\mathcal{C}^{t}_{h}$) as,

$\mathcal{C}_{p}^{t}(i,j)=\left(\mathcal{U}-\delta\cdot|\mathbf{p}^{t}_{\tau}|_{2}\right)\cdot(1-d_{i,j}).$
(5)

Here, $\mathcal{U}$ is a positive value corresponding to the cost of
traversing a moderately traversable terrain. We assume a moderately
traversable terrain as we do not use the terrain information ahead from the
terrain segmentation. $\mu$ is a scale factor for the traversability’s impact
on cost. $d_{i,j}$ is the normalized distance to the $(i,j)^{th}$ grid from
the bottom center grid in front of the robot (see Fig. 5.e), with values
ranging from 0 (directly in front) to 1 (furthest from the robot).

###  IV-E Adaptive Multimodal Coupling

The Adaptive Multimodal Coupling mechanism combines the general knowledge map
$\mathcal{C}_{g}^{t}$, history map $\mathcal{C}_{h}^{t}$, and the
proprioception map $\mathcal{C}_{p}^{t}$ into a coupled traversability cost
map $\mathcal{C}_{coupled}^{t}$. This integration is achieved through the
reliability metric $\xi\in[0-1]$ (Section IV-C), which assesses the quality of
RGB images to adaptively adjust the contributions of the vision-based
components. The construction of $\mathcal{C}_{coupled}^{t}$ is formulated as,

$\mathcal{C}_{coupled}^{t}(i,j)=\xi\cdot(\mathcal{C}_{g}^{t}(i,j)+\mathcal{C}_{h}^{t}(i,j))+\mathcal{C}_{p}^{t}(i,j).$
(6)

Here, each $(i,j)^{th}$ grid in the input maps results in a corresponding
$(i,j)^{th}$ grid in $C_{coupled}^{t}$. The intuition behind this formulation
lies in the different reliability of the modalities. The components reliant on
vision ($C_{g}^{t}$ and $C_{h}^{t}$) are susceptible to variations in
environmental conditions, such as motion blur, which can diminish their
reliability. Conversely, the proprioception-based component $C_{p}^{t}$
provides an accurate measure of the terrain’s physical properties, unaffected
by visual distortions. Thus, $\xi$ serves as an adaptive scaling factor,
reducing the influence of vision-based assessments when their reliability is
compromised, and ensuring that coupled map reflects the most accurate
traversability information possible.

Figure 6: Navigation trajectories of AMCO (Ours) and the other methods in
three challenging outdoor scenarios. AMCO, ProNav, and RFC can switch between
three gaits (trot, crawl, and amble) during navigation as presented in three
different colors. AMCO, ProNav, and RFC can switch between three gaits (trot,
crawl, and amble) during navigation as presented in three different colors.
The trajectory colors are represented as follow: AMCO (trot: brown, crawl:red,
amble: pink), ProNav [14] (trot: blue, crawl:purple, amble: light blue), GaNav
[8] (orange), Spot’s Inbuilt (yellow), and RFC [18] (trot: green, crawl:light
green, amble: light beige). Vision-only methods such as GA-Nav fail under low
light conditions while proprioception-only methods such as ProNav lead to
robot failures in extremely unstable terrains since proprioception cannot
estimate trversability beforehand. In contrast, AMCO minimizes the robot’s
instability during navigation by adaptively coupling both vision and
proprioception.

###  IV-F Navigation using the Coupled Traversability Cost Map

We incorporate a modified version of the Model Predictive Controller (MPC) in
[39] to generate actions (i.e., ($v,\omega$) linear and angular velocity
pairs) for the robot to prefer relatively stable terrains while reaching user-
defined local goals. MPC in [39] calculates a restricted velocity search space
$\mathcal{V}_{r}$ by choosing only the obstacle-free and dynamically feasible
actions from an action space
$\mathcal{V}_{s}=\\{(v,\omega)|v\in[0,v_{max}],\omega\in[-\omega_{max},\omega_{max}]\\}$,
where $v_{max}$ and $\omega_{max}$ are the robot’s linear and angular velocity
limits.

Then, we define an objective function $J(v,\omega)$ as follows to calculate
the optimal action from the restricted velocity space $\mathcal{V}_{r}$.

$J(v,\omega)=\beta_{1}.goal(v,\omega)+\beta_{2}.obs(v,\omega)+\beta_{3}.sur(v,\omega),$
(7)

where $goal(v,\omega)$ and $obs(v,\omega)$ are cost terms that indicate the
distance to the goal and proximity to an obstacle for a given action
$(v,\omega)\in\mathcal{V}_{r}$. $\beta_{i}\,\forall i=1,2,3$ are tunable
weights. We introduce a traversability cost term $sur(v,\omega)$ to leverage
the terrain perception information encoded in the coupled traversability cost
map $\mathcal{C}_{coupled}$. To calculate the $sur(v,\omega)$ for a given
action $(v,\omega)$, we first extrapolate the action for a $\Delta T$ time and
obtain a trajectory $traj^{R}(v,\omega)$ w.r.t. the robot. Then,
$traj^{R}(v,\omega)$ is projected to the cost map using perspective projection
[51]. Let’s denote the projected trajectory on the cost map as
$traj^{C}(v,\omega)\in\mathcal{C}_{coupled}$. Then, the terrain surface
traversability cost $sur(v,\omega)$ is calculated as,

$sur(v,\omega)=\frac{1}{|traj^{C}(v,\omega)|}\sum_{(i,j)\in
traj^{C}(v,\omega)}\mathcal{C}_{coupled}^{t}(i,j),$ (8)

where $\mathcal{C}_{coupled}(i,j)$ is the traversability cost of the
$(i,j)^{th}$ location on the $\mathcal{C}_{coupled}^{t}$ at time t, and
$|traj^{C}(v,\omega)|$ is the cardinality of the $traj^{C}(v,\omega)$.
Finally, the optimal navigation action $(v^{*},\omega^{*})$ is obtained as,

$(v^{*},\omega^{*})=\underset{(v,\omega)\in\mathcal{V}_{r}}{\operatorname{argmin}}J(v,\omega).$
(9)

After that, we send $(v^{*},\omega^{*})$ along with $g^{*}$ (which is computed
from equation 2) to the robot’s controller.

##  V Results and Analysis

###  V-A Implmentation & Robot Setup

We implement AMCO on Boston Dynamics Spot, a quadruped robot with 12 degrees
of freedom (DOF) which provides joint feedback (position, velocities, and
forces) from the robot legs and the current consumed by the battery.
Additionally, the robot is equipped with a VLP16 Velodyne lidar and a Zed 2i
camera. AMCO runs on an Intel NUC edge computer equipped with an Intel i7 CPU,
and an Nvidia RTX2060 GPU. We use the following other parameters for our
implementation:
$n=40,\gamma=1,\alpha=4.5\rho_{1}=0.299,\rho_{2}=0.587,\rho_{3}=0.114,\delta=\,31.875,\mathcal{U}\,=127,\lambda_{1}=0.0008,\lambda_{2}=0.001,\lambda_{3}=\,0.0025,\lambda_{4}=\,0.003,v_{max}=\,0.6\,m/s,\omega_{max}=\,0.2\,rad/s,\beta_{1}=\,2.4,\beta_{2}\,=\,3.2,\beta_{3}\,=0.05$.

###  V-B Comparison Methods

  * •

Spot’s in-built planner: A planner that uses RGB-D cameras to detect and avoid
obstacles.

  * •

GA-Nav [8]: A vision-based method that uses semantic segmentation of RGB
images to compute traversability costs for different terrains. It is combined
with a local planner [52] to compute trajectories on low-cost terrains and
avoid obstacles.

  * •

ProNav [14]: A proprioceptive-based method that uses joint feedback and
battery’s current to estimate traversability and changes to an appropriate
gait while computing goal-conditioned velocities using [2].

  * •

Random Forest Classifier (RFC) [18]: It uses proprioceptive signals to
classify the terrain type. We used the dataset in [14] to train the classifier
to identify between four different terrain types (granular, poor foothold,
high resistance and stable). RFC is combined with [2] to generate goal-
directed velocities $(v^{*},\omega^{*})$.

###  V-C Evaluation Metrics

  * •

Success Rate: The ratio of successful navigation trials where the robot was
able to reach its goal without freezing or colliding with obstacles.

  * •

Normalized Trajectory Length: The ratio between the robot’s trajectory length
and the straight-line distance to the goal averaged across both successful and
unsuccessful trials.

  * •

IMU Energy Density: The mean of the aggregated squared acceleration values
measured by the IMU sensors across the x, y, and z axes, calculated over the
successful trials [23]: $E_{i}=\sum_{n=1}^{N}a_{i}^{2}$, and
$E_{\text{Total}}=E_{ax}+E_{ay}+E_{az}$, where $a_{i}$ represents one of the
three acceleration signals (x, y, and z axes), and $N$ is the IMU readings
along the trajectory.

  * •

Vibration Cost: The cumulative sum of deviations, measured from a predefined
stable reference terrain, in the actuator positions at the robot’s hip joints
along its trajectory [14]:

$\delta_{j}(t)=\begin{cases}\left|p^{j}(t)-\min(p^{j}_{\text{ref}})\right|&\text{if
}p^{j}(t)<\min(p^{j}_{\text{ref}}),\\\
\left|p^{j}(t)-\max(p^{j}_{\text{ref}})\right|&\text{if
}p^{j}(t)>\max(p^{j}_{\text{ref}}).\\\ \end{cases}$

Where, $p^{j}(t)$ is the position of joint $j$ at time $t$, and
$p^{j}_{\text{ref}}$ represents reference positions from a stable terrain
(concrete). The total Vibration Cost at time $t$ is then computed as
$\text{Vibration Cost}(t)=\sum_{j}\delta_{j}(t)$.

###  V-D Test Scenarios

  * •

Scenario 1: contains granular terrain (sand) and grass.

  * •

Scenario 2: contains dense vegetation.

  * •

Scenario 3: contains bushes, mulch, and concrete.

  * •

Scenario 4: contains mud, grass and concrete.

Metrics | Method |  Scen. 1 |  Scen. 2 |  Scen. 3 |  Scen. 4
---|---|---|---|---|---
Success Rate (%) $\uparrow$ | In-built system |  10 |  10 |  - |  -
GA-Nav[8] |  80 |  30 |  20 |  60
RFC[18] |  40 |  50 |  60 |  30
ProNav[14] |  60 |  60 |  70 |  40
AMCO w/o reliability |  70 |  60 |  50 |  80
AMCO w/o history |  70 |  70 |  80 |  60
| AMCO (ours) |  100 |  90 |  100 |  90
Normalized Trajectory Length | In-built system |  1.215 |  1.420 |  - |  -
GA-Nav[8] |  1.324 |  1.394 |  2.105 |  1.447
RFC[18] |  1.089 |  0.916 |  1.129 |  0.838
ProNav[14] |  1.063 |  0.948 |  1.036 |  0.861
AMCO w/o reliability |  1.192 |  1.131 |  1.235 |  1.217
AMCO w/o history |  1.230 |  1.178 |  1.189 |  1.253
| AMCO (ours) |  1.171 |  1.064 |  1.093 |  1.184
IMU Energy Density $\downarrow$ | In-built system |  37506 |  51764 |  - |  -
GA-Nav[8] |  18392 |  29354 |  21349 |  26096
RFC[18] |  23412 |  30233 |  26043 |  37412
ProNav[14] |  21342 |  26490 |  24392 |  35291
AMCO w/o reliability |  14323 |  25374 |  25034 |  24523
AMCO w/o history |  16271 |  24361 |  22375 |  25828
| AMCO (ours) |  13928 |  19832 |  20126 |  23120
Vibration Cost $\downarrow$ | In-built system |  29.3 |  48.7 |  - |  -
GA-Nav[8] |  14.3 |  28.5 |  23.9 |  19.4
RFC[18] |  15.9 |  29.2 |  37.4 |  36.7
ProNav[14] |  16.4 |  31.3 |  34.9 |  34.1
AMCO w/o reliability |  12.3 |  24.1 |  26.6 |  19.1
AMCO w/o history |  11.5 |  22.8 |  21.4 |  23.4
| AMCO (ours) |  9.3 |  20.3 |  19.3 |  17.3
Table III: The table shows the quantitative results of AMCO and the other
methods over 10 trials. We use four navigation metrics to evaluate our
method’s performance. All metrics are averaged over both the successful and
unsuccessful trails (reaching the goal).

###  V-E Analysis and Discussion

We evaluated our method’s navigation performance qualitatively in Figs. 1 and
6, and quantitatively in Table III. Across the four scenarios, our method AMCO
consistently outperforms the other methods in terms of successful goal-
reaching by effectively selecting appropriate gaits and velocities to reach
the designated goal. Further, AMCO results in lower vibration experienced by
the robot in all scenarios compared to the other methods.

In Scenario 1, GA-Nav generates significantly longer trajectories preferring
grass over the granular sand terrain, and demonstrates oscillatory behavior
near the boundary between the two terrains. ProNav and RFC use relatively
straight trajectories and switch to crawl gait after encountering heavy
instability in the granular sand region. However, in certain instances, their
inconsistent gait selection leads to sinkage in the sand. In contrast, AMCO
switches to the crawl gait in advance using the general knowledge map to
minimize the potential instabilities in the forthcoming terrain (i.e., sand).

Scenario 2 depicts a navigation task on concrete followed by a densely
vegetated region. ProNav leads to leg entanglement in vegetation due to its
delayed gait switching. GANav’s perception of vegetation is affected by image
motion blur which leads to inconsistent segmentation. However, AMCO generates
trajectories to maximize the stay in the concrete region while switching to
the amble gait before entering the vegetated region to reduce the leg
entanglement risks.

In Scenario 3, our method AMCO relies heavily on proprioception map for
navigation due to low and varying lighting conditions which results in less
reliable RGB images. Both Spot’s in-built system and GANav struggles to reach
the goal due to erroneous perception from the camera images under challenging
lighting. The complexity of the muddy terrain in Scenario 4 poses significant
challenges to all the methods. Particularly, RFC and ProNav methods experience
considerable leg sinkage due to delayed gait switching. Although GA-Nav
attempts to take longer trajectories through grass and concrete, the method
struggles in muddy regions due to its fixed gait. In contrast, AMCO initially
adjusts its gait using the general knowledge map and later changes the
trajectory to avoid the heavily deformable muddy regions to reach the goal.

Benefits of Image Reliability: We observe that our method’s navigation
performance is significantly affected without the image reliability
estimation, especially under low-light conditions (scenario 3) and motion blur
(scenarios 2 and 4). This is primarily due to the inconsistent segmentation
impacts on the general knowledge map, which eventually results in errors in
the coupled traversability cost estimation. However, AMCO’s adaptive coupling
which accounts for image reliability ensures prioritizing the proprioception
under unreliable image inputs.

Benefits of Traversability History: We observe a notable decrease in success
rate when traversability history is omitted from AMCO’s formulation.
Particularly in scenarios 1 and 4, where the visually similar-looking granular
terrain’s deformability varies from one region to another. However, the use of
traversability history allows AMCO to avoid severely deformable regions based
on recent experiences on the same terrain. Further, the recent history enables
AMCO to update the forthcoming terrain conditions better, compared to relying
only on fixed costs provided by image segmentation.

##  VI Conclusion, Limitations & Future work

We present AMCO, a novel approach for quadruped robot navigation through
challenging outdoor environments by adaptively combining vision-based and
proprioceptive-based perception capabilities. Our method effectively utilizes
semantic segmentation from RGB images and proprioceptive inputs, to generate a
coupled perception representation. This enables the selection of appropriate
gaits and velocities, which significantly improve navigation success rates and
stability across various terrains. Our method has some limitations. For
instance, AMCO’s reliance on proprioceptive data under dark conditions limits
its capabilities. It’s a good direction to explore integrating other sensor
modalities in evaluating traversability such as (thermal or hyperspectral
cameras). Furthermore, incorporating Vision Language Models (VLMs) could offer
more insights into complex environments, due to their common reasoning
capabilities.

## References

  * [1] J. Frey, M. Mattamala, N. Chebrolu, C. Cadena, M. Fallon, and M. Hutter, “Fast traversability estimation for wild visual navigation,” _arXiv preprint arXiv:2305.08510_ , 2023.
  * [2] A. J. Sathyamoorthy, K. Weerakoon, T. Guan, M. Russell, D. Conover, J. Pusey, and D. Manocha, “Vern: Vegetation-aware robot navigation in dense unstructured outdoor environments,” _arXiv preprint arXiv:2303.14502_ , 2023.
  * [3] S. Sotnik and V. Lyashenko, “Agricultural robotic platforms,” 2022.
  * [4] G. Valsecchi, C. Weibel, H. Kolvenbach, and M. Hutter, “Towards legged locomotion on steep planetary terrain,” in _2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2023, pp. 786–792.
  * [5] L. Bruzzone and P. Fanghella, “Functional redesign of mantis 2.0, a hybrid leg-wheel robot for surveillance and inspection,” _Journal of Intelligent & Robotic Systems_, vol. 81, pp. 215–230, 2016.
  * [6] T. Yoshiike, M. Kuroda, R. Ujino, H. Kaneko, H. Higuchi, S. Iwasaki, Y. Kanemoto, M. Asatani, and T. Koshiishi, “Development of experimental legged robot for inspection and disaster response in plants,” in _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2017, pp. 4869–4876.
  * [7] J. Sun, Y. Meng, J. Tan, C. Sun, J. Zhang, N. Ding, H. Qian, and A. Zhang, “A vision-based perception framework for outdoor navigation tasks applicable to legged robots,” in _2017 Chinese Automation Congress (CAC)_. IEEE, 2017, pp. 2894–2899.
  * [8] T. Guan, D. Kothandaraman, R. Chandra, A. J. Sathyamoorthy, K. Weerakoon, and D. Manocha, “Ga-nav: Efficient terrain segmentation for robot navigation in unstructured outdoor environments,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 3, pp. 8138–8145, 2022.
  * [9] A. Li, C. Yang, J. Frey, J. Lee, C. Cadena, and M. Hutter, “Seeing through the grass: Semantic pointcloud filter for support surface learning,” _arXiv preprint arXiv:2305.07995_ , 2023.
  * [10] A. J. Sathyamoorthy, K. Weerakoon, M. Elnoor, and D. Manocha, “Using lidar intensity for robot navigation,” _arXiv preprint arXiv:2309.07014_ , 2023.
  * [11] S. Dey, D. Fan, R. Schmid, A. Dixit, K. Otsu, T. Touma, A. F. Schilling, and A.-A. Agha-Mohammadi, “Prepare: Predictive proprioception for agile failure event detection in robotic exploration of extreme terrains,” in _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2022, pp. 4338–4343.
  * [12] K. Weerakoon, A. J. Sathyamoorthy, M. Elnoor, and D. Manocha, “Vapor: Holonomic legged robot navigation in outdoor vegetation using offline reinforcement learning,” _arXiv preprint arXiv:2309.07832_ , 2023.
  * [13] Z. Fu, A. Kumar, A. Agarwal, H. Qi, J. Malik, and D. Pathak, “Coupling vision and proprioception for navigation of legged robots,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 17 273–17 283.
  * [14] M. Elnoor, A. Sathyamoorthy, K. Weerakoon, and D. Manocha, “Pronav: Proprioceptive traversability estimation for autonomous legged robot navigation in outdoor environments,” _arXiv preprint arXiv:2307.09754_ , 2023.
  * [15] X. Yao, J. Zhang, and J. Oh, “Rca: Ride comfort-aware visual navigation via self-supervised learning,” in _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2022.
  * [16] C. A. Brooks and K. D. Iagnemma, “Self-supervised classification for planetary rover terrain sensing,” in _2007 IEEE aerospace conference_. IEEE, 2007, pp. 1–9.
  * [17] A. H. Al-dabbagh and R. Ronsse, “A review of terrain detection systems for applications in locomotion assistance,” _Robotics and Autonomous Systems_ , vol. 133, p. 103628, 2020.
  * [18] C. Kertész, “Rigidity-based surface recognition for a domestic legged robot,” _IEEE Robotics and automation letters_ , vol. 1, no. 1, pp. 309–315, 2016.
  * [19] D. Wisth, M. Camurri, and M. Fallon, “Vilens: Visual, inertial, lidar, and leg odometry for all-terrain legged robots,” _IEEE Transactions on Robotics_ , 2022.
  * [20] S. Jung, J. Lee, X. Meng, B. Boots, and A. Lambert, “V-strong: Visual self-supervised traversability learning for off-road navigation,” _arXiv preprint arXiv:2312.16016_ , 2023.
  * [21] J. Dallas, M. P. Cole, P. Jayakumar, and T. Ersal, “Terrain adaptive trajectory planning and tracking on deformable terrains,” _IEEE Transactions on Vehicular Technology_ , vol. 70, no. 11, pp. 11 255–11 268, 2021.
  * [22] F. J. Comin, W. A. Lewinger, C. M. Saaj, and M. C. Matthews, “Trafficability assessment of deformable terrain through hybrid wheel-leg sinkage detection,” _Journal of Field Robotics_ , vol. 34, no. 3, pp. 451–476, 2017.
  * [23] P. Try and M. Gebhard, “A vibration sensing device using a six-axis imu and an optimized beam structure for activity monitoring,” _Sensors_ , vol. 23, no. 19, p. 8045, 2023.
  * [24] E. I. Al Khatib, M. A. K. Jaradat, and M. F. Abdel-Hafez, “Low-cost reduced navigation system for mobile robot in indoor/outdoor environments,” _IEEE Access_ , vol. 8, pp. 25 014–25 026, 2020.
  * [25] Y. D. Yasuda, L. E. G. Martins, and F. A. Cappabianco, “Autonomous visual navigation for mobile robots: A systematic literature review,” _ACM Computing Surveys (CSUR)_ , vol. 53, no. 1, pp. 1–34, 2020.
  * [26] R. Miyamoto, M. Adachi, H. Ishida, T. Watanabe, K. Matsutani, H. Komatsuzaki, S. Sakata, R. Yokota, and S. Kobayashi, “Visual navigation based on semantic segmentation using only a monocular camera as an external sensor,” _Journal of Robotics and Mechatronics_ , vol. 32, no. 6, pp. 1137–1153, 2020.
  * [27] W. Zhan, C. Xiao, Y. Wen, C. Zhou, H. Yuan, S. Xiu, X. Zou, C. Xie, and Q. Li, “Adaptive semantic segmentation for unmanned surface vehicle navigation,” _Electronics_ , vol. 9, no. 2, p. 213, 2020.
  * [28] S. Fahmi, V. Barasuol, D. Esteban, O. Villarreal, and C. Semini, “c,” _IEEE Transactions on Robotics_ , 2022.
  * [29] A. Agarwal, A. Kumar, J. Malik, and D. Pathak, “Legged locomotion in challenging terrains using egocentric vision,” in _Conference on Robot Learning_ , 2022, pp. 403–415.
  * [30] M. Aladem, S. Baek, S. A. Rawashdeh, _et al._ , “Evaluation of image enhancement techniques for vision-based navigation under low illumination,” _Journal of Robotics_ , vol. 2019, 2019.
  * [31] K. Haresh, Y. Elvin, W. Garrett, B. Joydeep, and S. Peter, “Learning to extrapolate human preferences for preference aligned path planning,” _arXiv preprint arXiv:2309.09912_ , 2023.
  * [32] A. Loquercio, A. Kumar, and J. Malik, “Learning visual locomotion with cross-modal supervision,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 7295–7302.
  * [33] R. García, M. Estrada, M. Ebrahimi, F. Zuppichini, L. Gambardella, A. Giusti, and A. Ijspeert, “Gait-dependent traversability estimation on the k-rock2 robot,” in _2022 26th International Conference on Pattern Recognition (ICPR)_. IEEE, 2022, pp. 4204–4210.
  * [34] H. Karnan, E. Yang, D. Farkash, G. Warnell, J. Biswas, and P. Stone, “Sterling: Self-supervised terrain representation learning from unconstrained robot experience,” in _Conference on Robot Learning (CoRL 2023)_ , 2023.
  * [35] S. Teng, M. W. Mueller, and K. Sreenath, “Legged robot state estimation in slippery environments using invariant extended kalman filter with velocity update,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 3104–3110.
  * [36] J. Jin, C. Zhang, J. Frey, N. Rudin, M. Mattamala, C. Cadena, and M. Hutter, “Resilient legged local navigation: Learning to traverse with compromised perception end-to-end,” _arXiv preprint arXiv:2310.03581_ , 2023.
  * [37] T. Homberger, L. Wellhausen, P. Fankhauser, and M. Hutter, “Support surface estimation for legged robots,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 8470–8476.
  * [38] K. Weerakoon, A. J. Sathyamoorthy, M. Elnoor, and D. Manocha, “Adventr: Autonomous robot navigation in complex outdoor environments,” _arXiv preprint arXiv:2311.08740_ , 2023.
  * [39] D. Fox, W. Burgard, and S. Thrun, “The dynamic window approach to collision avoidance,” _IEEE Robotics Automation Magazine_ , vol. 4, no. 1, pp. 23–33, March 1997.
  * [40] T. Overbye and S. Saripalli, “Path optimization for ground vehicles in off-road terrain,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 7708–7714.
  * [41] L. Wellhausen and M. Hutter, “Artplanner: Robust legged robot navigation in the field,” in _Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2021.
  * [42] T. Miki, J. Lee, J. Hwangbo, L. Wellhausen, V. Koltun, and M. Hutter, “Learning robust perceptive locomotion for quadrupedal robots in the wild,” _Science Robotics_ , vol. 7, no. 62, p. eabk2822, 2022.
  * [43] H. Kolvenbach, C. Bärtschi, L. Wellhausen, R. Grandia, and M. Hutter, “Haptic inspection of planetary soils with legged robots,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 2, pp. 1626–1632, 2019.
  * [44] A. Maćkiewicz and W. Ratajczak, “Principal components analysis (pca),” _Computers & Geosciences_, vol. 19, no. 3, pp. 303–342, 1993.
  * [45] M. Wigness, S. Eum, J. G. Rogers, D. Han, and H. Kwon, “A rugd dataset for autonomous navigation and visual perception in unstructured outdoor environments,” in _International Conference on Intelligent Robots and Systems (IROS)_ , 2019.
  * [46] S. Bezryadin, P. Bourov, and D. Ilinih, “Brightness calculation in digital image processing,” in _International Symposium on Technologies for Digital Photo Fulfillment 2007_ , vol. 1, 2007, pp. 10–15.
  * [47] H. Tong, M. Li, H. Zhang, and C. Zhang, “Blur detection for digital images using wavelet transform,” in _2004 IEEE International Conference on Multimedia and Expo (ICME)_. IEEE, 2004.
  * [48] K. Purohit, A. B. Shah, and A. N. Rajagopalan, “Learning based single image blur detection and segmentation,” in _IPCV Lab, Department of Electrical Engineering, Indian Institute of Technology Madras, India_ , 2023.
  * [49] S. Nayak and B. Ravindran, “Reinforcement learning for improving object detection,” in _Indian Institute of Technology Madras, Chennai TN, India_ , 2023.
  * [50] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [51] K. Weerakoon, A. J. Sathyamoorthy, J. Liang, T. Guan, U. Patel, and D. Manocha, “Graspe: Graph based multimodal fusion for robot navigation in unstructured outdoor environments,” _arXiv preprint arXiv:2209.05722_ , 2022.
  * [52] K. Weerakoon, A. J. Sathyamoorthy, U. Patel, and D. Manocha, “Terp: Reliable planning in uneven outdoor environments using deep reinforcement learning,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 2022, pp. 9447–9453.


# A note on the stability of Monotone Markov Chains

Bar Light School of Mathematical Sciences, Department of Statistics and
Operations Research, Tel Aviv University, Israel. e-mail:
<EMAIL_ADDRESS>
Abstract:

> This note studies monotone Markov chains a subclass of Markov chains with
> extensive applications in operations research and economics. While the
> properties that ensure the global stability of these chains are well
> studied, their establishment often relies on the fulfillment of a certain
> splitting condition. We address the challenges of verifying the splitting
> condition, by introducing simple, applicable conditions that ensure global
> stability. The simplicity of these conditions is demonstrated through
> various examples including autoregressive processes and portfolio allocation
> problems.

Keywords: Markov chains; Monotone Markov chains; Global stability.

##  1 Introduction

Monotone Markov chains are an important class of Markov chains with widespread
applications across fields such as operations research, economics, and the
broader realm of applied probability. Their uses span a variety of areas,
including queueing systems, savings dynamics, and inventory management, to
name just a few. The properties of these chains have been extensively studied,
leading to the development of a rich literature that provides various
conditions under which these chains exhibit a unique stationary distribution
and global stability (for example, see Dubins and Freedman (1966),
Bhattacharya and Lee (1988), Hopenhayn and Prescott (1992), Lund and Tweedie
(1996), Bhattacharya and Majumdar (2007), Bhattacharya et al. (2010), and
Kamihigashi and Stachurski (2014)).

The establishment of these properties often hinges on the fulfillment of a
splitting condition (see Section 3.5 in Bhattacharya and Majumdar (2007)).
This condition, particularly elegant in the context of infinite state spaces,
is often easier to verify than classical irreducibility conditions. In fact,
it can sometimes hold in scenarios where irreducibility falls short, as noted
in Bhattacharya and Lee (1988) (see also Example 1). However, despite the
theoretical appeal of the splitting condition, verifying its applicability in
practical scenarios can be challenging. This note seeks to bridge this gap by
introducing a set of easily applicable conditions that imply global stability.
These conditions are satisfied when the Markov chain under consideration
exhibits specific concavity and contraction properties, which are typically
straightforward to verify in applications. To demonstrate the applicability of
these conditions, we present various examples from existing literature,
including AR(1) processes, RCA(1) processes, wealth evolution, and portfolio
allocation problems.

##  2 Main Results

Let $S=I_{1}\times\ldots\times I_{n}\subseteq\mathbb{R}^{n}$ where each
$I_{i}$ is a nonempty open, half-open, closed, or half-closed interval in
$\mathbb{R}$. We denote by $\mathcal{B}(S)$ the Borel sigma algebra on $S$ and
by $\mathcal{P}(S)$ the set of all probability measures on $S$ endowed with
the weak topology.

We consider the Markov chain $\\{X_{k}\\}_{k=1}^{\infty}$ on $S$ given by

$X_{k+1}=w(X_{k},V_{k+1})$ (1)

where $w:S\times E\rightarrow S$ is a measurable function and $V_{k}$’s are
independent and identically distributed random variables on some set $E$.

In this note we focus on monotone Markov chains. We endow $\mathbb{R}^{n}$
with the standard product partial order $\geq$, i.e., $x\geq y$ for
$x,y\in\mathbb{R}^{n}$ if $x_{i}\geq y_{i}$ for $i=1,\ldots,n$. A function $f$
from $S\subseteq\mathbb{R}^{n}$ to $\mathbb{R}^{n}$ is called increasing if
$x\geq y$ implies $f(x)\geq f(y)$ for all $x,y\in S$ and strictly increasing
if $x>y$ implies $f(x)>f(y)$ for all $x,y\in S$. We denote by
$[x^{\prime\prime},x^{\prime}]=\\{x\in\mathbb{R}^{n}:x^{\prime\prime}\leq
x\leq x^{\prime}\\}$ an order interval in $\mathbb{R}^{n}$ and by
$\mathbb{R}_{+}^{n}=\\{x\in\mathbb{R}^{n}:x\geq 0\\}$ the non-negative part of
$\mathbb{R}^{n}$.

Let $(E,\geq_{E})$ be partially ordered set. For the rest of the note we
assume that $w:S\times E\rightarrow S$ is continuous in the first argument and
is increasing, i.e., $w(x^{\prime},v^{\prime})\geq
w(x^{\prime\prime},v^{\prime\prime})$ whenever $x^{\prime}\geq
x^{\prime\prime}$ and $v^{\prime}\geq_{E}v^{\prime\prime}$.

We denote by $\mu_{k}^{x}$ the law of $X_{k}$ when the initial state is
$X_{1}=x$, and by $Q(x,B)=\mathbb{P}(v\in E:w(x,v)\in B)$ for any
$B\in\mathcal{B}(S)$ the Markov transition kernel

The probability measure $\pi$ on $S$ is called a stationary distribution of
$Q$ if $M\pi=\pi$ where $M\mu(B)=\int_{X}Q(x,B)\mu(dx)$ for any
$B\in\mathcal{B}(S)$. A sequence of probability measures $\\{\mu_{k}\\}$ on
$S$ is called tight if for all $\epsilon>0$ there is a compact set
$K_{\epsilon}$ of $S$ such that $\mu_{k}(S\setminus K_{\epsilon})\leq\epsilon$
for all $k$. Tightness is a standard assumption in order to ensure the
existence of a stationary distribution (see Meyn and Tweedie (2012) for an
extensive study of stationary distributions). The Markov kernel $Q$ is called
globally stable if $Q$ has a unique stationary distribution $\pi$ and
$M^{t}\mu$ converges to $\pi$ for every $\mu\in\mathcal{P}(S)$.

We now present the main theorem of this note. We provide conditions that are
typically simple to verify on the function $w$ that imply the global stability
of $Q$. We illustrate the usefulness of these conditions after we provide the
proof of Theorem 1.

We will say that $(v^{\prime},v^{\prime\prime})$ is an ordered normal pair if
$v^{\prime},v^{\prime\prime}\in E$, $v^{\prime}>_{E}v^{\prime\prime}$,
$\mathbb{P}(v\in E:v\geq_{E}v^{\prime})>0$, $\mathbb{P}(v\in
E:v^{\prime\prime}\geq_{E}v)>0$, and $w(x,v^{\prime})>w(x,v^{\prime\prime})$
for all $x\in S$. For a given $v\in E$ a fixed point of $w(\cdot,v)$ is an
element $x\in S$ such that $w(x,v)=x$.

###### Theorem 1

Assume that the sequence $\\{\mu_{k}^{x}\\}_{k=1}^{\infty}$ is tight for any
$x\in S$.

Suppose that $(v^{\prime},v^{\prime\prime})$ is an ordered normal pair and the
following two conditions are satisfied:

(i) The function $w(\cdot,v^{\prime\prime})$ has a unique fixed point.

(ii) For any $x\in S$, there exist $y^{\prime\prime},y^{\prime}\in S$ such
that

$y^{\prime}\geq\max\\{w(y^{\prime},v^{\prime}),x\\}\text{ and
}y^{\prime\prime}\leq\min\\{w(y^{\prime\prime},v^{\prime\prime}),x\\}.$

Then $Q$ is globally stable.

To prove the theorem, we will need the following two Propositions. Recall that
a partially ordered set $(Z,\geq)$ is said to be a lattice if for all $x,y\in
Z$, $\sup\\{x,y\\}$ and $\inf\\{y,x\\}$ exist in $Z$. $(Z,\geq)$ is a complete
lattice if for all non-empty subsets $Z^{\prime}\subseteq Z$ the elements
$\sup Z^{\prime}$ and $\inf Z^{\prime}$ exist in $Z$. Every order interval
$[x^{\prime\prime},x^{\prime}]:=\\{x\in S:x^{\prime\prime}\leq x\leq
x^{\prime}\\}$ in $\mathbb{R}^{n}$ is a complete lattice.

We will use the following Proposition regarding the comparison of fixed
points. For a proof, see Corollary 2.5.2 in Topkis (2011).

###### Proposition 1

Suppose that $Z$ is a nonempty complete lattice, $E$ is a partially ordered
set, and $f(z,e)$ is an increasing function from $Z\times E$ into $Z$. Then
the greatest and least fixed points of $f(z,e)$ exist and are increasing in
$e$ on $E$.

We will use Proposition 2 to provide the sufficient conditions that imply the
stability of monotone Markov chains. The key condition that implies global
stability is a weaker version of the splitting condition (Bhattacharya and
Lee, 1988). For a proof, see Theorem 2 in Kamihigashi and Stachurski (2014)
(for results with convergence rates, but using a stronger splitting condition,
see Bhattacharya et al. (2010)).

###### Proposition 2

Assume that for any $x^{\prime},x^{\prime\prime}\in S$ with $x^{\prime}\geq
x^{\prime\prime}$ we have $\mathbb{P}(X_{m}^{\prime}\leq
X_{m}^{\prime\prime})$ for some integer $m$ where
$\\{X_{k}^{\prime}\\}_{k=1}^{\infty}$ and
$\\{X_{k}^{\prime\prime}\\}_{k=1}^{\infty}$ are independent Markov chains and
$X_{k}^{\prime}$ has a law $\mu_{k}^{x^{\prime}}$ and $X_{k}^{\prime\prime}$
has a law $\mu_{k}^{x^{\prime\prime}}$.

Then $Q$ is globally stable if and only if the sequence
$\\{\mu_{k}^{x}\\}_{k=1}^{\infty}$ is tight for any $x\in S$.

We are now ready to prove Theorem 1. We will show that the condition of
Proposition 2 holds.

Proof. Let $x^{\prime},x^{\prime\prime}\in S$ be such that $x^{\prime}\geq
x^{\prime\prime}$. Define the sequences $z_{k+1}=w(z_{k},v^{\prime})$ and
$y_{k+1}=w(y_{k},v^{\prime\prime})$ where $z_{1}=x^{\prime\prime}$ and
$y_{1}=x^{\prime}$.

First, suppose that $x^{\prime\prime}=z_{1}\leq w(z_{1},v^{\prime})$ and
$x^{\prime}=y_{1}\geq w(y_{1},v^{\prime\prime})$,

The sequence $\\{z_{k}\\}_{k=1}^{\infty}$ is an increasing sequence. To see
this, first note that $z_{2}=w(z_{1},v^{\prime})\geq z_{1}$. If $z_{k}\geq
z_{k-1}$ for some $k\geq 2$, then $w$ being increasing implies that
$z_{k+1}=w(z_{k},v^{\prime})\geq w(z_{k-1},v^{\prime})=z_{k}$. Hence, by
induction, $\\{z_{k}\\}_{k=1}^{\infty}$ is an increasing sequence. Similarly,
the sequence $\\{y_{k}\\}_{n=1}^{\infty}$ is a decreasing sequence.

From condition (ii), there exist $y^{\prime}$ and $y^{\prime\prime}$ in $S$
such that $y^{\prime\prime}\leq x^{\prime\prime}\leq x^{\prime}\leq
y^{\prime}$ and $w(y^{\prime},v^{\prime})\leq y^{\prime}$ and
$y^{\prime\prime}\leq w(y^{\prime\prime},v^{\prime\prime})$. Thus, the
function $f=w$ defined on
$[y^{\prime\prime},y^{\prime}]\times\\{v^{\prime\prime},v^{\prime}\\}$ and
equals $w$ is from
$[y^{\prime\prime},y^{\prime}]\times\\{v^{\prime\prime},v^{\prime}\\}$ into
$[y^{\prime\prime},y^{\prime}]$ because

$w(y,v^{\prime\prime})\leq w(y,v^{\prime})\leq w(y^{\prime},v^{\prime})\leq
y^{\prime}\text{ and }y^{\prime\prime}\leq
w(y^{\prime\prime},v^{\prime\prime})\leq w(y^{\prime\prime},v^{\prime})\leq
w(y,v^{\prime})$

for all $y\in[y^{\prime\prime},y^{\prime}]$. Note that the inequalities above
imply that the sequences $\\{z_{k}\\}_{k=1}^{\infty}$ and
$\\{y_{k}\\}_{n=1}^{\infty}$ are bounded.

Thus, the bounded and increasing sequence $\\{z_{k}\\}_{k=1}^{\infty}$
converges to a limit $C$ which is a fixed point of $w(\cdot,v^{\prime})$ by
the continuity of $w$. Similarly, the sequence $\\{y_{k}\\}_{n=1}^{\infty}$ is
decreasing and bounded and therefore converges to a limit $C^{\ast}$ which is
a fixed point of $w(\cdot,v^{\prime\prime})$. Note that $C\leq y^{\prime}$.

We claim that $C>C^{\ast}$. The function $f$ is increasing in both arguments.
Hence, $f$ is an increasing function from a complete lattice to a complete
lattice. From Proposition 1, the greatest and least fixed points of $f$ are
increasing on $\\{v^{\prime\prime},v^{\prime}\\}$. From condition (i), the
function $w(\cdot,v^{\prime\prime})$ has a unique fixed point $C^{*}$. Hence,
the least fixed point of $w(\cdot,v^{\prime})$ on
$[y^{\prime\prime},y^{\prime}]$, say $C^{\prime}$, satisfies $C^{*}\leq
C^{\prime}$. Using the fact that $w(x,v^{\prime})>w(x,v^{\prime\prime})$ for
all $x\in S$ we conclude that $C^{*}<C^{\prime}$. Because
$C\in[y^{\prime\prime},y^{\prime}]$ is a fixed point of $w(\cdot,v^{\prime})$
we have $C^{\prime}\leq C$ so $C^{*}<C$.

Let $x^{\ast}=(C+C^{\ast})/2$ then $x^{*}\in S$. Since $z_{k}\uparrow C$ and
$y_{k}\downarrow C^{\ast}$, there exists a finite $N_{1}$ such that
$z_{k}>x^{\ast}$ for all $k\geq N_{1}$, and similarly, there exists a finite
$N_{2}$ such that $y_{k}<x^{\ast}$ for all $k\geq N_{2}$. Let
$m=\max\\{N_{1},N_{2}\\}$. Thus, after $m$ steps, all sequences
$\\{y_{k}^{\prime}\\},\\{z_{k}^{\prime}\\}$ such that $y_{k}^{\prime}\leq
y_{k}$ and $z_{k}^{\prime}\geq z_{k}$ for all $k$ satisfy
$y_{k}^{\prime}<x^{*}<z_{k}^{\prime}$. Because $w$ is increasing, the
probability of a sequence $\\{z_{k}^{\prime}\\}$ such that $z_{k}^{\prime}\geq
z_{k}$ for $k=1,\ldots,m$ is at least $[\mathbb{P}(v\in
E:v\geq_{E}v^{\prime})]^{m}>0$. Hence, the probability of moving from state
$x^{\prime\prime}$ to the set $\\{x\in S:x\geq x^{\ast}\\}$ after $m$ steps is
at least $[\mathbb{P}(v\in E:v\geq_{E}v^{\prime})]^{m}>0$, and similarly, the
probability of moving from the state $x^{\prime}$ to the set $\\{x\in
S:x<x^{\ast}\\}$ after $m$ steps is at least $\mathbb{P}(v\in
E:v\leq_{E}v^{\prime\prime})]^{m}>0$.

Thus, we showed that $\mu_{m}^{x^{\prime}}(\\{x\in S:x<x^{*}\\})>0$ and
$\mu_{m}^{x^{\prime\prime}}(\\{x\in S:x\geq x^{*}\\})>0$ for some $x^{*}\in S$
and some integer $m$ when $x^{\prime\prime}\leq
w(x^{\prime\prime},v^{\prime})$ and $x^{\prime}\geq
w(x^{\prime},v^{\prime\prime})$.

Now consider the case that $x^{\prime\prime}\nleq
w(x^{\prime\prime},v^{\prime})$ and $x^{\prime}\ngeq
w(x^{\prime},v^{\prime\prime})$. From condition (ii) we can find
$y^{\prime},y^{\prime\prime}\in S$ such that

$y^{\prime\prime}\leq x^{\prime\prime}\leq x^{\prime}\leq y^{\prime}\text{ and
}y^{\prime\prime}\leq w(y^{\prime\prime},v^{\prime})\text{, }y^{\prime}\geq
w(y^{\prime},v^{\prime\prime}).$

Thus, using the argument above, there exists $y^{*}$ such that there is a
positive probability to move from the state $y^{\prime\prime}$ to the set
$\\{x\in S:x\geq y^{*}\\}$ and to move from the state $y^{\prime}$ to the set
$\\{x\in S:x<y^{*}\\}$ after $m$ steps. Because $w$ is increasing, $\mu_{m}$
is monotone, i.e., we have $\mu_{m}^{x}(B)\geq\mu_{m}^{y}(B)$ for every upper
set $B$ and $x\geq y$ where $B$ is an upper set if $z\in B$ implies
$z^{\prime}\in B$ for all $z^{\prime}\geq z$. Thus,

$\mu_{m}^{x^{\prime\prime}}(\\{x\in S:x\geq
y^{*}\\})\geq\mu_{m}^{y^{\prime\prime}}(\\{x\in S:x\geq y^{*}\\})>0$

and

$\mu_{m}^{x^{\prime}}(\\{x\in S:x<y^{*}\\})\geq\mu_{m}^{y^{\prime}}(\\{x\in
S:x<y^{*}\\})>0.$

We conclude that for any $x^{\prime\prime},x^{\prime}\in S$ such that
$x^{\prime}\geq x^{\prime\prime}$ we have $\mu_{m}^{x^{\prime}}(\\{x\in
S:x<y^{*}\\})>0$ and $\mu_{m}^{x^{\prime\prime}}(\\{x\in S:x\geq y^{*}\\})>0$
for some $y^{*}\in S$ and some integer $m$.

Hence,

$\mathbb{P}(X_{m}^{\prime}\leq
X_{m}^{\prime\prime})\geq\mathbb{P}(X_{m}^{\prime}\leq
y^{*})\mathbb{P}(X_{m}^{\prime\prime}>y^{*})>0$

for some $m$ when $\\{X_{k}^{\prime}\\}_{k=1}^{\infty}$ and
$\\{X_{k}^{\prime\prime}\\}_{k=1}^{\infty}$ are independent Markov chains and
$X_{k}^{\prime}$ has a law $\mu_{k}^{x^{\prime}}$ and $X_{k}^{\prime\prime}$
has a law $\mu_{k}^{x^{\prime\prime}}$.

From Proposition 2, $M$ has a unique stationary distribution and
$M^{n}\lambda$ converges to the unique stationary distribution for every
$\lambda\in\mathcal{P}(S)$.

If $S$ has a greatest and a least element then condition (ii) of Theorem 1 is
satisfied. Indeed, we can choose $y^{\prime}$ to be the greatest element and
$y^{\prime\prime}$ to be the least element in condition (ii). In this case, it
is also immediate that the tightness condition holds. This leads to the
following Corollary.

###### Corollary 1

Assume that $S$ has a greatest and a least element.

Suppose that $(v^{\prime},v^{\prime\prime})$ is an ordered normal pair and the
function $w(\cdot,v^{\prime\prime})$ has a unique fixed point. Then $Q$ is
globally stable.

In many cases, it is possible to identify a $v^{\prime\prime}$ such that
$w(\cdot,v^{\prime\prime})$ possesses a unique fixed point, thereby
facilitating the application of Theorem 1. For broader results where a unique
fixed point is assured, we may invoke contraction properties (see Corollary 2)
or concavity properties (see Corollary 3) of the function $w$.

Recall that the maximum norm on $\mathbb{R}^{n}$ is given by $\lVert
x\rVert_{\infty}=\max_{i}|x_{i}|$. A function $f$ from $\mathbb{R}^{n}$ to
$\mathbb{R}^{n}$ is said to be contraction with respect to the maximum norm if
$\lVert f(x)-f(y)\rVert_{\infty}\leq K\lVert x-y\rVert_{\infty}$ for some
$K\in(0,1)$ and all $x,y$. The next Corollary shows a connection between the
contraction properties of $w(\cdot,v)$ to global stability.

###### Corollary 2

Assume that the sequence $\\{\mu_{k}^{x}\\}_{k=1}^{\infty}$ is tight for any
$x\in S$.

Suppose that $(v^{\prime},v^{\prime\prime})$ is an ordered normal pair. Assume
that $S=\mathbb{R}^{n}$ and $w(x,v^{\prime})$ and $w(x,v^{\prime\prime})$ are
contractions with respect to the maximum norm.111A version of this Corollary
can be easily adjusted for other norms that are not the maximum norm. Also
note that the condition that $w(x,v^{\prime})$ is a contraction can be relaxed
if condition (ii) of Theorem 1 holds. Then $Q$ is globally stable.

Proof. To use Theorem 1 we need to show that conditions (i) and (ii) hold.

From the the Banach fixed-point theorem condition (i) holds.

Let $x\in S$ and let $\underline{x}=\min_{i}x_{i}$ and
$\overline{x}=\max_{i}x_{i}$. Assume that $\overline{x}>0$. Define
$y^{\prime}=tz\in S$ where $t\geq 1$ is a scalar and $z_{i}=\overline{x}$ for
$i=1,\ldots,n$. Then $y^{\prime}\geq x$ and $\lVert
y^{\prime}-x\rVert_{\infty}=t\overline{x}-\underline{x}$. By the contraction
property we have

$w_{i}(y^{\prime},v^{\prime})-w_{i}(x,v^{\prime})\leq
K(t\overline{x}-\underline{x})$

for $i=1,\ldots,n$ and some $K\in(0,1)$. We have

$K(t\overline{x}-\underline{x})+w_{i}(x,v^{\prime})\leq t\overline{x}\text{ if
and only if
}\frac{w_{i}(x,v^{\prime})-K\underline{x}}{t}\leq(1-K)\overline{x}$

which holds for some large $t$. Hence, $w_{i}(y^{\prime},v^{\prime})\leq
y^{\prime}_{i}$ for each $i$. The case that $\underline{x}\leq 0$ can be shown
in a similar manner.

An analogous argument shows that there exists $y^{\prime\prime}\in S$ such
that $y^{\prime\prime}\leq x$ and $y^{\prime\prime}\leq
w(y^{\prime\prime},v^{\prime\prime})$. Thus, condition (ii) of Theorem 1
holds.

Corollary 2 can be useful in easily proving the global stability of important
Markov processes such as autoregressive processes. We now provide a few
examples.

###### Example 1

(Autoregressive process) Consider the Markov chain on $S=\mathbb{R}^{n}$ which
describes an autoregressive process

$X_{t+1}=w(X_{t},V_{t+1})=AX_{t}+V_{t+1}$

where $V_{t+1}$ is a random vector on $E=\mathbb{R}^{n}$ with
$\mathbb{E}|V_{i,t+1}|<\infty$ for $i=1,\ldots,n$ and $A\in\mathbb{R}^{n\times
n}_{+}$. Then $w$ is an increasing function when $E$ is endowed with the
product order on $\mathbb{R}^{n}$. Suppose that the operator norm $\rVert
A\rVert_{\infty}$ is bounded by $0<K<1$ where $\rVert
A\rVert_{\infty}=\sup_{x\neq 0}\rVert Ax\rVert_{\infty}/\rVert
x\rVert_{\infty}$. Then $w(\cdot,v)$ is a contraction with respect to the
maximum norm for every $v$. Hence, we can apply Corollary 2 to prove the
stability of the Markov chain. Interestingly, one can provide examples of
AR(1) processes where standard methods to prove stability such as
irreducibility do not apply (see for example Athreya and Pantula (1986) and
Kamihigashi and Stachurski (2012)).

The AR(1) example above can be extended to a positive autoregressive process
with random coefficients (RCA) as our next example shows. Note that in this
example, $w(\cdot,v)$ is typically not a contraction for every $v$.

###### Example 2

(Nonlinear positive autoregressive process with random coefficients). Consider
the Markov chain on $S=\mathbb{R}_{+}$

$X_{t+1}=w(X_{t},V_{t+1}):=Y_{t+1}f(X_{t})+Z_{t+1}$ (2)

with $V_{t+1}=(Y_{t+1},Z_{t+1})$ where $Z_{t+1}$ is a random variable on
$E=\mathbb{R}_{+}$ with a finite mean, $Y_{t+1}$ is a random variable on
$\mathbb{R}_{+}$, and $f:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ is an
increasing function that is Lipschitz continuous with a constant $1$, i.e.,
$|f(x_{2})-f(x_{1})|\leq|x_{2}-x_{1}|$ for all $x_{1},x_{2}\in\mathbb{R}_{+}$.
In particular, $f$ can be the identity function and then the chain describes a
positive autoregressive process with a random coefficient (see Goldie and
Maller (2000) and Erhardsson (2014)). Then $w$ is an increasing function when
$E=\mathbb{R}_{+}^{2}$ is endowed with the product order on $\mathbb{R}^{2}$.
We assume that the tightness condition holds (it holds if
$\mathbb{E}(Y_{t+1})<1$). Hence, by choosing
$v^{\prime}=(y^{\prime},z^{\prime})$ and
$v^{\prime\prime}=(y^{\prime\prime},z^{\prime\prime})$ that are an ordered
pair with $1>y^{\prime}>y^{\prime\prime}$ so that $w$ is contraction, we can
apply Corollary 2 to prove the stability of the Markov chain. This example can
be generalized to the multidimensional case where $S=\mathbb{R}^{n}_{+}$.

###### Remark 1

The Markov chain induced by Equation (2) plays an important role in economic
dynamics. This equation models the wealth evolution of an agent who receives a
random income $Z_{t}$ and experiences random returns on savings $R_{t}$. In
each period, the agent has a wealth of $X_{t}$ and chooses to save $f(X_{t})$
according to some saving function $f$ that is typically determined by
optimizing the agent’s expected discounted utility. Such dynamics of wealth
are prevalent in various economic models and have been extensively studied, as
surveyed in Benhabib and Bisin (2018). The Markov chain induced by Equation
(2) also describes the evolution of firms’ states in some dynamic oligopoly
models (Light and Weintraub, 2022).

We provide an additional example of a portfolio allocation problem where one
can easily prove the global stability of the Markov chain under consideration
using Corollary 2.

###### Example 3

(Portfolio allocation problem). Consider the following allocation problem. In
each period $t$, an agent has wealth $x_{t}\geq 0$ to invest in two different
assets. Asset 1 yields a random return $R_{1,t+1}$ and asset 2 yields a random
return $R_{2,t+1}$. In addition, the random variable $Z_{t+1}$ describes the
withdrawal or addition to the agent’s wealth in each period. The agent solves
the portfolio optimization problem, and the solution is given by two non-
negative functions $g_{1}(x)$ and $g_{2}(x)$, such that $g_{1}(x)+g_{2}(x)=x$.
Here, $g_{i}(x)$ describes how much the agent invests in asset $i$ when the
agent has a wealth of $x$. We assume a standard assumption that $g_{i}$ is
increasing for $i=1,2$, i.e., the agent invests more in each asset when the
agent’s wealth is higher. The Markov chain on $S=[0,\infty)$ that describes
the agent’s wealth evolution is given by

$X_{t+1}=w(X_{t},V_{t+1}):=\max\\{(1+R_{1,t+1})g_{1}(X_{t})+(1+R_{2,t+1})g_{2}(X_{t})+Z_{t+1},0\\}$

with $V_{t+1}=(R_{1,t+1},R_{2,t+1},Z_{t+1})$. Then $w$ is increasing. Now
suppose that $(v^{\prime},v^{\prime\prime})$ is an ordered normal pair such
that $v^{\prime}=(r^{\prime},r^{\prime},z^{\prime})$,
$v^{\prime\prime}=(r^{\prime\prime},r^{\prime\prime},z^{\prime\prime})$ with
$0>r^{\prime}>r^{\prime\prime}$, $z^{\prime}>z^{\prime\prime}$,
$z^{\prime}>0$. Then

$w(x,v^{\prime})=\max\\{(1+r^{\prime})g_{1}(x)+(1+r^{\prime})g_{2}(x)+z^{\prime},0\\}=(1+r^{\prime})x+z^{\prime}$

and $w(\cdot,v^{\prime})$ is a contraction as $(1+r^{\prime})\in(0,1)$.
Similarly, $w(\cdot,v^{\prime\prime})$ is a contraction and we can use
Corollary 2 to prove the stability of the chain.

The next Corollary shows that natural concavity properties of $w$ can be
leveraged in order to use Theorem 1 and prove the global stability of monotone
Markov chains.

###### Corollary 3

Assume that the sequence $\\{\mu_{k}^{x}\\}_{k=1}^{\infty}$ is tight for any
$x\in S$.

Suppose that $(v^{\prime},v^{\prime\prime})$ is an ordered normal pair. Assume
that $S=\mathbb{R}_{+}^{n}$ and let $w=(w_{1},\ldots,w_{n})$. Suppose that
$w(a,v^{\prime\prime})>a$, $w(a,v^{\prime})>a$ for some $a>0$ and
$w(b,v^{\prime\prime})<b$, $w(b,v^{\prime})<b$ for some $b>a$.

Then if $w_{i}(\cdot,v^{\prime\prime})$ and $w_{i}(\cdot,v^{\prime})$ are
strictly concave for each $i=1,\ldots,n$, $Q$ is globally stable.

Proof. To use Theorem 1 we need to show that conditions (i) and (ii) hold.

Under the conditions of the Corollary, it is well known that condition (i) of
Theorem 1 holds (see for example Kennan (2001)).

For condition (ii) of Theorem 1, we can choose $y^{\prime\prime}$ to be the
vector $0$ since it is the least element of $S$. In addition, for any $x\in
S$, we can take $\lambda\in[0,1]$ and $b=\lambda y^{\prime}$ such that
$y^{\prime}\geq x$ and

$b_{i}>w_{i}(b,v^{\prime})=w_{i}(\lambda
y^{\prime}+(1-\lambda)0,v^{\prime})\geq\lambda
w_{i}(y^{\prime},v^{\prime})+(1-\lambda)w_{i}(0,v^{\prime})\geq\lambda
w_{i}(y^{\prime},v^{\prime})$

so $y_{i}^{\prime}>w_{i}(y^{\prime},v^{\prime})$ for $i=1,\ldots,n$. Thus,
$y^{\prime}\geq\max\\{w(y^{\prime},v^{\prime}),x\\}$ and condition (ii) of
Theorem 1 holds.

## References

  * Athreya and Pantula (1986) Athreya, K. B. and S. G. Pantula (1986): “Mixing properties of Harris chains and autoregressive processes,” _Journal of applied probability_ , 23, 880–892.
  * Benhabib and Bisin (2018) Benhabib, J. and A. Bisin (2018): “Skewed wealth distributions: Theory and empirics,” _Journal of Economic Literature_ , 56, 1261–1291.
  * Bhattacharya and Majumdar (2007) Bhattacharya, R. and M. Majumdar (2007): _Random dynamical systems: theory and applications_ , Cambridge University Press.
  * Bhattacharya et al. (2010) Bhattacharya, R., M. Majumdar, and N. Hashimzade (2010): “Limit theorems for monotone Markov processes,” _Sankhya A_ , 72, 170–190.
  * Bhattacharya and Lee (1988) Bhattacharya, R. N. and O. Lee (1988): “Asymptotics of a Class of Markov Processes Which are not in General Irreducible,” _The Annals of Probability_ , 1333–1347.
  * Dubins and Freedman (1966) Dubins, L. E. and D. A. Freedman (1966): “Invariant probabilities for certain Markov processes,” _The Annals of Mathematical Statistics_ , 37, 837–848.
  * Erhardsson (2014) Erhardsson, T. (2014): “Conditions for convergence of random coefficient AR (1) processes and perpetuities in higher dimensions,” _Bernoulli_ , 20, 990–1005.
  * Goldie and Maller (2000) Goldie, C. M. and R. A. Maller (2000): “Stability of perpetuities,” _The Annals of Probability_ , 28, 1195–1218.
  * Hopenhayn and Prescott (1992) Hopenhayn, H. A. and E. C. Prescott (1992): “Stochastic monotonicity and stationary distributions for dynamic economies,” _Econometrica: Journal of the Econometric Society_ , 1387–1406.
  * Kamihigashi and Stachurski (2012) Kamihigashi, T. and J. Stachurski (2012): “An order-theoretic mixing condition for monotone Markov chains,” _Statistics & Probability Letters_, 82, 262–267.
  * Kamihigashi and Stachurski (2014) ——— (2014): “Stochastic stability in monotone economies,” _Theoretical Economics_ , 9, 383–407.
  * Kennan (2001) Kennan, J. (2001): “Uniqueness of positive fixed points for increasing concave functions on Rn: An elementary result,” _Review of Economic Dynamics_ , 4, 893–899.
  * Light and Weintraub (2022) Light, B. and G. Y. Weintraub (2022): “Mean field equilibrium: uniqueness, existence, and comparative statics,” _Operations Research_ , 70, 585–605.
  * Lund and Tweedie (1996) Lund, R. B. and R. L. Tweedie (1996): “Geometric convergence rates for stochastically ordered Markov chains,” _Mathematics of operations research_ , 21, 182–194.
  * Meyn and Tweedie (2012) Meyn, S. P. and R. L. Tweedie (2012): _Markov Chains and Stochastic Stability_ , Springer Science & Business Media.
  * Topkis (2011) Topkis, D. M. (2011): _Supermodularity and Complementarity_ , Princeton university press.