#  _R2H_ : Building Multimodal Navigation Helpers that _Respond to Help_

Yue Fan, Kaizhi Zheng, Jing Gu, Xin Eric Wang
University of California, Santa Cruz
{yfan71, kzheng31, jgu110<EMAIL_ADDRESS>
###### Abstract

The ability to assist humans during a navigation task in a supportive role is
crucial for intelligent agents. Such agents, equipped with environment
knowledge and conversational abilities, can guide individuals through
unfamiliar terrains by generating natural language responses to their
inquiries, grounded in the visual information of their surroundings. However,
these multimodal conversational navigation helpers are still underdeveloped.
This paper proposes a new benchmark, _Respond to Help (R2H)_ , to build
multimodal navigation helpers that can respond to help, based on existing
dialog-based embodied datasets. R2H mainly includes two tasks: (1) Respond to
Dialog History (RDH), which assesses the helper agent’s ability to generate
informative responses based on a given dialog history, and (2) Respond during
Interaction (RdI), which evaluates the helper agent’s ability to maintain
effective and consistent cooperation with a task performer agent during
navigation in real-time. Furthermore, we propose a novel task-oriented
multimodal response generation model that can see and respond, named _SeeRee_
, as the navigation helper to guide the task performer in embodied tasks.
Through both automatic and human evaluations, we show that SeeRee produces
more effective and informative responses than baseline methods in assisting
the task performer with different navigation tasks. Project website:
https://sites.google.com/view/respond2help/home.

Figure 1: R2H demo. A task-oriented helper provides responses to help a task
performer who is delivering a package. The helper has access to task and
environment information that is not available to the task performer, for
example, the location of the destination and map of the environment.

##  1 Introduction

Assisting humans in real-world scenarios is a fundamental capability that AI
agents should possess. A multimodal conversational helper agent, as a
supportive role providing real-time navigation assistance in the environment,
can greatly improve work efficiency and success rate of humans, like emergency
rescue in complex architectures. Figure 1 illustrates an example of a delivery
person seeking assistance in navigating through an unfamiliar building. With
the help from a navigation helper agent, the delivery person can ask questions
about directions and receive responses that are tailored to visual information
about the current surroundings.

The most critical aspect for a conversational helper agent’s success is its
ability to effectively guide task performers in a cooperative manner. To
achieve this, the helper agent needs to provide real-time assistance, ensuring
the successful completion of the tasks. However, creating such an agent poses
a significant challenge, because the evaluation of the helper agent’s
performance is not solely dependent on the agent itself, but also requires the
presence of a task performer.

To fully consider the cooperative dynamic between the helper agent and a task
performer, involving a human in the evaluation as a performer would be the
most direct approach, though it is often impractical due to the high cost and
low efficiency. An alternative solution is to involve another agent as the
task performer. In this work, we introduce the Respond to Help (R2H)
benchmark, designed to automatically evaluate conversational multimodal
navigation helpers in this cooperative dynamic. The R2H benchmark incorporates
pre-trained and fixed task performer agents into the evaluation tasks. These
performer agents follow the responses from the helper agent, providing a
practical and efficient way to evaluate the helper agent’s performance.

Leveraging two existing vision-and-dialog navigation datasets, CVDN Thomason
et al. (2020) and AlFRED Shridhar et al. (2020), our R2H benchmark introduces
two novel tasks: the Respond to Dialog History task and the Respond during
Interaction task. In the Respond to Dialog History (RDH) task, the helper
agent generates a response based on the dialog history, with the aim of
guiding the task performer agent closer to the target. In the Respond during
Interaction (RdI) task, the helper agent is required to generate multiple
responses based on the demands of the task performer, guiding the task
performer agent to navigate to the destination. As a result, R2H benchmark
provides a practical evaluation for helper-performer cooperation in both
short- and long-term. Specially distinguished from other language generation
tasks emphasising the similarity of generated language to the ground truth,
the tasks in R2H benchmark especially focus on how much the success rate of
task performers is benefited with the help from the helper.

We also present a multimodal helper agent, SeeRee, to respond to inquiries
from the task performer. Our helper agent leverages the oracle knowledge about
the task and environment that is unavailable to the task performer, such as
the destination location in a navigation task, to generate responses to
inquiries from the task performer. SeeRee employs pre-trained vision and
language models, specifically the Video Swin Transformer Liu et al. (2022) and
BERT Devlin et al. (2019), to handle multimodal inputs. To manage long input
sequences, SeeRee leverages a novel Conditional Optimized Sparse (COS)
attention mask. Moreover, we introduce a Parse by Step method, which leverages
GPT-3 Brown et al. (2020) to transform ground-truth human responses into
structured, noise-free step-by-step instructions. Using those parsed
instructions (instead of human responses) as the new supervision results can
train a better helper agent with improved performance in helping the task
performer.

In our experiments, we benchmark SeeRee and a baseline model using the R2H
benchmark. The results and ablation studies demonstrate that SeeRee surpasses
the baseline in generating effective responses; validate the COS attention
mask and Parse by Step method. We also conduct extensive human evaluations to
assess how effectively SeeRee’s responses assist humans in completing embodied
tasks, which shows that SeeRee delivers highly accurate responses that
significantly enhance the task success rate compared to the baseline.

Additionally, we ask human testers to rate the faithfulness and naturalness of
the responses evaluate the response from helper agents with automatic scores.
As a result, our experiments indicate that a higher language similarity to
human helpers does not necessarily lead to a more successful conversational
helper agent.

The main contributions are concluded as follows:

  * •

We present the Respond to Help (R2H) benchmark as a testbed for automatically
evaluating the capabilities of multimodal conversational navigation helper
agent, that helps task performers complete tasks by providing natural language
responses to inquiries based on environment information.

  * •

We propose a novel task-oriented multimodal helper agent, SeeRee, utilizing
the Conditional Optimized Sparse (COS) attention mask and noise-free step-by-
step instructions (Parse by Step).

  * •

Our experiments on the R2H task and human evaluations show that SeeRee
outperforms other baseline helper agents and even approaches human-level
performance in some aspects. The experiments also indicate that a closer
linguistic resemblance to human helpers does not automatically translate into
a more effective conversational helper agent.

i

ii

iii

Figure 2: Comparison between different dialog-based embodied benchmark types.
The benchmark either (i) evaluates task performers, where performers follow
instructions in human annotations, (ii) evaluates helper-performer pairs,
where the helper and performer agents need to jointly learn and be evaluated
together, or (iii) evaluates helper agents only (our R2H benchmark), where
helpers need to provide appropriate instructions according to performer and
environment information.

##  2 The R2H Benchmark

Significant differences exist between building a helper agent and developing
task performer agents for dialog-based multimodal navigation tasks. Task
performers developed in the pioneer works Thomason et al. (2020); Gao et al.
(2022); Fan et al. (2022) are challenged as command followers, evaluated based
on their performance of following dialog histories from human annotations, as
shown in Figure 2i. However, building the helper agent requires evaluations in
a collaborative setting with task performers because being able to provide
responses to help the task performer is the most important aspect of the
helper agent.

Involving human task performers to evaluate the helper agent is ideal but
expensive. Alternatively, inspired by Padmakumar et al. (2022), Nguyen and
Daumé III (2019) and Roman et al. (2020) that study and build specific helper
and performer agents to collaborate (shown in Figure 2ii), we introduce the
Respond to Help (R2H) benchmark (shown in Figure 2iii), involving task
performer in the evaluation process. This approach allows for a more
comprehensive and realistic assessment of the helper agent’s capabilities, as
it tests the agent’s ability to respond effectively in a wide range of
scenarios. The benchmark includes two novel tasks, the Respond to Dialog
History (RDH) task and the Respond during Interaction (RdI) task, building
upon three existing vision-and-dialog navigation datasets. RDH task evaluates
helper agents in a situation where partial human dialog history is provided
and RdI task aims at challenging the helper agents with real collaborative
scenarios.

###  2.1 Respond to Dialog History Task

Respond to Dialog History (RDH) Task focuses on evaluating the accuracy and
completeness of the response from helper agents. The helper agent is
challenged with understanding the dialog history and respond to help the task
performer based on information about the task and environment in the form of
image sequences. After the responses $\hat{r}_{i}$ generated, they will be
concatenated with all available human dialog history
$h_{i-1}={\\{q_{0},r_{0},\dots,q_{i-1},r_{i-1}\\}}$ in the corresponding
trajectory before the inquiries $q_{i}$ from human task performers. As a
result, generated response from the helper agent forms a new dialog history
$\hat{h}=\\{h_{i-1},q_{i},\hat{r}_{i}\\}$ which becomes the input to the task
performer.

R2H benchmark adopts Sate-Of-The-Art open-sourced performer agents for each
vision-and-language navigation dataset. The task performer agent is pre-
trained on the original training set with human dialogs $h_{i}$ including the
response from the human helper $r_{i}$ and predict actions based on $\hat{h}$
for completing the task. Therefore, the progress and success made by the task
performer can be seen as a test of the accuracy and completeness of the
responses generated by the task performer agent.

###  2.2 Respond during Interaction Task

The Respond during Interaction (RdI) task challenges the ability of helper
agents to cooperate consistently with the task performer agent. Similar to the
RDH task, the RdI task involves a pre-trained task performer agent predicting
navigation actions based on dialog histories. However, unlike the RDH task, no
dialog history is initially provided in the RdI task. The task performer agent
initiates inquiries $\hat{q}_{i}$ for help when needed and navigate based on
the ongoing dialog between itself and the helper agent
$\hat{h}_{i}=\\{\hat{q}_{0},\hat{r}_{0},\dots,\hat{q}_{i},\hat{r}_{i}\\}$,
where $\hat{r}_{i}$ is the real-time responses from the helper agent to
$\hat{q}_{i}$. As a result, the dialog $\hat{h}_{i}$ as a result of
interaction serves as the primary source of guidance for the task performer
agent, making the consistent quality of the helper agent’s responses crucial
for successful navigation.

###  2.3 Adapting Existing Datasets

R2H benchmark establish the same tasks across different datasets.

#### Datasets

R2H benchmark is built upon existing vision-and-dialog navigation datasets
with dialogs between task performers and helpers.

  * •

CVDN Thomason et al. (2020) is situated in the Matterport3D simulator Chang et
al. (2017) with photo-realistic scenes. The dataset records the collaboration
between the human task performer and the human helper to complete navigation
tasks of finding target objects in different indoor environments. The helper
uses expert knowledge to guide the task performer with natural language when
questions are asked by the task performer.

  * •

DialFRED Gao et al. (2022) is built on Ai2-thor Kolve et al. (2017) simulator
with synthetic views. Similar to the CVDN, the helper and task performer
collaborate to navigate to targets; however, DialFRED dataset involves a
significant amount of template based dialogs and is collected in a way that
each trajectory only corresponds to one pair of inquiry and response, without
any dialog history. Therefore it is not suitable for RdI task.

#### Adaption Across Datasets

Given the variability of available information across different datasets and
environments, the R2H benchmark is designed with a harmonizing approach,
converting the environment specific information into image sequences. A
script-based sampler are designed to generate the image sequences by
leveraging expert information in each dataset. The sampler outputs image
sequences showing the task performer’s views on the shortest path to the
destination in both CVDN and DialFRED datasets. Especially for CVDN dataset,
following the data collection process in dataset, a connectivity graph for
viewpoints is used to generate the shortest path and therefore the image
sequence length is variable but limited to views within 5 viewpoints of the
current position. As a result, helper agents can be evaluated in different
datasets with the same task inputs, which enhanced the benchmark’s versatility
to further adapt to new datasets.

###  2.4 Metrics

Since we aim to evaluate how capable the response generated by helper agents
is in helping the task performer, we adopt the metrics for task completion:
Goal Progress (GP), evaluating the distance of the progress made towards the
destination, where it is computed as the trajectory length, deducted by the
remaining trajectory from the current location to the destination viewpoint;
Success Rate (SR), showing the ratio of tasks being completed successfully;
Success weighted by inverse Path Length (SPL) Anderson et al. (2018) or Path
Weighted Success Rate (PWSR) Gao et al. (2022): measuring the Success Rate
weighted by the total length of the navigation trajectory.

##  3 The SeeRee Agent

In this section, we introduce the helper agent that can _see and respond_ ,
named SeeRee. SeeRee generates responses to task-oriented navigation inquiries
from the task performer. As shown in Figure 3, our helper agent SeeRee
generates natural language responses to the task performer’s inquiries based
on the task and environment information that is not aware by the task
performer. Since the available information can vary among different tasks and
environments, SeeRee is designed to adapt to different scenarios by converting
the information into image sequences using task- and environment-specific
samplers. The sampler we adopted for the experiments is detailed in Section 2.
Then, the image sequences are padded to a fixed length Lin et al. (2022) and
encoded by Video Swin Transformer (VidSwin) Liu et al. (2022). The image
sequence embedding is concatenated with BERT text embedding Devlin et al.
(2019) and fed into a multimodal transformer. Finally, the responses are
generated from the multimodal transformer in an auto-regressive way.

Figure 3: Overview of SeeRee. The visual and text inputs are encoded and fed
into the multimodal transformer, where a Conditional Optimized Sparse (COS)
attention mask is applied. The COS attention mask has fixed binary values
except for the learnable conditional mask $C$ for visual embedding (VE) that
is conditioned on VE itself. Yellow, blue, and green colored rows correspond
to the attention masks for LE of input inquiry and generated response and VE,
respectively.

###  3.1 Multimodal Transformer

Following prior multimodal language generation studies Hu et al. (2020); Lin
et al. (2022), our multimodal transformer takes as input the embedding
containing both text and image information and generates natural language
responses in a unidirectional sequence-to-sequence generation process. We
treat the input inquiries as prompts for generating the response, and a
special token [CLS] is added to the end of the inquiry. During training, we
apply Mask Language Modeling (MLM) Devlin et al. (2019) to the response where
$80\%$ tokens are masked with [MSK] tokens, and $10\%$ tokens are changed
randomly. Cross entropy loss is applied to predictions for the masked tokens:

$L_{MLM}=\Sigma_{i}L_{CrossEntropy}(y_{i},\hat{y}_{i}),$ (1)

where $y_{i}$ is the masked token at position $i$ and $\hat{y}_{i}$ is the
prediction.

At inference time, the text is generated in an auto-regressive manner, where
we insert multiple [MSK] tokens after the [CLS] token and predict tokens to
replace [MSK]tokens one by one unidirectionally until the prediction is [EOS]
or all the [MSK] tokens are predicted.

###  3.2 Conditional Optimized Sparse (COS) Attention Mask

One challenge in generating responses for dialog-based embodied tasks is
effectively modeling the long input image sequence, reducing the redundancy in
the repetitive images but keeping the critical details. To this end, we
introduce a Conditional Optimized Sparse (COS) attention mask for the
multimodal transformer, as shown in Figure 3. The mask can be divided into
three row sections, corresponding to in what range the embeddings for input
inquiry, the response generated, input image sequence can attend to,
respectively. The first row section shows that the language embedding (LE) for
input inquiry can attend to itself and the input visual embedding (VE). The
second row section means the LE for the generated response can attend to the
VE and all the previous LE, allowing unidirectional text generation Devlin et
al. (2019). The third row section indicates that the VE can attend to partial
itself and the LE of input inquiry. Especially, instead of being fulling
binary and pre-defined, a learnable conditional mask $C$ that is non-binary
and sparse is adopted in the third row section of the COS attention mask,
controlling the self-attention of the VE. $C$ is conditioned on VE, and the
mapping is modeled by:

$C=\sigma(f(\text{VE})),$ (2)

where $\sigma(x)=\frac{1}{1+e^{-x}}$ and $f$ is a multi-layer perceptron. In
this way, our COS attention mask uses a conditional optimizing strategy that
optimizes the attention mask based on the image sequence. Additionally, in
order to let the transformer attend to the specific details of the VE that are
most relevant to the task, we enforce $C$ to be sparse, letting the VE to
sparsely attend to itself using a sparsity loss Lin et al. (2022):

$L_{SPARSE}=\lambda\times\sum_{i=1}^{M}\sum_{j=1}^{M}\left|C_{i,j}\right|,$
(3)

where $\lambda$ is a regularization hyperparameter and $C_{i,j}$ is the value
of the learnable conditional mask $C$. As a result, COS attention mask enables
better encoding and understanding of long visual input and improves the
response generation result.

$\begin{array}[]{rl}\textbf{Prompt:}&\text{Commander says: `Yes to the
kitchen. Go to the left of the fireplace and then all the way up the stairs'.
}\\\ &\text{Step by step: 1. Yes. 2. go to the kitchen 3. go the left of the
fireplace, 4. go upstairs.}\\\ &\text{Commander says:\\_\\_\\_\\_. step by
step: 1.}\end{array}$
---
Index | Original response | Processed response
1 | Go into the bedroom and walk through it and exit it by using a door on the left. | $\begin{array}[]{l}\text{1. Enter the bedroom. }\\\ \text{2. Walk through it.}\\\ \text{3. Exit by using a door on the left.}\end{array}$
2 | Yeah keep going around the outside till you get to the end. And sorry about the mixup at first. | $\begin{array}[]{l}\text{1. Yeah.}\\\ \text{2. Keep going around the outside.}\\\ \text{3. Get to the end.}\end{array}$
3 | Go straight a little, then the right and go downstairs. | $\begin{array}[]{l}\text{1. Go straight a little.}\\\ \text{2. Go right.}\\\ \text{3. Go downstairs.}\end{array}$
4 | I would go back. | $\begin{array}[]{l}\text{1. Go back.}\end{array}$

Table 1: Examples of our Parse by Step method on the CVDN dataset Thomason et
al. (2020). We fill the original response to the blank of the prompt and input
to GPT-3 for sentence completion. The output from the GPT-3 becomes the
processed response with mainly task-related instructions kept and organized in
steps. Through Parse by Step, we preprocess the response in the training set.

###  3.3 Response Preprocessing with Parse by Step

Training a helper agent to directly imitate the responses in the human dialog
may not be optimal as they may be unorganized and include utterances
irrelevant to the task. Structured step-by-step instructions are easier for
the helper agent to learn. Therefore, we propose a Parse by Step method for
SeeRee, utilizing GPT-3 Brown et al. (2020), a large language model that has
been trained on a vast amount of natural language texts, to preprocess the
ground-truth responses in the training data. In line with the idea of in-
context learning Brown et al. (2020); Kojima et al. (2022), we manually create
the prompt for inputs to GPT-3. Table 1 illustrates the prompt and sampled
preprocessed results. By filling each response in the training set in the
blank of the prompt and letting GPT-3 complete the sentence, we get the
preprocessed training data from the output, which is parsed in a step-by-step
manner with a streamlined language pattern. As a result, the token $y_{i}$ in
the objective function (1) is sampled from a tokenized preprocessed human
response $Y$:

$y_{i}\in Tok(Y),Y=p(R),$ (4)

where $Tok$ is the tokenization process, $P$ is the Parse by Step method, and
$R$ is the original human response in the dialog of the training set. In our
experiments, with the preprocessed training data as supervision for training,
SeeRee is able to generate more informative responses.

##  4 Experiments

###  4.1 Implementation Details

We train SeeRee using AdamW optimizer Loshchilov and Hutter (2018) for 10k
iterations with a batch size of 6 and learning rate of $1e^{-4}$. We select
the results based on the best GP in the unseen validation set. We initialize
the encoders and multimodal transformers in SeeRee with weights from SwinBert
Lin et al. (2022) to benefit from its image sequence understanding ability.
Training takes about 12 hours on one NVIDIA A6000 GPU.

#### Baseline Model

We adopt the RMM Guide model ($\mathcal{G}$) Roman et al. (2020) as the
baseline model in our experiments. RMM $\mathcal{G}$ is a sequence-to-sequence
LSTM-based model that generates natural language help based on the input image
sequence. During the experiment, we apply the same sampler for both SeeRee and
the baseline model.

| $\begin{array}[]{c}\textbf{Seen}\\\ \textbf{Validation}\end{array}$ | $\begin{array}[]{c}\textbf{Unseen}\\\ \textbf{Validation}\end{array}$
---|---|---
Helper | $\begin{array}[]{c}\textbf{Task}\\\ \textbf{Performer}\end{array}$ | $\begin{array}[]{r}\text{GP}\uparrow\end{array}$ | $\begin{array}[]{r}\text{SPL}\uparrow\end{array}$ | $\begin{array}[]{r}\text{SR}\uparrow\end{array}$ | $\begin{array}[]{r}\text{GP}\uparrow\end{array}$ | $\begin{array}[]{r}\text{SPL}\uparrow\end{array}$ | $\begin{array}[]{r}\text{SR}\uparrow\end{array}$
$\begin{array}[]{l}\text{Human Annotator}\\\ \end{array}$ | $\begin{array}[]{l}\text{HAMT}\end{array}$ | 6.91 | 17.59 | 20.68 | 5.13 | 11.15 | 17.09
$\begin{array}[]{c}\text{RMM }\mathcal{G}\end{array}$ | 4.65 | 8.64 | 14.37 | 2.83 | 6.84 | 10.69
$\begin{array}[]{l}\text{SeeRee (ours)}\\\ \end{array}$ | 6.50 | 13.95 | 17.80 | 4.87 | 10.13 | 15.21

(a)

| $\begin{array}[]{c}\textbf{Seen}\\\ \textbf{Validation}\end{array}$ | $\begin{array}[]{c}\textbf{Unseen}\\\ \textbf{Validation}\end{array}$
---|---|---
Helper | $\begin{array}[]{c}\textbf{Task}\\\ \textbf{Performer}\end{array}$ | $\begin{array}[]{r}\text{SR}\uparrow\end{array}$ | $\begin{array}[]{r}\text{PWSR}\uparrow\end{array}$ | $\begin{array}[]{r}\text{SR}\uparrow\end{array}$ | $\begin{array}[]{r}\text{PWSR}\uparrow\end{array}$
$\begin{array}[]{l}\text{Human Annotator}\\\ \end{array}$ | $\begin{array}[]{l}\text{DialFRED}\\\ \text{Performer}\end{array}$ | 49.05 | 39.11 | 33.38 | 14.56
$\begin{array}[]{c}\text{RMM }\mathcal{G}\end{array}$ | 46.49 | 35.25 | 32.08 | 13.80
$\begin{array}[]{l}\text{SeeRee (ours)}\\\ \end{array}$ | 49.05 | 39.11 | 33.07 | 14.27

(b)

Table 2: Results of Respond to Dialog History (RDH) task on CVDN dataset (a)
and DialFRED dataset (b) Thomason et al. (2020); Gao et al. (2022). We replace
the response in validation sets with responses from different helper agents.
Since the task performer agent is trained with human dialog and is fixed, it
relies on the information contained in the response to complete the task.
Thus, the better the task performer agent performs in the task, the more
effective the response is.

###  4.2 RDH Task

#### Task Performer

For RDH on CVDN dataset, we use HAMT111https://github.com/cshizhe/VLN-HAMT.
Chen et al. (2021), pre-trained on the original CVDN Navigation from Dialog
History (NDH) task as the task performer. For RHD on DialFRED, we leverage the
task performer 222Due to unavailable model weights, we reproduced the model
with comparable results as in the original paper. in the original work Gao et
al. (2022) that takes a single round of input to complete the task.

#### Results

As shown in Table 2, on either dataset, the task performer agent achieves the
best performance using the response generated by SeeRee, outperforming the
results using responses from the baseline helper agent, RMM guider agent. We
also show the task performer’s performance on the original validation set,
where the responses are provided by human annotators. By comparing the
results, we find that SeeRee’s responses on CVDN are highly comparable to
those of human helpers in terms of effectiveness, with a difference of only
about $10\%$. Additionally, on DiaFRED, SeeRee even reaches the same
performance as human helpers in seen validation set for generating effective
responses that guide the task performer agent to success. We believe this is
because the human utterances in DialFRED are mostly template-based, which
eases the challenge in multimodal generation. We believe that once SeeRee is
well-trained, it could outperform human helpers by making fewer mistakes.

###  4.3 RdI Task

| $\begin{array}[]{c}\textbf{Seen}\\\ \textbf{Validation}\end{array}$ | $\begin{array}[]{c}\textbf{Unseen}\\\ \textbf{Validation}\end{array}$
---|---|---
Helper | $\begin{array}[]{c}\textbf{Task}\\\ \textbf{Performer}\end{array}$ | $\begin{array}[]{r}\text{SPL}\uparrow\end{array}$ | $\begin{array}[]{r}\text{SR}\uparrow\end{array}$ | $\begin{array}[]{r}\text{GP}\uparrow\end{array}$ | $\begin{array}[]{r}\text{SPL}\uparrow\end{array}$ | $\begin{array}[]{r}\text{SR}\uparrow\end{array}$ | $\begin{array}[]{r}\text{GP}\uparrow\end{array}$
$\begin{array}[]{l}\text{RMM }\mathcal{G}\\\ \end{array}$ | $\begin{array}[]{l}\text{RMM}\\\ \mathcal{N}+\mathcal{Q}\\\ \end{array}$ | 1.39 | 3.33 | 10.67 | 0.82 | 1.18 | 4.86
$\begin{array}[]{c}\text{RMM }\mathcal{G}\text{ (Fixed)}\end{array}$ | 1.70 | 3.33 | 9.55 | 0.66 | 2.36 | 5.41
$\begin{array}[]{l}\text{SeeRee (ours)}\\\ \end{array}$ | 2.33 | 5.55 | 10.74 | 0.87 | 1.57 | 5.55

Table 3: Results of evaluating different helper agents with the performer
agent formed by the RMM Navigator model ($\mathcal{N}$) and RMM Questioner
model ($\mathcal{Q}$) Roman et al. (2020) on the two-agent task built on CVDN
Thomason et al. (2020). Our SeeRee agent enables the best two-agent training
results.

#### Task Performer

We utilize the task performer model from the pioneering work RMM Roman et al.
(2020) that combines two components: the RMM Navigator model ($\mathcal{N}$),
responsible for predicting navigation actions, and the RMM Questioner model
($\mathcal{Q}$), generating inquires to the helper agent. As a result, the
combination allows the task performer collaborate with helper agents to
navigate towards destination.

#### Results

As shown in Table 3, we train and evaluate the same task performer agent
$\mathcal{N}+\mathcal{Q}$ with different response generation models in the RdI
task on CVDN Thomason et al. (2020): (1) the helper agent RMM $\mathcal{G}$ is
trained and updated jointly with the task performer agent; (2) the helper
agent RMM $\mathcal{G}$ is fixed during training, (3) the helper agent is
changed to SeeRee and kept fixed during training. The results demonstrate that
SeeRee, when serving as the helper agent, performs the best in collaborating
with the task performer in the RdI task. Interestingly, we find that only
updating the task performer agent during training leads to better results. One
possible explanation for this is that joint training may create potential
instability, making it challenging for both models to reach optimum
simultaneously. The helper agent could face difficulty in converging due to
the changing models of the task performer agent and vice versa.

###  4.4 Ablation Study

Helper | $\begin{array}[]{c}\textbf{COS}\\\ \textbf{attention mask}\end{array}$ | $\begin{array}[]{c}\textbf{Parse by Step}\end{array}$ | $\begin{array}[]{c}\textbf{Seen}\\\ \textbf{Validation}\end{array}$ | $\begin{array}[]{c}\textbf{Unseen}\\\ \textbf{Validation}\end{array}$
---|---|---|---|---
GP | B2 | R | GP | B2 | R
$\begin{array}[]{l}\text{Human}\\\ \text{Annotator}\\\ \end{array}$ | - | ✗ | 6.91 | - | - | 5.13 | - | -
$\begin{array}[]{l}\text{}\\\ \end{array}$ | - | ✓ | 7.26 | - | - | 5.10 | - | -
$\begin{array}[]{l}\text{SeeRee}\\\ \text{(ours)}\\\ \end{array}$ | ✗ | ✗ | 5.43 | 9.89 | 21.79 | 4.65 | 10.00 | 22.13
✓ | ✗ | 5.86 | 14.44 | 25.49 | 4.72 | 13.94 | 25.48
✓ | ✓ | 6.50 | 13.78 | 24.24 | 4.87 | 13.16 | 24.14

Table 4: Ablation study of the SeeRee agent on CVDN dataset Thomason et al.
(2020) based on GP in RDH task and language generation metrics, BLUE2 (B2) and
ROUGE-L (R). We directly apply our Parse by Step method to the original
validation data created by humans, showing that Parse by Step maintains
essential task-related information. The results show the effectiveness of COS
attention mask and Parse by Step in task-oriented response generation.

| $\begin{array}[]{c}\textbf{Task}\\\ \textbf{Completion}\end{array}$ | $\begin{array}[]{c}\textbf{Subjective}\\\ \textbf{Response Evaluation}\end{array}$
---|---|---
Helper | $\begin{array}[]{r}\text{GP}\uparrow\end{array}$ | $\begin{array}[]{r}\text{SPL}\uparrow\end{array}$ | $\begin{array}[]{r}\text{SR}\uparrow\end{array}$ | $\begin{array}[]{r}\text{Naturalness}\uparrow\end{array}$ | $\begin{array}[]{r}\text{faithfulness}\uparrow\end{array}$
$\begin{array}[]{l}\text{No helper}\\\ \end{array}$ | 3.54 | 2.23 | 4.50 | - | -
$\begin{array}[]{l}\text{RMM }\mathcal{G}\\\ \end{array}$ | 6.32 | 5.89 | 10.57 | 0.73/1 | 0.59/1
$\begin{array}[]{l}\text{SeeRee (ours)}\\\ \end{array}$ | 9.89 | 13.82 | 18.18 | 0.72/1 | 0.75/1

Table 5: Results of human evaluation on RdI task in Matterport3D simulator
Chang et al. (2017). The human testers start in initialized positions and will
be provided with target objects based on unseen validation data from CVDN
Thomason et al. (2020). Different helper agents are tested on the same set of
data and we measure the task completion of human testers, as well as the
subjective evaluation on the responses.

To thoroughly analyze the effect of different components in our model, we
conduct ablation studies on CVDN dataset based on RDH task and language
generation metrics, BLUE2 Papineni et al. (2002) and ROUGE-L Lin and Och
(2004). The result is shown in Table 4.

#### Conditional Optimized Sparse (COS) Attention Mask

is shown to benefit the response generation in the R2H task through ablation
studies. We repeated the same training on SeeRee model, but replaced the
conditional mask $C$ with a fixed attention mask with all ones. Results show
that when using the COS attention mask, the task performer receives
significant improvements. This illustrates that the COS attention mask helps
to enrich the response with more valuable information that comes from the
visual environment information, enabling better performance of the task
performer agent in approaching the destination.

#### Parse By Step

is first evaluated on the original validation set as a sanity check, where the
task performer infers on the human dialog from the original dataset, but the
response within is processed by our Parse by Step method. The results show
that the human response processed with Pase by Step is overall equally capable
as the original response, with a $5\%$ drop in SPL and SR on the seen
validation set and a $5\%$ increase in GP on the seen validation set and SR on
the unseen validation set. This indicates that the information contained in
the original response is kept. We then ablate the method on SeeRee by
comparing the SeeRee model trained on the training data preprocessed or not
with our Parse by Step method. The evaluation result shows that despite the
BLUE2 score and ROUGH-L score drops, GP in the RDH task receives a major
increase. This proves the effectiveness of our Parse by Step method in
facilitating the training of the helper agent and indicates that a high
language similarity to human responses does not necessarily equate to a more
effective conversational helper agent.

###  4.5 Human Evaluation

To further evaluate the performance of our helper agent, SeeRee, we conduct
human evaluations to assess the quality of the responses generated. Human
participants are paid with $17/h and they act as task performers navigating in
the Matterport3D simulator Chang et al. (2017). We randomly sample 60
trajectories in unseen validation sets of CVDN Thomason et al. (2020) to
provide the target object and starting position to the participants. During
the simulation, participants can control their movement in the environment
using their keyboards and ask questions to the helper agent whenever needed.
Upon completion of the task, we assess task success and goal progress in the
same way as in Thomason et al. (2020). Additionally, we ask participants to
provide their subjective assessment of the naturalness and faithfulness of the
responses. We evaluate SeeRee, a baseline helper agent, and the situation with
no helper agent. The results show that SeeRee provides the best results in
terms of task completion. Through subjective evaluation, we find that SeeRee
achieves significantly higher scores in terms of response faithfulness.
Despite being trained with data preprocessed by Parse by Step, where the
training supervision is no longer the original human utterances, it still
achieves almost equal score of naturalness compared to the baseline model
trained on original human responses. Through these evaluations, we show the
ability of SeeRee to help human users complete embodied tasks.

##  5 Related Work

#### Dialog-based Multimodal Embodied Benchmarks

Previous dialog-based multimodal embodied benchmarks are usually focusing on
evaluating either task performers Thomason et al. (2020); Gao et al. (2022);
Shi et al. (2022) or the corresponding pairs of task performer and helper
Roman et al. (2020); Hahn et al. (2020); Padmakumar et al. (2022). For
instance, the CVDN Thomason et al. (2020) evaluates a task performer to
navigate to a desired room by dialog histories. Gao et al. (2022) developed a
dialogue-enabled embodied instruction following benchmark, DialFRED, based on
the ALFRED benchmark Shridhar et al. (2020) and presented a task performer
framework. Further, in order to study the collaboration between the performer
and helper, there is a wide range of activities involved in these tasks, such
as navigating to a specific location Roman et al. (2020), locating positions
Hahn et al. (2020), and interacting objects Padmakumar et al. (2022). Compared
to these benchmarks, our R2H benchmark aims for better helper agents and is
the only benchmark for sole helper evaluation.

#### Multimodal-based Language Generation

SeeRee is in line with a growing collection of methods applied to the visual
question-answering task, where multiple inputs are encoded and then decoded
into text. Cho et al. (2021) introduced the VL-T5 model a unified framework
that learns different tasks in a single architecture with the same language
modeling objective; Wang et al. (2022) proposed Generative Image-to-text
Transformer, to unify vision-language tasks such as image/video captioning and
question answering; Fu et al. (2021) tackled video question answering problem
with VIOLET model that adopts a video transformer to model the temporal
dynamics of video inputs explicitly. Although showing great successes, one
problem shared by these works is the input frames to the model are limited in
quantity, only around half a dozen. Since the task of modeling the helper
generating responses requires more detailed information from the visual input
which may only flash once and will be easily ignored by sparse sampling, the
input has to include a longer image sequence. Lin et al. (2022) developed
SwinBERT, a learnable sparse attention mask for video caption that reduces the
computation cost and enables long frame sequence as input. However, the
learned sparse attention mask is fixed after training which lacks
generalization ability. In this work, we apply the COS attention mask for
SeeRee, improving the model’s ability to understand and uncover information
from long sequence inputs.

##  6 Conclusion

In this study, we introduce the Respond to Help (R2H) benchmark with two
tasks, Respond to Dialog History and Respond during Interaction, assessing a
helper agent’s guidance capabilities. With the R2H benchmark, we build and
evaluate a navigation helper agent, SeeRee. The results show that SeeRee
outperformed the baseline model. Through further ablation study and human
evaluation, we prove the effectiveness of SeeRee in assisting humans with
tasks and also argue that the effectiveness of responses cannot be determined
by their linguistic resemblance to human dialogue alone.

## Ethics Statement

The human evaluation part of this project is classified as exempt by Human
Subject Committee vis IRB protocols. Additionally, we recognize the potential
ethical issues related to training language generation model using human
dialog data, such as the possibility of the model learning harmful language
without understanding its context. To mitigate this concern, our proposed data
preprocessing method, Parse by Step, converts the responses in the training
data into more structured and task-specific instructions, effectively reducing
the presence of noise and profanity in the training data. As a result, the
likelihood of our model generating inappropriate responses is greatly
minimized.

## References

  * Anderson et al. (2018) Peter Anderson, Qi Wu, Damien Teney, Jake Bruce, Mark Johnson, Niko Sünderhauf, Ian Reid, Stephen Gould, and Anton Van Den Hengel. 2018.  Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3674–3683.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Chang et al. (2017) Angel Chang, Angela Dai, Thomas Funkhouser, Maciej Halber, Matthias Niessner, Manolis Savva, Shuran Song, Andy Zeng, and Yinda Zhang. 2017.  Matterport3d: Learning from RGB-D data in indoor environments.  _International Conference on 3D Vision (3DV)_.
  * Chen et al. (2021) Shizhe Chen, Pierre-Louis Guhur, Cordelia Schmid, and Ivan Laptev. 2021.  History aware multimodal transformer for vision-and-language navigation.  In _NeurIPS_.
  * Cho et al. (2021) Jaemin Cho, Jie Lei, Hao Tan, and Mohit Bansal. 2021.  Unifying vision-and-language tasks via text generation.  In _International Conference on Machine Learning_ , pages 1931–1942. PMLR.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.
  * Fan et al. (2022) Yue Fan, Winson Chen, Tongzhou Jiang, Chun Zhou, Yi Zhang, and Xin Eric Wang. 2022\.  Aerial vision-and-dialog navigation.  _arXiv preprint arXiv:2205.12219_.
  * Fu et al. (2021) Tsu-Jui Fu, Linjie Li, Zhe Gan, Kevin Lin, William Yang Wang, Lijuan Wang, and Zicheng Liu. 2021.  Violet: End-to-end video-language transformers with masked visual-token modeling.  _arXiv preprint arXiv:2111.12681_.
  * Gao et al. (2022) Xiaofeng Gao, Qiaozi Gao, Ran Gong, Kaixiang Lin, Govind Thattai, and Gaurav S Sukhatme. 2022.  Dialfred: Dialogue-enabled agents for embodied instruction following.  _arXiv preprint arXiv:2202.13330_.
  * Hahn et al. (2020) Meera Hahn, Jacob Krantz, Dhruv Batra, Devi Parikh, James Rehg, Stefan Lee, and Peter Anderson. 2020.  Where are you? localization from embodied dialog.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 806–822.
  * Hu et al. (2020) Xiaowei Hu, Xi Yin, Kevin Lin, Lijuan Wang, Lei Zhang, Jianfeng Gao, and Zicheng Liu. 2020.  Vivo: Surpassing human performance in novel object captioning with visual vocabulary pre-training.
  * Kojima et al. (2022) Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022.  Large language models are zero-shot reasoners.  _arXiv preprint arXiv:2205.11916_.
  * Kolve et al. (2017) Eric Kolve, Roozbeh Mottaghi, Winson Han, Eli VanderBilt, Luca Weihs, Alvaro Herrasti, Daniel Gordon, Yuke Zhu, Abhinav Gupta, and Ali Farhadi. 2017.  Ai2-thor: An interactive 3d environment for visual ai.  _arXiv preprint arXiv:1712.05474_.
  * Lin and Och (2004) Chin-Yew Lin and Franz Josef Och. 2004.  Automatic evaluation of machine translation quality using longest common subsequence and skip-bigram statistics.  In _Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL-04)_ , pages 605–612.
  * Lin et al. (2022) Kevin Lin, Linjie Li, Chung-Ching Lin, Faisal Ahmed, Zhe Gan, Zicheng Liu, Yumao Lu, and Lijuan Wang. 2022.  Swinbert: End-to-end transformers with sparse attention for video captioning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 17949–17958.
  * Liu et al. (2022) Ze Liu, Jia Ning, Yue Cao, Yixuan Wei, Zheng Zhang, Stephen Lin, and Han Hu. 2022\.  Video swin transformer.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 3202–3211.
  * Loshchilov and Hutter (2018) Ilya Loshchilov and Frank Hutter. 2018.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_.
  * Nguyen and Daumé III (2019) Khanh Nguyen and Hal Daumé III. 2019.  Help, anna! visual navigation with natural multimodal assistance via retrospective curiosity-encouraging imitation learning.  _arXiv preprint arXiv:1909.01871_.
  * Padmakumar et al. (2022) Aishwarya Padmakumar, Jesse Thomason, Ayush Shrivastava, Patrick Lange, Anjali Narayan-Chen, Spandana Gella, Robinson Piramuthu, Gokhan Tur, and Dilek Hakkani-Tur. 2022.  Teach: Task-driven embodied agents that chat.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pages 2017–2025.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_ , pages 311–318.
  * Roman et al. (2020) Homero Roman Roman, Yonatan Bisk, Jesse Thomason, Asli Celikyilmaz, and Jianfeng Gao. 2020.  Rmm: A recursive mental model for dialogue navigation.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 1732–1745.
  * Shi et al. (2022) Zhengxiang Shi, Yue Feng, and Aldo Lipani. 2022.  Learning to execute actions or ask clarification questions.  In _Findings of the Association for Computational Linguistics: NAACL 2022_ , pages 2060–2070.
  * Shridhar et al. (2020) Mohit Shridhar, Jesse Thomason, Daniel Gordon, Yonatan Bisk, Winson Han, Roozbeh Mottaghi, Luke Zettlemoyer, and Dieter Fox. 2020.  ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks.  In _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Thomason et al. (2020) Jesse Thomason, Michael Murray, Maya Cakmak, and Luke Zettlemoyer. 2020.  Vision-and-dialog navigation.  In _Conference on Robot Learning_ , pages 394–406. PMLR.
  * Wang et al. (2022) Jianfeng Wang, Zhengyuan Yang, Xiaowei Hu, Linjie Li, Kevin Lin, Zhe Gan, Zicheng Liu, Ce Liu, and Lijuan Wang. 2022.  Git: A generative image-to-text transformer for vision and language.  _arXiv preprint arXiv:2205.14100_.

##  Appendix A Case Study

In this section, we show a few examples of SeeRee generating responses in the
R2H task on both CVDN dataset Thomason et al. (2020) and DialFRED dataset Gao
et al. (2022). As shown in Figure 4 and Figure 5, each example includes the
input inquiry from human, the sampled input image sequence from the
environment, the response generated by SeeRee and the human response.

##  Appendix B Human Evaluation Details

In our human evaluation study, we recruited five students from the university
who consented to participate and have their data used for this work. These
participants had the same minimal prior knowledge about the project and were
given instructions on how to use the simulator before the evaluation began.

i

ii

Figure 4: Examples of the response generated by SeeRee in RDH task on CVDN
Thomason et al. (2020)

i

ii

Figure 5: Examples of the response generated by SeeRee in RDH task on DiaFRED
Gao et al. (2022)


: Deductive Verification and Scheduling Languages Join Forces

Anonymous1Anonymous Institute
Lars B. van den Haak10000-0002-0330-5016 Anton Wijs10000-0002-2071-9624 Marieke Huisman20000-0003-4467-072X
Mark van den Brand10000-0003-3529-6182

L. B. van den Haak, A.J. Wijs, M. Huisman and M.G.J. van den Brand

Eindhoven University of Technology, The Netherlands

{l.b.v.d.haak, a.j.wijs<EMAIL_ADDRESS>University of Twente, The Netherlands

§.§.§ Acknowledgements

This work is carried out in the context of the NWO TTW ChEOPS project 17249.
We want to thank Jan Martens for their discussions and feedback on this work.

[1]
Amighi, A., Haack, C., Huisman, M., Hurlin, C.: Permission-based separation
logic for multithreaded Java programs. LMCS  11(1) (2015)

[2]
Bacon, D., Graham, S., Sharp, O.: Compiler Transformations for
High-Performance Computing. ACM Computing Surveys  26(4),  345–420

[3]
Baghdadi, R., Ray, J., Romdhane, M.B., Sozzo, E.D., Akkas, A., Zhang, Y.,
Suriana, P., Kamil, S., Amarasinghe, S.P.: Tiramisu: A Polyhedral Compiler
for Expressing Fast and Portable Code. In: CGO. pp. 193–205. IEEE (2019).

[4]
Becker, N., Müller, P., Summers, A.J.: The axiom profiler: Understanding
and debugging smt quantifier instantiations. In: Tools and Algorithms for the
Construction and Analysis of Systems: 25th International Conference, TACAS
2019, Held as Part of the European Joint Conferences on Theory and Practice
of Software, ETAPS 2019, Prague, Czech Republic, April 6–11, 2019,
Proceedings, Part I 25. pp. 99–116. Springer (2019)

[5]
Blom, S., Darabi, S., Huisman, M., Oortwijn, W.: The VerCors Tool Set:
Verification of Parallel and Concurrent Software. In:
Polikarpova, N., Schneider, S. (eds.) Integr. Form. Methods. pp.
102–110. Lecture Notes in Computer Science, Springer International
Publishing, Cham (2017). 10.1007/978-3-319-66845-1_7

[6]
Bornat, R., Calcagno, C., O'Hearn, P., Parkinson, M.: Permission accounting in
separation logic. In: POPL. pp. 259–270 (2005)

[7]
Chame, C.C.J., Hall, M.: CHiLL: A framework for composing high-level loop
transformations. 08-897, University of Southern California (2008)

[8]
Chen, T., Moreau, T., Jiang, Z., Zheng, L., Yan, E., Cowan, M., Shen, H., Wang,
L., Hu, Y., Ceze, L., Guestrin, C., Krishnamurthy, A.: TVM: An
Automated End-to-End Optimizing Compiler for Deep Learning. In: 13th
USENIX Symp. Oper. Syst. Des. Implement. OSDI 18. pp.
578–594. USENIX Association, USA (2018)

[9]
Dross, C., Conchon, S., Paskevich, A.: Reasoning with Triggers. Research
Report RR-7986, INRIA (Jun 2012),

[10]
Hagedorn, B., Elliott, A.S., Barthels, H., Bodik, R., Grover, V.: Fireiron: A
Data-Movement-Aware Scheduling Language for GPUs. In: Proc. ACM
Int. Conf. Parallel Archit. Compil. Tech. pp. 71–82.
ACM, Virtual Event GA USA (Sep 2020). 10.1145/3410463.3414632

[11]
Hähnle, R., Huisman, M.: Deductive Software Verification: From
Pen-and-Paper Proofs to Industrial Tools. In: Computing and Software Science
- State of the Art and Perspectives. LNCS, vol. 10000, pp. 345–373. Springer

[12]
Hijma, P., Heldens, S., Sclocco, A., van Werkhoven, B., Bal, H.: Optimization
Techniques for GPU Programming. ACM Computing Surveys  55(11),
239:1–239:81 (2023)

[13]
Kowarschik, M., Weiß, C.: An Overview of Cache Optimization Techniques and
Cache-Aware Numerical Algorithms. In: Algorithms for Memory Hierarchies.
LNCS, vol. 2625, pp. 213–232. Springer (2003)

[14]
Leijen, D.: Division and modulus for computer scientists (July 2003),
short note about division definitions in programming languages

[15]
Leiserson, C.E., Thompson, N.C., Emer, J.S., Kuszmaul, B.C., Lampson, B.W.,
Sanchez, D., Schardl, T.B.: There’s plenty of room at the
top: What will drive computer performance after Moore’s
law? Science  368(6495) (2020). 10.1126/science.aam9744

[16]
Leroy, X.: A formally verified compiler back-end. Journal of Automated
Reasoning  43(4),  363–446 (2009)

[17]
Liu, A., Bernstein, G.L., Chlipala, A., Ragan-Kelley, J.: Verified
tensor-program optimization via high-level scheduling rewrites. Proc. ACM
Program. Lang.  6(POPL),  55:1–55:28 (Jan 2022).

[18]
Müller, P., Schwerhoff, M., Summers, A.: Viper - a verification
infrastructure for permission-based reasoning. In: VMCAI (2016)

[19]
Namjoshi, K.S., Singhania, N.: Loopy: Programmable and formally verified loop
transformations. In: International Static Analysis Symposium. pp. 383–402.
Springer (2016)

[20]
Namjoshi, K.S., Xue, A.: A Self-certifying Compilation Framework for
WebAssembly. In: International Conference on Verification, Model Checking,
and Abstract Interpretation. pp. 127–148. Springer (2021)

[21]
Newcomb, J.L., Adams, A., Johnson, S., Bodik, R., Kamil, S.: Verifying and
Improving Halide's Term Rewriting System with Program Synthesis. Proc.  ACM Program. Lang.  4(OOPSLA),  166:1–166:28 (Nov 2020).

[22]
O'Connor, L., Chen, Z., Rizkallah, C., Jackson, V., Amani, S., Klein, G.,
Murray, T., Sewell, T., Keller, G.: Cogent: Uniqueness Types and Certifying
Compilation. Journal of Functional Programming  31(e25),  1–66

[23]
de Putter, S., Wijs, A.: Verifying a verifier: on the formal correctness of an
LTS transformation verification technique. In: FASE. pp. 383–400. Springer

[24]
Ragan-Kelley, J., Adams, A., Sharlet, D., Barnes, C., Paris, S., Levoy, M.,
Amarasinghe, S., Durand, F.: Halide: Decoupling algorithms from schedules for
high-performance image processing. Commun. ACM  61(1),  106–115
(Dec 2017). 10.1145/3150211

[25]
Ragan-Kelley, J., Barnes, C., Adams, A., Paris, S., Durand, F., Amarasinghe,
S.: Halide: A Language and Compiler for Optimizing Parallelism,
Locality, and Recomputation in Image Processing Pipelines.
SIGPLAN Not.  48(6),  519–530 (Jun 2013).

[26]
Reinking, A., Bernstein, G., Ragan-Kelley, J.: Formal Semantics for the
Halide Language. Master's thesis, EECS Department, University of
California, Berkeley (2020, May)

[27]
Safari, M., Huisman, M.: Formal verification of parallel stream compaction and
summed-area table algorithms. In: International Colloquium on Theoretical
Aspects of Computing. pp. 181–199. Springer (2020)

[28]
Safari, M., Oortwijn, W., Joosten, S., Huisman, M.: Formal Verification of
Parallel Prefix Sum. In: Lee, R., Jha, S., Mavridou, A. (eds.) NASA
Form. Methods. pp. 170–186. Lecture Notes in Computer Science,
Springer International Publishing, Cham (2020).

[29]
Sakar, Ö., Safari, M., Huisman, M., Wijs, A.: Alpinist: An
Annotation-Aware GPU Program Optimizer. In: TACAS, LNCS, vol. 13244, pp.
332–352. Springer, Cham (2022). 10.1007/978-3-030-99527-0_18

[30]
Zhang, Y., Yang, M., Baghdadi, R., Kamil, S., Shun, J., Amarasinghe, S.P.:
GraphIt: a high-performance graph DSL. Proc. ACM Program. Lang.
2(OOPSLA),  1–30 (2018)


# Refined Transformation Approach for Stabilization of MIMO System by Pole
Placement

Justin Jacob<EMAIL_ADDRESS>Sreya Das<EMAIL_ADDRESS>Navin
Khaneja<EMAIL_ADDRESS>Systems and Control Engineering Department,
Indian Institute of Technology, Bombay

###### Abstract

The paper presents a distinctive and straightforward technique for
stabilization of multi-variable systems. The idea is to decouple the system
state matrix depending on different inputs and outputs. Refined special
canonical transformations are described for the design of controller and
observer for a single-input and single-output (SISO) case and are extended to
multi-input multi-output (MIMO) systems. These transformations help in the
stabilization of the error dynamics of the observer and in placing the closed
loop poles of the system. The idea is not only in the transformations taken
but also how the gain matrices are selected which simplifies the computation.

###### keywords:

controllability, cyclic subspace, Hurwitz, observability, similarity
transformation, stability, state feedback.

††journal: arXiv

##  1 Introduction

Any physical system can be expressed in the form of dynamical equations, and
these govern the characteristics of the system. Around the operating point any
non-linear system can be linearized. Stability and performance of a linear
time-invariant (LTI) system depend on the location of closed-loop poles[1] of
the system. The stabilization of a system is done with the help of controllers
where state feedback is used for placing the poles in the desired location[2].
The pole placement for MIMO systems is not as straight forward as the SISO
case and doesn’t give a unique solution. Some of the approaches mentioned in
the literature[3] include: conversion of the system to Brunovsky canonical
form [4], using Lyapnov equation to obtain the state feedback matrix without
revealing the structure of the resulting feedback system subjected to the
condition that state and feedback coefficient matrix has no common
eigenvalues[5], eigen structure method[6] for solving the Sylvester’s
equation[7], minimum number of states to obtain arbitrary pole placement by
using dynamic compensators[8], pole placement after decoupling using
Luenberger canonical form[9][10]. Recent studies mainly concentrate on
optimizing the present techniques; Pandey[11] presents an extensive comparison
of different existing algorithms. This paper approaches the stabilization
problem in a new perspective rather than going with the optimization of
conventional techniques. Our idea is to decompose the state matrix to block
triangular matrix form[12] and to apply state feedback. Here a structured way
for obtaining the similarity transformation is presented, which the classical
literature fail to establish. In most practical cases, the states are not
readily available for feedback, and we need to use a state observer. In both
the controller and observer design, we try to stabilize the model by placing
the poles in desired locations.

Assuming the LTI system is controllable and observable we define two special
canonical transformations one for the controller and other for observer
design. These similarity transformations of state matrix are refined from the
controllability and observability matrices. We derive the new augmented state
matrix in a lower triangular block matrix and upper triangular block matrix
form for controller and observer design respectively. Initially, the approach
is applied to the SISO system to get a generalized view of the components
later these generalized equations are used to the diagonal blocks of the
augmented system matrix of MIMO case. The transformations also give the
special form of input and output matrices which helps to simplify the
computations (Definition 1). Also for reducing complexity, the gain matrix
coefficients are selected in a particular way.

###### Definition 1

We define the special forms of input and output matrices that will allow us to
simplify the complexity in calculating the controller and observer gain
matrices. In this special forms each non-zero entity corresponds to the input
and output for the corresponding block of the augmented system matrix of
controller and observer, respectively.
Special input matrix from

$\widehat{B}=\begin{bmatrix}0&0&\cdots&0\\\ \vdots&\vdots&\cdots&\vdots\\\
0&0&\cdots&1\\\ \vdots&\vdots&\iddots&\vdots\\\ 0&1&\cdots&0\\\
\vdots&\vdots&\cdots&\vdots\\\ 1&0&\cdots&0\end{bmatrix}$

Special output matrix from

$\widetilde{C}=\begin{bmatrix}1&0&\cdots&0&\cdots&\cdots&0&0&\cdots&0\\\
0&\cdots&0&1&0&\cdots&\cdots&0&\cdots&0\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\ddots&\vdots&\vdots&\vdots&\vdots\\\
0&\cdots&\cdots&0&\cdots&\cdots&1&0&\cdots&0\end{bmatrix}$

This form restricts the augmented system matrix in the triangular block
structure, where each diagonal block helps to attain the form similar to the
SISO system.

###  1.1 System Model

Consider the $n^{th}$ order linear dynamic system given by the state and
output equation

$\dot{x}=A\,x+B\,u$ (1.1) $y=Cx$ (1.2)

where $x$ is $(n\times 1)$ state vector which belongs to the vector space $V$,
$u$ is $(p\times 1)$ input vector, $y$ is $(q\times 1)$ output vector, $A$ is
$(n\times n)$ state matrix, $B$ is $(n\times p)$ input matrix and $C$ is
$(q\times n)$ output matrix. An observer is used to identify the states of the
system from the information of the output of the system. Model of the observer
is given as

$\dot{z}=A\,z+B\,u+L(y-y_{m})$ (1.3) $y_{m}=C\,z$ (1.4)

where $z$ is $(n\times 1)$ observed state vector, $y_{m}$ is $(q\times 1)$
observer output vector and $L$ is $(n\times q)$ observer gain matrix. The
controller uses these states to stabilize the system using the state feedback.

Figure 1: System with observer and controller

$u=-K\,z$ (1.5)

where $K$ is $(p\times n)$ controller feedback gain matrix. Without loss of
generality, here the reference signal which is kept at zero. Assuming the
system is fully state controllable with the controllability matrix $M$, the
column vectors will span the whole space[2], $V$.

$M=\begin{bmatrix}B&AB&A^{2}B&\cdots&A^{n-2}B&A^{n-1}B\end{bmatrix}$ (1.6)

where input matrix $B=\left[b_{1}\ b_{2}\ldots b_{j}\ldots b_{p}\right]$.
Obtaining the cyclic subspaces $S_{j}$ corresponding to each input vector
$b_{j}$’s we have $S_{1}\cup S_{2}\cup\cdots\cup S_{j}\cup\cdots\cup S_{p}=V$.
The $dim(S_{j})$ gives the controllability index of the corresponding input
vector $b_{j}$. Assuming fully state observable, the observability matrix $N$,
the row vectors will span the whole space[2], $V$.

$N=\begin{bmatrix}C\\\ C\,A\\\ \vdots\\\ C\,A^{n-2}\\\
C\,A^{n-1}\end{bmatrix}$ (1.7)

where the output matrix
$C=\left[c^{T}_{1}\,c^{T}_{2}...\,c^{T}_{j}\,...c^{T}_{q}\right]^{T}$.
Obtaining the cyclic subspaces $R_{j}$ corresponding to each output vector
$c_{j}$’s we have $R_{1}\cup R_{2}\cup\cdots\cup R_{j}\cup\cdots\cup R_{q}=V$.
$dim(R_{j})$ gives the observability index of the corresponding output vector
$c_{j}$.

##  2 System Stabilization

From (1.1) and (1.3), the error dynamics $\dot{e}_{x}$ is obtained as

$\displaystyle\begin{split}\dot{e}_{x}=\dot{x}-\dot{z}=&(A-LC)\,e_{x}\\\
y-y_{m}=&C\,e_{x}\end{split}$ (2.1)

Applying (1.5) in (1.1) along with (2.1) we get the total state equation as

$\begin{bmatrix}\dot{x}\\\ \dot{e_{x}}\end{bmatrix}=\begin{bmatrix}A-BK&BK\\\
0&A-LC\end{bmatrix}\,\begin{bmatrix}x\\\ e_{x}\end{bmatrix}$ (2.2)

###### Remark 1

Any system of the form (2.2) is stable iff $A-BK$ and $A-LC$ are individually
Hurwitz.

Since (2.2) is of the block upper triangular form the characteristics equation
is only contributed by the diagonal blocks. The eigenvalues of the observer
based controller system hence are the eigenvalues of $A-BK$ and eigenvalues of
$A-LC$. Thus $K$ and $L$ are designed in a way such that $A-BK$ and $A-LC$
have stable eigenvalues. By this way, we can stabilize a linear system which
is controllable and observable.

##  3 Observer Design

###  3.1 Single Output Case

Assuming the system is fully observable, $Q$ is the linear transformation to
obtain the special canonical form of the system (1.1), where $T$ denotes the
transpose.

###### Definition 2

$Q=\begin{bmatrix}c^{T}&(c\,A)^{T}&\cdots&\cdots&(c\,{A^{n-1}})^{T}\end{bmatrix}^{T}$
(3.1)

The rows are arranged from top to bottom in the ascending powers of $A$.

The inverse exists as all the $n$ rows are linearly independent, and the
transformation used is $\widetilde{z}=Q\,z$ where
$\widetilde{z}^{T}=\begin{bmatrix}\widetilde{z}_{1}&\widetilde{z}_{2}&\cdots&\widetilde{z}_{n}\end{bmatrix}$.
The transformed system equations is

$\dot{\widetilde{z}}=Q\,A\,Q^{-1}\,\widetilde{z}+Q\,b\,u+Q\,L\,(y-y_{m})$
(3.2) $y_{m}=c\,Q^{-1}\widetilde{z}$ (3.3)

where

$\begin{split}{QAQ^{-1}=\begin{bmatrix}0&1&0&\cdots&0&0\\\ 0&0&1&\cdots&0&0\\\
\vdots&&&\ddots&&\vdots&\\\ \\\ 0&0&\cdots&\cdots&0&1\\\
-a_{1}&-a_{2}&\cdots&\cdots&-a_{n-1}&-a_{n}\end{bmatrix}}\\\ \\\
{cQ^{-1}=\begin{bmatrix}1&0&\cdots&&0&0\end{bmatrix}}\end{split}$ (3.4)

$a_{n}$, $a_{n-1}$, $\cdots$, $a_{1}$ are the coefficient of the systems
characteristic equation given by $s^{n}+a_{n}s^{n-1}+\cdots+a_{2}s+a_{1}$. The
error dynamics corresponding to (2.1) becomes
$\dot{\widetilde{e}}_{x}=[Q\,A\,Q^{-1}-Q\,L\,c\,Q^{-1}]\,\widetilde{e}_{x}$
where $\widetilde{{e}}_{x}=Q\,x-\widetilde{z}$. The transformed augmented
state transition matrix, $G=[Q\,A\,Q^{-1}-Q\,L\,c\,Q^{-1}]$ is stabilized by
$QL=\begin{bmatrix}l_{n}&l_{n-1}&\cdots&l_{1}\end{bmatrix}^{T}$.

$[sI{{-}}G]=\begin{bmatrix}s+{{l}}_{n}&{{-}}1&0&\cdots&0&0\\\
l_{n-1}&s&{{-}}1&\cdots&0&0\\\ \vdots&&\ddots&\ddots&&\vdots&\\\ \\\
l_{2}&0&\cdots&\cdots&s&{{-}}1\\\
l_{1}{{+}}a_{1}&a_{2}&\cdots&\cdots&a_{n-1}&s{{+}}a_{n}\end{bmatrix}$

To get the characteristic polynomial, the determinant of above the matrix is
taken with respect to the first column.

$\begin{split}(s&+l_{n})\left[s^{n-1}+a_{n}\,s^{n-2}+\cdots\cdots+a_{3}\,s+a_{2}\right]\\\
&+l_{n-1}\left[s^{n-2}+a_{n}\,s^{n-3}+\cdots\cdots+a_{4}\,s+a_{3}\right]\\\ &\
\vdots\\\ &+l_{2}\left[s+a_{n}\right]\\\ &+l_{1}+a_{1}\end{split}$ (3.5)

whose general form is

$\rho(s)+\sum_{j=2}^{n}l_{j}\left(\sum_{i=1}^{j}s^{j-i}\,a_{n+2-i}\right)+l_{1}$
(3.6)

where $a_{n+1}=1$ and $\rho(s)$ is the characteristic polynomial of the
original system. The coefficient of $s^{n-1}$ is a function of $l_{n}$ and
$a_{n}$, where $a_{n}$ is the system coefficient and from the knowledge of the
required eigenvalue to stabilize the error dynamics, we can obtain the value
of $l_{n}$. All the constant terms are compared to the desired characteristic
equation $s^{n}+\alpha_{n}\,s^{n-1}+\cdots\cdots+\alpha_{2}\,s+\alpha_{1}$

$\displaystyle s^{n-1}\Rightarrow$ $\displaystyle\alpha_{n}\Longrightarrow
l_{n}+a_{n}$ (3.7) $\displaystyle s^{n-2}\Rightarrow$
$\displaystyle\alpha_{n-1}\Longrightarrow l_{n-1}+l_{n}\,a_{n}+a_{n-1}$
$\displaystyle\vdots$ $\displaystyle s^{1}\Rightarrow$
$\displaystyle\alpha_{2}\Longrightarrow
l_{2}+l_{3}\,a_{n}+\cdots+l_{n}\,a_{3}+a_{2}$ $\displaystyle s^{0}\Rightarrow$
$\displaystyle\alpha_{1}\Longrightarrow
l_{1}+l_{2}\,a_{n}+\cdots+l_{n}\,a_{2}+a_{1}$

The generalized coefficient of the augmented characteristic polynomial is

$\alpha_{i}=\sum_{j=i}^{n+1}l_{j}\,a_{n+1+i-j}$ (3.8)

where $a_{n+1}=l_{n+1}=1$ and $\alpha_{i}$ are the desired coefficient for
stabilizing observer error dynamics.

###  3.2 Multiple Output Case

System (1.2) with $q$ outputs has the output matrix
$C=\left[c^{T}_{1}\,c^{T}_{2}...\,c^{T}_{j}\,...c^{T}_{q}\right]^{T}$.

###### Definition 3

Refined transformation matrix $Q$ is obtained from the corresponding basis of
the constrained cyclic subspaces, $U_{j}$ generated by $c_{j}$.

$\displaystyle
Q=[\,{c_{1}}^{T}\cdots({c_{1}}{A^{m_{1}-1}})^{T}|\cdots\,|\,{c_{j}}^{T}\cdots({c_{j}}{A^{m_{j}-1}})^{T}\,|$
(3.9)
$\displaystyle\cdots|{c_{k}}^{T}\,\cdots\,({c_{k}}{A^{m_{k}-1}})^{T}\,]^{T}$

Here the subspaces are subjected to the condition where the total space
$V=U_{1}\oplus U_{2}\oplus\cdots\oplus U_{j}\oplus\cdots\oplus U_{k}$, $k\leq
q$ where $dim(U_{j})=m_{j}$ and $\sum_{j=1}^{k}m_{j}=dim(V)=n$. The
arrangement is similar to Definition 2.

$Q$ transforms the system matrix to block upper triangular matrix and the
output matrix to the special canonical form in Definition 1.

$\begin{split}{QAQ^{-1}=\begin{bmatrix}\widetilde{A}_{1}&\bigstar&\bigstar&\cdots&\bigstar\\\
0&\widetilde{A}_{2}&\bigstar&\cdots&\bigstar\\\
\vdots&\vdots&\widetilde{A}_{j}&\cdots&\vdots\\\
\vdots&\vdots&\vdots&\ddots&\bigstar\\\
0&0&0&\cdots&\widetilde{A}_{k}\end{bmatrix}}\\\ \\\
{CQ^{-1}=\begin{bmatrix}\widetilde{C}_{1}&0&\cdots&0\\\
0&\widetilde{C}_{2}&\cdots&0\\\ \vdots&\vdots&\widetilde{C}_{j}&\vdots\\\
0&0&\cdots&0\\\ 0&0&\cdots&\widetilde{C}_{k}\end{bmatrix}}\end{split}$ (3.10)

where $\widetilde{A}_{j}$ is $(m_{j}\times m_{j})$ and $\widetilde{C}_{j}$ is
$(1\times m_{j})$ matrices which corresponds to the form (3.4). $\bigstar$
denotes $\widetilde{A}_{ij}$ and has a dimension of $m_{i}\times m_{j}$, which
does not involves in the calculation.

###### Definition 4

$\widetilde{L}$ to stabilize the error dynamics has $m_{j}$ number of non zero
coefficients in each column corresponding to $c_{j}$ in the $Q$ matrix.

$\widetilde{L}=\begin{bmatrix}l^{1}_{m_{1}}&0&\cdots&\cdots&0\\\
\vdots&\vdots&&\vdots&\vdots\\\ l_{1}^{1}&0&\cdots&\cdots&\vdots\\\
0&l_{m_{j}}^{j}&\ddots&\cdots&\vdots\\\ \vdots&\vdots&&\vdots&\vdots\\\
0&l_{1}^{j}&\ddots&\cdots&\vdots\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\ddots&\cdots&l_{m_{k}}^{k}\\\ \vdots&\vdots&&\vdots&\vdots\\\
0&0&\cdots&\cdots&l_{1}^{k}\end{bmatrix}$ (3.11)

If the $Q$ matrix has used only $k$ output vector from $C$ matrix, where $k<q$
then, $q-k$ columns of the $\widetilde{L}$ matrix all takes zeros as it has
dimension $(n\times q)$. The choice of $\widetilde{L}$ will preserve the block
upper triangular form in the augmented system matrix
$\widetilde{A}-\widetilde{L}\widetilde{C}$, where $\widetilde{A}=QAQ^{-1}$,
$\widetilde{C}=CQ^{-1}$ and $\widetilde{L}=QL$.

The characteristic matrix
$\left[sI-\left(\widetilde{A}-\widetilde{L}\widetilde{C}\right)\right]$ has
each diagonal block similar to the single output case.
$det(sI-\widetilde{A}+\widetilde{L}\widetilde{C})$ is obtained from the
product of diagonal blocks. Note for the untransformed system the observer
gain $L=Q^{-1}\widetilde{L}$.

$\left|(sI_{m_{1}}-\widetilde{A}_{1})\right|*\cdots*\left|(sI_{m_{j}}-\widetilde{A}_{j})\right|*\cdots*\left|(sI_{m_{k}}-\widetilde{A}_{k})\right|$
(3.12)

Each block has an order $m_{j}$ and can be separately evaluated as a single
output case discussed in the previous section 3.1. The desired values of the
poles say ($\gamma_{1},\gamma_{2},\cdots,\gamma_{n}$), to eliminate the error,
as quickly as possible, is placed with the help of each block. $j^{th}$ block
helps in placing $m_{j}$ poles.

##  4 Controller Design

###  4.1 Single Input Case

Assuming the system is fully controllable, we take $P$ as the linear
transformation to obtain the special canonical form for the system (1.1).

###### Definition 5

$P=\begin{bmatrix}A^{n-1}\,B&A^{n-2}\,B&\cdots&\cdots&A\,B&B\end{bmatrix}$
(4.1)

The columns are arranged from left to right in the ascending powers of $A$.

Since $P$ has $n$ linearly independent columns, it has a rank $n$, and its
range is the whole space[2] $V$. The transformed state,
$\widehat{x}=P^{-1}\,x$, where
$\widehat{x}^{T}=\begin{bmatrix}\widehat{x}_{1}&\widehat{x}_{2}&\cdots&\widehat{x}_{n}\end{bmatrix}$,
and the transformed system equation is

$\dot{\widehat{x}}=P^{-1}\,A\,P\,\widehat{x}+P^{-1}\,B\,u$ (4.2)

where,

$\begin{split}{P^{-1}\,A\,P=\begin{bmatrix}-a_{n}&1&0&\cdots&0&0\\\
-a_{n-1}&0&1&\cdots&0&0\\\ \vdots&&&\ddots&&\vdots&\\\ \\\
-a_{2}&0&\cdots&\cdots&0&1\\\ -a_{1}&0&\cdots&\cdots&0&0\end{bmatrix}}\\\ \\\
{P^{-1}\,B=\begin{bmatrix}0\\\ 0\\\ \vdots\\\ \\\ 0\\\
1\end{bmatrix}}\end{split}$ (4.3)

$a_{n}$, $a_{n-1}$, $\cdots$, $a_{1}$ are the coefficient of the systems
characteristic equation. Using the estimated state vector $z$, the feedback
law used is $u=-K\,z$, where
$K=\begin{bmatrix}k_{1}&k_{2}&\cdots&k_{n}\end{bmatrix}$. After transformation
two terms obtained in the system equation, are $\widehat{x}$ and
$\widehat{e}_{z}=\widehat{x}-\widehat{z}$, where $\widehat{z}=P^{-1}z$. The
total system dynamics is given by

$\begin{bmatrix}\dot{\widehat{x}}\\\
\dot{\widehat{e}_{x}}\end{bmatrix}=\begin{bmatrix}\widehat{A}-\widehat{B}\widehat{K}&\widehat{B}\widehat{K}\\\
0&P^{-1}(A-LC)P\end{bmatrix}\,\begin{bmatrix}\widehat{x}\\\
\widehat{e}_{x}\end{bmatrix}$ (4.4)

where $\widehat{A}=P^{-1}AP$, $\widehat{B}=P^{-1}B$ and $\widehat{K}=KP$.
Since the lower block of (2.2) and (4.4) are similar, we need to consider only
the first block of the total system as we have already taken care of the lower
part in the observer design. So the augmented state transition matrix required
is $F=[\widehat{A}-\widehat{B}\widehat{K}]$ where
$\widehat{K}=\begin{bmatrix}\widehat{k}_{1}&\widehat{k}_{2}&\cdots&\widehat{k}_{n}\end{bmatrix}$.
Now the characteristic polynomial is obtained and has a form similar to (3.5)
where $a_{j}$ is in place of $l_{j}$ and $\widehat{k}_{j}$ in place of
$a_{j}$. We use the same (3.6) with the corresponding changes, where
$\widehat{k}_{n+1}=1$. Let {$\lambda_{1},\lambda_{2},\cdots,\lambda_{n}$} is
the desired set of poles of the system and say the desired characteristic
polynomial to be
$s^{n}+\beta_{n}\,s^{n-1}+\cdots\cdots+\beta_{2}\,s+\beta_{1}$. The general
coefficient form is

$\beta_{i}=\sum_{j=i}^{n+1}a_{j}\,\widehat{k}_{n+1+i-j}$ (4.5)

where $a_{n+1}=\widehat{k}_{n+1}=1$. Coefficients $\widehat{k}_{j}$ are
obtained similar to the observer case and these stabilizes the closed loop
system.

###  4.2 Multiple Input Case

System (1.1) with $p$ inputs has the input matrix $B=\left[b_{1}\ b_{2}\ldots
b_{j}\ldots b_{p}\right]$.

###### Definition 6

Refined transformation matrix $P$ is obtained from the corresponding basis of
the constrained cyclic subspaces ($W_{j}$) generated by $b_{j}$.

$\displaystyle P=[A^{n_{k}-1}b_{k}\,\cdots
b_{k}|\cdots|\,A^{n_{j}-1}b_{j}\cdots b_{j}\,|$ (4.6)
$\displaystyle\cdots|\,A^{n_{1}-1}b_{1}\cdots b_{1}]$

Here the subspaces are subjected to the condition where the total space
$V=W_{1}\oplus W_{2}\oplus\cdots\oplus W_{j}\oplus\cdots\oplus W_{k}$, $k\leq
p$ where $dim(W_{j})=n_{j}$ and $\sum_{j=1}^{k}n_{j}=dim(V)=n$. The
arrangement is similar to Definition 5.

$P$ transforms the system matrix to block lower triangular matrix and the
input matrix to the special canonical form in Definition 1.

$\begin{split}{P^{-1}AP=\begin{bmatrix}\widehat{A}_{k}&0&0&\cdots&0\\\
\star&\widehat{A}_{k-1}&0&\cdots&0\\\
\vdots&\ddots&\widehat{A}_{j}&\cdots&\vdots\\\
\vdots&\vdots&\ddots&\ddots&\vdots\\\
\star&\star&\star&\cdots&\widehat{A}_{1}\end{bmatrix}}\\\ \\\
{P^{-1}\,B=\begin{bmatrix}0&0&\cdots&\widehat{B}_{k}\\\ 0&0&\cdots&0\\\
\vdots&\vdots&\widehat{B}_{j}&\vdots\\\ 0&\widehat{B}_{2}&\cdots&0\\\
\widehat{B}_{1}&0&\cdots&0\end{bmatrix}}\end{split}$ (4.7)

where $\widehat{A}_{j}$ is $(n_{j}\times n_{j})$ and $\widehat{B}_{j}$ is
$(n_{j}\times 1)$ matrices which correspond to the form (4.3). $\star$ denotes
$\widehat{A}_{ij}$ and has a dimension of $n_{i}\times n_{j}$, which does not
involve in the calculation.

###### Definition 7

$\widehat{K}$ which places the closed loop poles has $n_{j}$ number of non
zero coefficients in each rows corresponding to $b_{j}$ in the $P$ matrix.

$\widehat{K}=\begin{bmatrix}0&\cdots&0&0&\cdots&0&\widehat{k}_{1}^{1}&\cdots&\widehat{k}_{n_{1}}^{1}\\\
0&\cdots&0&\widehat{k}_{1}^{j}&\cdots&\widehat{k}_{n_{j}}^{j}&0&\cdots&0\\\
\vdots&\cdots&\vdots&\vdots&\cdots&\vdots&\vdots&\cdots&\vdots\\\
\widehat{k}_{1}^{k}&\cdots&\widehat{k}_{n_{k}}^{k}&0&\cdots&0&\cdots&\cdots&0\end{bmatrix}$
(4.8)

The choice of $\widehat{K}$ will preserve the block lower triangular form in
the augmented system matrix $[\widehat{A}-\widehat{B}\widehat{K}]$. The
characteristic matrix
$\left[sI-\left(\widehat{A}-\widehat{B}\widehat{K}\right)\right]$ has each
diagonal block similar to the single input case. The
$det(sI-\widehat{A}+\widehat{B}\widehat{K})$ is obtained from the product of
diagonal blocks. Note for the untransformed system the feedback gain
$K=\widehat{K}P^{-1}$ . The desired values of the closed loop poles to
stabilize the system can be placed by each block individually, similar to
single input case. $L$ and $K$ stabilizes the system (2.2).

In order to have a faster response, the poles of the observer can be taken
more negative w.r.t the controller. It may be noted that the column vectors of
input and row vectors of output matrix can be taken in any sequential order
and there will be a corresponding change in the transformation. Nevertheless,
the forms obtained for the system matrices will follow the defined ones.

##  5 Conclusions

This paper presents a simple and straight forward approach towards the
stabilization of linear time-invariant MIMO systems. Although the
controllability and observability transformation approach are widely used, the
refined transformation approach simplifies the problem prominently. The
defined similarity transformations help to obtain the special canonical forms
of the input and output matrix (Definition 1). This transformation transforms
the state matrix to the block triangular form, which enables to obtain similar
characteristic polynomial for controller and observer case. Besides, the
controller and observer gain matrices are defined in such a way that reduces
the computational complexity in calculating the gain matrix coefficients. The
characteristic polynomial for MIMO case corresponds to the product of the
diagonal blocks in the augmented state matrix which resembles the SISO case.
The significant achievement is that it follows a similar equation which
satisfies for both observer and controller design. It must be noted that if
input order is changed, a new input matrix corresponding to the change is
obtained. This changes the special transformation matrix and enables us to use
different inputs to control the system so that the designer can optimize the
use of control effort corresponding to different inputs. The same can be done
in the case for observer design with rearranging the output.

## References

  * [1] J. H. Mulligan, The effect of pole and zero locations on the transient response of linear dynamic systems, Proceedings of the IRE 37 (5) (1949) 516–529.  doi:10.1109/JRPROC.1949.232649.
  * [2] R. Kalman, On the general theory of control systems, IFAC Proceedings Volumes 1 (1) (1960) 491 – 502, 1st International IFAC Congress on Automatic and Remote Control, Moscow, USSR, 1960.  doi:https://doi.org/10.1016/S1474-6670(17)70094-8.
  * [3] E. Davison, W. Wonham, On pole assignment in multivariable linear systems, IEEE Transactions on Automatic Control 13 (6) (1968) 747–748.  doi:10.1109/TAC.1968.1099056.
  * [4] J. A. Hermida-Alonso, M. P. Perez, T. Sanchez-Giralda, Brunovsky’s canonical form for linear dynamical systems over commutative rings, Linear Algebra and its applications 233 (1996) 131–147.
  * [5] C.-T. Chen, Linear system theory and design (1999).
  * [6] P. Van Dooren, The generalized eigenstructure problem in linear system theory, IEEE Transactions on Automatic Control 26 (1) (1981) 111–129.  doi:10.1109/TAC.1981.1102559.
  * [7] S. Bhattacharyya, E. de Souza, Pole assignment via sylvester’s equation, Systems & Control Letters 1 (4) (1982) 261 – 263.  doi:https://doi.org/10.1016/S0167-6911(82)80009-1.
  * [8] F. Brasch, J. Pearson, Pole placement using dynamic compensators, IEEE Transactions on Automatic Control 15 (1) (1970) 34–43.  doi:10.1109/TAC.1970.1099352.
  * [9] P. K. Kar, J. D. Aplevich, N. J. Bergman, Decouplable multivariable systems: canonical forms and pole assignment, Electrical Engineers, Proceedings of the Institution of 120 (11) (1973) 1433–1438.  doi:10.1049/piee.1973.0291.
  * [10] M. Valasek, N. Olgac, Generalization of ackermann’s formula for linear mimo time invariant and time varying systems, in: Proceedings of 32nd IEEE Conference on Decision and Control, 1993, pp. 827–832 vol.1.  doi:10.1109/CDC.1993.325034.
  * [11] A. Pandey, R. Schmid, T. Nguyen, Y. Yang, V. Sima, A. L. Tits, Performance survey of robust pole placement methods, in: 53rd IEEE Conference on Decision and Control, 2014, pp. 3186–3191.  doi:10.1109/CDC.2014.7039881.
  * [12] W. Wonham, On pole assignment in multi-input controllable linear systems, IEEE Transactions on Automatic Control 12 (6) (1967) 660–665.  doi:10.1109/TAC.1967.1098739.