11institutetext: School of Computing and Mathematics, Charles Sturt University
Bathurst, NSW 2795, Australia.
11email<EMAIL_ADDRESS>
Authors’ Instructions

# Signal Classification using Smooth Coefficients of Multiple Wavelets to
Achieve High Accuracy from Compressed Representation of Signal

Paul Grant${}^{\textrm{(\Letter)}}$ Md Zahidul Islam

###### Abstract

Classification of time series signals has become an important construct and
has many practical applications. With existing classifiers we may be able to
accurately classify signals, however that accuracy may decline if using a
reduced number of attributes. Transforming the data then undertaking reduction
in dimensionality may improve the quality of the data analysis, decrease time
required for classification and simplify models. We propose an approach, which
chooses suitable wavelets to transform the data, then combines the output from
these transforms to construct a dataset to then apply ensemble classifiers to.
We demonstrate this on different data sets, across different classifiers and
use differing evaluation methods. Our experimental results demonstrate the
effectiveness of the proposed technique, compared to the approaches that use
either raw signal data or a single wavelet transform.

###### Keywords:

Signal Classification, Energy Distribution, Wavelets, Ensembles

##  1 Introduction

In this paper which we build upon our previous work [1] where an approach
using multi-wavelet decomposition to build a set of attributes composed of
wavelet coefficients derived from different wavelet filters to enable noisy
signal classification. Here present a method which first determines a manner
to select suitable wavelets, then implements and combines these selected
wavelets to not only transform but reduce the dimension of the data and yet
still maintain or improve upon classification accuracy when using decision
trees as our classifier.

Use of decision tree induction for classification has become a common approach
in machine learning. Decision trees attempt to allot symbolic decisions to new
samples and provide a visual representation of the derived rule set. Automatic
rule induction systems for inducing classification rules have already proved
valuable as tools for assisting in knowledge acquisition for expert systems
[2]. Classification is a methodology that determines categories within a
collection of data, which then allows the analysis of large data sets. If we
use labeled datasets to train algorithms that classify the data it is
considered an instance of supervised learning.

In most research, a signal is related to the main topic of interest. Here we
apply wavelet transforms to that signal. We utilise the smooth components from
multiple wavelets to provide the attributes used for the classification
process. We demonstrate Classification across 3 different sets of signals111We
designate these signals as raw or unmodified Data., where we apply classifiers
to both raw and transformed signals. We show that accuracy may be improved or
even maintained with reduced elements in the attribute space by using
wavelets, and even further enhanced by multiple wavelet transformed data
combined with ensemble of trees classifiers.

Wavelet coefficients in preference to raw data has been previously mentioned
[3], where a single wavelet filter was used. Using wavelet transformed data to
select various frequency levels within the signal, enabling reduction or
elimination of specific inherent frequencies (and noise), to then undertake
classification has proved successful [4]. Wavelets may be used to reduce
noise222Noise here includes missing or misclassification of values as well as
other induced random fluctuations in the data. in time series data, with the
aim to provide better classification performance which may be achieved after
conducting a wavelet transform on the original data, also compression using
wavelets speeds up the classification process [5]. Multiple Wavelets have been
previously used [6, 1] and applied to noise reduction as well as Image and ECG
data compression. However finding a close to optimal wavelet filter (or
filters) to use which provides a close to best representation the underlying
data, is not a trivial task.

##  2 Wavelets

Wavelets are linear transforms see Definition 2.1, that can be used to segment
the data into separate non overlapping bandwidths. They have advantages where
the signal has discontinuities and sharp spikes. Wavelets have been applied in
various areas such as image compression, turbulence, human vision, radar and
digital signal processing [7]. A wavelet transform is the representation of a
function by wavelet coefficients.

###### Definition 2.1

Linear Transform

A linear transformation is a transformation $T:R^{n}\rightarrow R^{m}$
satisfying

$\displaystyle T(u+v)$ $\displaystyle=$ $\displaystyle T(u)+T(v)$
$\displaystyle T(cu)$ $\displaystyle=$ $\displaystyle cT(u)$

for all vectors $u,v$ in $R^{n}$ and all scalars $c$.

If we sample a wavelet discretely and apply that resulting filter applied to
our raw data then we have a Discrete Wavelet Transform, (DWT). The DWT allows
us to analyse (decompose) a time series into coefficients W, from which we may
synthesise (reconstruct) our original series [8]. The DWT in principle
provides more information than the time series raw data points in
classification because the DWT locates where the signal energies are
concentrated in the frequency domain [3]. We provide an overview of the DWT
and the Multiple Discrete Wavelet transform (MDWT), adapted from [1].

####  2.0.1 DWT

Let a sequence $X_{1},X_{2},\ldots,X_{n}$ represent a time series of $n$
elements, denoted as $\\{X_{t}:t=1,\ldots,n\\}$ where $n=2^{J}$ :
$J\in\mathbb{Z^{+}},\;X_{t}\in\mathbb{R}$, the discrete wavelet transform is a
linear transform which decomposes $X_{t}$ into $J$ levels giving $n$ DWT
coefficients; the wavelet coefficients are obtained by premultiplying $X$ by
$\mathcal{W}$.

$\textbf{W}=\mathcal{W}X$ (1)

  * •

W is a vector of DWT coefficients ($j$th component is $W_{j}$)

  * •

$\mathcal{W}$ is $n\times n$ orthonormal transform matrix; i.e.,
$\mathcal{W}^{T}\mathcal{W}=I_{n}$, where $I_{n}$ is $n\times n$ identity
matrix

  * •

inverse of $\mathcal{W}$ is its transpose,
$\implies\mathcal{W}\mathcal{W}^{T}=I_{n}$
$\therefore\mathcal{W}^{T}$W = $\mathcal{W}^{T}\mathcal{W}X=X$

W is partitioned into $J+1$ subvectors

$\textbf{W}=[\textbf{W}_{1},\textbf{W}_{2},\ldots,\textbf{W}_{j},\ldots,\textbf{W}_{J},\textbf{V}_{J}]$
(2)

  * •

$\textbf{W}_{j}$ has $n/2^{j}$ elements 333 note:
$\sum^{J}_{j=1}\frac{n}{2^{j}}=\frac{n}{2}+\frac{n}{4}+\dots+2+1=2^{J}-1=n-1$

  * •

$\textbf{V}_{J}$ has one element 444If we decompose $X_{t}:n=2^{J}$, to level
$Jo:1\leq J_{0}\leq J$ then $\textbf{V}_{Jo}$ has $n/2^{Jo}$ elements

conversely the synthesis equation for the DWT is:

$X=\mathcal{W}^{T}\textbf{W}=\left[\mathcal{W}^{T}_{1},\mathcal{W}^{T}_{2},\ldots,\mathcal{W}^{T}_{J},\mathcal{V}^{T}_{J}\right]\left[\begin{tabular}[]{c}$\textbf{W}_{1}$\\\
$\textbf{W}_{2}$\\\ {\scriptsize$\vdots$}\\\ $\textbf{W}_{J}$\\\
$\textbf{V}_{J}$\\\ \end{tabular}\right]$ (3)

Equation 3 leads to additive decomposition which expresses $X$ as the sum of
$J+1$ vectors, each of which is associated with a particular scale
$\mathcal{T}_{j}$

$X=\sum^{J}_{j=1}\mathcal{W}^{T}_{j}\textbf{W}_{j}+\mathcal{V}^{T}_{J}\textbf{V}_{J}\equiv\sum^{J}_{j=1}\mathcal{D}_{j}+\mathcal{S}_{J}$
(4)

  * •

$\mathcal{D}_{j}\equiv\mathcal{W}^{T}_{j}\textbf{W}_{j}$ is portion of
synthesis due to scale $\mathcal{T}_{j}$, called the jth ’detail’

  * •

$\mathcal{S}_{J}\equiv\,\mathcal{V}^{T}_{J}\textbf{V}_{j}$ is a vector called
the ’smooth’ of the $J$th order [8].

###### Remark 1

If we use the DWT to only decompose $X_{t}$ to the first level, then from
Equation 4 the transformed signal consists of $\frac{n}{2}$ detail
coefficients and $\frac{n}{2}$ smooth coefficients. Similarly, decomposition
to second level, $\frac{3n}{4}$ detail coefficients and $\frac{n}{4}$ smooth
coefficients. (provided signal length n, is a factor of 2 or 4 respectively.)

###  2.1 MDWT

To construct a Multiple Discrete Wavelet Transform from a time series
$\\{X_{t}:t=1,\ldots,n\\}$ we use the DWT to deconstruct the signal to level
$J_{0}$ : $J_{0}\in\mathbb{Z^{+}},\;X_{t}\in\mathbb{R}$, choose $N$ different
DWT filters and apply to $X_{t}$ sequentially. From Equation 4 this results
in:

$\sum^{N}_{i=1}\left[\sum^{J_{0}}_{j=1}\mathcal{D}_{ij}+\mathcal{S}_{iJ_{0}}\right]$
(5)

giving a sequence of vectors, where each $\text{DWT}_{i}$ is
$\mathcal{D}_{i1},\mathcal{D}_{i2},\dots,\mathcal{D}_{iJ_{0}},\;\mathcal{S}_{iJ_{0}}$
(which consists of the wavelet coefficients resulting from level $Jo$
decomposition). If we choose only the smooth coefficients
$s_{i,k}\in\mathcal{S}_{iJ_{0}}:1\leq k\leq\frac{n}{2^{J_{0}}}$ then

$\textit{MDWT}=s_{1,1},s_{1,2},\dots,s_{1,\frac{n}{2^{Jo}}},s_{2,1},s_{2,2},\dots,s_{2,\frac{n}{2^{Jo}}},\ldots,s_{N,1},s_{N,2},\dots,s_{N,\frac{n}{2^{J_{0}}}}$
(6)

###### Remark 2

This has $\frac{N}{2^{J_{0}}}$ times as many elements as in $X_{t}$.

###  2.2 Energy distribution

If we define the energy with a signal $X_{t}$ as the squared norm $||X||^{2}$,
see Definition 2.2, then may derive the energy distribution in the signal via
a normalised partial energy sequence; $\mathbf{NPES}$ [8].

For a signal $\\{X_{t}:t=0,\dots,n-1\\}$ if we reorder by magnitude then,

$|x_{(0)}|\geq|x_{(1)}|\geq\dots\geq|x_{(n-1)}|.$

This enables us to compute the NPES555Which permits construction of a plot of
cumulative energy% in the signal (or representation of), against the number of
data points, see Figure 2. , : $\;n-1\geq M-1$

$C_{M-1}\equiv\frac{\sum^{M-1}_{j=0}|x_{(j)}|^{2}}{\sum^{n-1}_{j=0}|x_{(j)}|^{2}}=\frac{\text{energy
in largest M terms}}{\text{total energy in signal}}$ (7)

and similarly for a NPES of wavelet666As the DWT is an orthonormal transform,
the energy in the transform (consisting of all $J+1$ subvectors) equates to
the energy in the signal. coefficients.

###### Definition 2.2

Vector Norm

Given an $n$-dimensional vector $X=x_{1},x_{2},\dots,x_{n}$

The vector norm $||X||^{p}$ for $p=1,2,\ldots$ is defined as

$||X||^{p}\equiv\left\\{\sum_{i}|x_{i}|^{p}\right\\}^{1/p}$

##  3 Our Technique

We present a method,“Multi-Wavelet Compression Signal Classification”,
(MWCSC) which utilises wavelet transforms of the signal data, First we
introduce the ideology of the main concepts followed by the advantages
provided, then provide a succinct overview of the steps required to implement
our technique.

$\bullet$ From the dataset used, we consider the different classes within the
signal data. Using wavelet transforms of these classes, we map the
distribution of the original signal energy/information against the
corresponding representation provided by the wavelet coefficients. We use the
NPES, see section 2.2, to select a group of suitable wavelet filters to
transform our data. NPES is an existing methodology that enables us to choose
wavelets that may better represent the distribution of energy in the signal.
We utilise the NPES with the aim providing the a sparse representation of the
original data, i.e. many coefficients have low values.

$\bullet$ From multiple wavelets we construct a Multiple Discrete Wavelet
transform, (MDWT, see section 2.1). The rationale for using multiple wavelets
in the transform is, we may include wavelets that are either symmetric, have
short support, provide higher accuracy and are orthogonal. No single wavelet
may provide all such properties simultaneously [9].

The MDWT provides the wavelet coefficients used to form the attributes on
which the classification methods derive their rule set from. For a transform
consisting of a single wavelet we obtain the same number of data points (here
wavelet coefficients) as provided in the original signal. However as we only
choose the smooth wavelet coefficients $S_{J}$, see Equation 4, we may reduce
the number of coefficients used to form the attributes for classification.

$\bullet$ At the first level of wavelet decomposition, the MDWT consisting of
$N$ wavelets (smooth coefficients only at $J=1$), then from Equation 5 we
would have have $\frac{N}{2}$ times the number of original data points, which
could be considered as attributes. Similarly at the second level of
decomposition, MDWT consisting of $N$ wavelets contains $\frac{N}{4}$ time the
number of original data points.

Similarly by reducing the overall number of attributes we may speed up the
classification process [5]. Our method enables us reduce the overall number of
attributes yet still maintain or even improve classification accuracy. For
evaluation of classification we utilise a different method for each dataset
chosen, to highlight the results of this approach regardless of the manner
used for grading the results.

###  3.1 Advantages

Our methodology does require some additional computation, however

  * $\bullet$

The NPES identifies suitable wavelets to use,

  * $\bullet$

By using only smooth coefficients from the wavelet transform, it is possible
reduce the number of attributes for the classifiers

  * $\bullet$

Using multiple wavelets increases accuracy

While the construction of the MDWT is not a complicated procedure, the results
returned via the MDWT constructed using only the smooth coefficients highlight
that the extra computation is worthwhile, providing us with similar levels of
accuracy yet reducing number of attributes.

We are providing a set of attributes for the classifiers where a considerable
amount of energy in the signal is then concentrated into a smaller of number
of components. The classification methods combined with MDWT tend to return
smaller sets of decision rules (or smaller less complex trees) to arrive at
their final rule set[1]. Using our MDWT compared to a single wavelet
transform, in Sections 4.2 to 4.4 the gain in classification accuracy when
used with single decision tree methods and even more so when used with
ensemble classification methods, is apparent . The software used in
construction and application is freely available on-line together : R [10],
the R package WMTSA [11] and WEKA [12].

###  3.2 Steps in the Proposed Technique: MWCSC

  * Step 1 Wavelet Selection.

  * From a set of Time series

$\\{X_{t_{i}}:t=1,\ldots,n,\,i=1,\ldots,K\\}$

  * which has a distinct number of classes, compare the energy distribution of each of the signal classes as represented by varied wavelet transforms, using the NPES described in section 2.2.

Step 2 Discrete Wavelet Transforms

  * For each single time series $X_{t_{i}}$ take the DWT of the signal using a different wavelet filter (as determined by the NPES in Step 1) for each of the transforms and extract the wavelet smooth coefficients $\mathcal{S}_{J_{0}}$.

Step 3 DataSet Construction via MDWT

  * 3a. Construct a new data series, (MDWT, see section 2.1) placing each of the individual vectors of the wavelet smooth coefficients (resulting from each DWT, with level of decomposition = $J_{0}$) in a continuous sequence, one after each other, see equation 6.

  * 3b. For each each of these MDWT, stack each transformed signal, to form a data array or matrix as depicted in Table 1.

Table 1:  Array of transformed data as developed by MDWT

MDWT($X_{t_{1}}$): |  $s_{1,1_{1}}$, |  $s_{1,2_{1}}$, | …, |  $s_{1,\frac{n}{2^{J_{0}}}_{1}}$, |  $s_{2,1_{1}}$, | …, |  $s_{2,\frac{n}{2^{J_{0}}}_{1}}$, | …, |  $s_{N,1_{1}}$, | …, | $s_{N,\frac{n}{2^{J_{0}}}_{1}}$
---|---|---|---|---|---|---|---|---|---|---|---
MDWT($X_{t_{2}}$): |  $s_{1,1_{2}}$, |  $s_{1,2_{2}}$, | …, |  $s_{1,\frac{n}{2^{J_{0}}}_{2}}$, |  $s_{2,1_{2}}$, | …, |  $s_{2,\frac{n}{2J_{0}}_{2}}$, | …, |  $s_{N,1_{2}}$, | …, | $s_{N,\frac{n}{2^{J_{0}}}_{2}}$
|  |  | $\vdots$ |  |  | $\vdots$ |  | $\vdots$ |  | $\vdots$ |
MDWT($X_{t_{K}}$): |  $s_{1,1_{K}}$, |  $s_{1,2_{K}}$, | …, |  $s_{1,\frac{n}{2^{J_{0}}}_{K}}$, |  $s_{2,1_{K}}$, | …, |  $s_{2,\frac{n}{2^{J_{0}}}_{K}}$, | …, |  $s_{N,1_{K}}$, | …, | $s_{N,\frac{n}{2^{J_{0}}}_{K}}$

Step 4 Build a classifier

  * Using the new data as generated in previous steps, apply ensemble classifiers.777We also applied single Decision tree classifiers to the MDWT data to as a baseline to compare with ensemble classifiers. to the transformed data.

##  4 Experimental Results

The data used was sourced from the UCR time series archive [13]. Here we
simply chose three data sets, each of different length and number of records,
see Table 2. These data sets exhibit widely different levels of
smoothness888Smoothness defined here as: standard deviation of the of first
differences of a time series elements. ie. standard deviation of ($X_{S}$) :
$X_{S}=x_{1}-x_{2},x_{2}-x_{3},\ldots,x_{n-1}-x_{n}$ when compared to each
other. We also use 5 Tree based classifiers from WEKA.

###  4.1 Classification methods used

We utilise the following classifiers999 For the Ensemble Classifiers*
throughout our experiment we set number of trees used to 100, no fine tuning
of parameters was undertaken..

  * $\bullet$

J48 a decision tree is an extension of ID3. Some additional features of J48;
accounting for missing values, decision trees pruning, continuous attribute
value ranges and derivation of rules [14].

  * $\bullet$

Random Forest* Class for constructing a forest of random trees.[15].

  * $\bullet$

ForestPA* Decision forest algorithm Forest PA, using bootstrap samples and
penalised attributes [16].

  * $\bullet$

SysFor* Decision forest algorithm SysFor, a systematically developed forest of
multiple decision trees [17].

  * $\bullet$

SimpleCart Classification and Regression Tree, Class implementing minimal
cost-complexity pruning [18].

Table 2: Dataset descriptions Data Name | Test Set | Training Set | No.of Classes | Length
---|---|---|---|---
ArrowHead | 35 | 176 | 3 | 251
Mallet | 2345 | 55 | 8 | 1024
FordA | 1320 | 3601 | 2 | 500

###  4.2 Arrowhead data

The first dataset consists of profiles of Arrowheads where we utilise the
profiles as time series. The dataset has three classes, see Figure 1, we
combined the test and training sets together to give 211 records This enabled
us to use Ten-fold Cross-Validation with WEKA for evaluation.

Figure 1: Profile of each Arrowhead class Figure 2: NPES of each Arrowhead
Class using Wavelet Transforms

Following the $\mathbf{MWSCS}$ procedure, initially we applied various wavelet
filters to each of the arrowhead classes to plot the NPES. Given the 251 data
points in length, the wavelet transform deconstructing the signal to the first
level, provided us with 125 detail and 125 smooth coefficients but also an
“Extra” class of coefficients, how this class is calculated and implemented in
the transform, by the chosen software is fully described in [8, Chap 4.11].

These additional coefficients are simply untransformed data. For this dataset
as the “Extra” coefficients contain considerable signal energy/information,
they are combined with the smooth coefficients in constructing our new data.
For each transformed signal, the Extra coefficients contain an average of
1.41% of signal energy per transformed signal at level 1 and 3.45% at level 2.

The NPES of samples taken from each Arrowhead class highlight suitable wavelet
filters to represent the energy in a smaller number of data points as shown in
Figure 2. Little difference is apparent between the wavelet filters shown,
however the filters s16 and d12 represent the energy slightly more efficiently
than d4. Hence we use these wavelet filters to transform our signal data and
build our transformed dataset, this however provides no compression in the
signal representation as we will still have same number of wavelet
coefficients as data points in the original signal.

By selecting only the smooth coefficients101010 In this instance we also
include the Extra coefficients as they represent considerable signal energy.
at the respective level we are able to reduce the number of attributes within
our data and maintain classification accuracy as shown in Table 3. Here
classification accuracy is defined as the number of correctly Classified
Instances with respect to the dataset’s Class labels which are initially
provided within the original data.111111Using Accuracy % here is a suitable
metric, as the dataset is reasonably balanced i.e. Class 1 has 81 records,
Class 2 and 3 have 65 records each.

####  4.2.1 Arrowhead Results

Table 3 demonstrates the benefits of the wavelet transforms, s16 wavelet
filter performs slightly better than d4121212As indicated by the NPES, Figure
2. for the ensemble classifiers, The use of the smooth coefficients resulting
from s16 (and when combined with d12), maintain accuracy while using reduced
numbers of attributes.

Using the smooth wavelet coefficients and including the Extra coefficients,
where these Extra coefficients contain considerable signal energy, still
provide considerable accuracy, especially when using the ensemble classifiers.

  * $\mathbf{Table\;\ref{tableArrow}\;Description:}$

  * $\bullet$

$\mathbf{Classifier}$ The first column is the list of classifiers used, see
section 4.1

  * $\bullet$

$\mathbf{Raw\;data}$ results from classifying original data, being 251 units
in length

  * $\bullet$

$\mathbf{Wavelet\;d4}$ results from data transformed using Wavelet filter d4,
signal decomposed to four levels, 248 units in length

  * $\bullet$

$\mathbf{Wavelet\;s16}$ results from data transformed using using Wavelet
filter s16, signal decomposed to four levels, 248 units in length

  * $\bullet$

$\mathbf{Wavelet\;s16\;\mathcal{S}_{1}+Extra}$ results from data transformed
using s16 using only the smooth level 1 and Extra coefficients, 126 units in
length

  * $\bullet$

$\mathbf{Wavelet\;s16\;d12\;combined\;\mathcal{S}_{2}}$ results from data
transformed using s16 and d12 filters, combining the smooth level 2
coefficients from both transforms to form a new data series , 62 + 62 = 124
units in length. A MDWT, see section 2.1

  * $\bullet$

$\mathbf{Wavelet\;s16\;d12\;combined\;\mathcal{S}_{2}+Extras}$ results from
data transformed using s16 and d12 wavelet filters, combining the smooth level
2 and Extra coefficients from both transforms to form a new data series , 64 +
64 = 128 units in length, again a MDWT.

Table 3: Classification of Arrowhead data, Cross Validation 10-Fold

| Classification Accuracy% |
---|---|---
| Raw data | Wavelet d4 | Wavelet s16 | Wavelet s16 | Waves s16 d12 | Waves s16 d12
$\mathbf{Classifier}$ |  | 4 levels | 4 levels |  $\mathcal{S}_{1}$ \+ Extra | combined $\mathcal{S}_{2}$ | comb. $\mathcal{S}_{2}$ \+ Extra
J48 | 75.35 | 76.03 | 74.41 | 79.14 | 77.72 | 72.72
Rforest | 86.25 | 84.36 | 86.25 | 90.05 | 89.1 | 89.57
ForestPA | 80.09 | 79.14 | 81.51 | 79.62 | 82.46 | 83.88
SysFor | 82.46 | 81.52 | 81.99 | 83.41 | 84.36 | 84.36
SimpleCart | 73.46 | 73.93 | 72.51 | 70.14 | 70.61 | 70.61

###  4.3 Mallat data

From the UCR dataset, Mallat Curve data, 8 distinct classes of 1024 units in
length, see Figure 3. We combined the data, both testing and training sets to
have a larger set containing 2400 records, eight classes of 300 records each.

Figure 3: Mallat data

Following the $\mathbf{MWCSC}$ procedure as with the Arrowhead data, using the
NPES to determine suitable wavelets to represent the signal energy, we apply
the classifiers to the wavelet transformed data. This time we use 20% of data
for training and 80% for testing, (the actual records in these sets were
chosen by WEKA).

####  4.3.1 Mallat data, Results

Table 4 highlights results from the Classifiers. The original data is 1024
unit long, hence the full wavelet transform also 1024 units long. Using the
smooth wavelet coefficients from $\mathcal{S}_{1}$ results 512 units in
length, similarly $\mathcal{S}_{2}$ results in 256 units and
$\mathcal{S}_{3}$, 128 units.

Using the various levels of decomposition, increasing the effective
compression of the signal transform we note that accuracy is maintained,
especially with the ensemble classifiers. However when we combine the two
$\mathcal{S}_{3}$ levels (a MDWT) from different wavelets (as determined by
the NPES), then the ensemble classifiers maintain considerable accuracy, given
the reduced transformed signal size, $\mathcal{S}_{3}\times$2 = 128 + 128 =
256 units. A small accuracy gain over the single wavelet transforms using
$\mathcal{S}_{2}$ or $\mathcal{S}_{3}$.

Table 4: Classification of Mallat data, 20% training, 80% testing

| Classification Accuracy% |
---|---|---
| Raw data | Wavelet s16 | Wavelet s16 | Wavelet s16 | Wavelet s16 | Waves s16 d8
$\mathbf{Classifier}$ |  | 10 levels | $\mathcal{S}_{1}$ | $\mathcal{S}_{2}$ | $\mathcal{S}_{3}$ | combined S3
J48 | 98.88 | 94.48 | 97.29 | 95.99 | 95.67 | 94.74
Rforest | 97.18 | 98.85 | 98.33 | 98.01 | 98.07 | 98.25
ForestPA | 96.61 | 97.34 | 97.39 | 97.23 | 97.81 | 97.86
SysFor | 95.52 | 95.93 | 96.15 | 94.63 | 95.15 | 95.36
SimpleCart | 95.57 | 95.0 | 96.3 | 95.93 | 94.17 | 94.53

###  4.4 Ford data

From the UCR dataset, Ford data, 2 distinct classes of 500 units in length.
here the classification problem is to diagnose whether a specific symption
exists or not in an automotive subsystem. We use the original training and
test sets as provided in the UCI data and follow the $\mathbf{MWCSC}$. The
test set, had 681 records in one class and 629 in the other.

NPES determined wavelet filters d16 and s20 as suitable. Results in Table 5
show we may maintain accuracy even at higher levels of compression,(or
attribute reduction). Using the smooth components at level 1,
$\mathcal{S}_{1}$ results in 250 units, using $\mathcal{S}_{2}$ provides 125
units, $\mathcal{S}_{3}$ gives 62 units and $\mathcal{S}_{3}$ \+ Extra
coefficient gives 63 units in length. Very little gain is evident in this last
transform as only a minor levels of signal energy is contained within the
Extra coefficients at the $3^{rd}$ level.131313The average energy/information
provided by the Extra coefficients at level $\mathcal{S}_{3}$, per transformed
signal is only 0.5% hence little if at all any gain in accuracy is achieved by
including the Extra coefficients at this level.

Table 5: Classification of Ford data, 3601 training records, 1320 testing
records

| Classification Accuracy% |
---|---|---
| Raw data | Wavelet d16 | Wavelet d16 | Wavelet d16 | Waves d16 s20 | Waves d16 s20
Classifier |  | S1 | S2 | S3 | combined S3 | comb. S3 + Extra
J48 | 56.13 | 58.03 | 56.44 | 52.42 | 58.71 | 58.18
Rforest | 73.25 | 72.95 | 71.37 | 73.41 | 74.2 | 75.53
ForestPA | 74.24 | 75.91 | 74.17 | 74.69 | 74.09 | 74.92
SysFor | 62.27 | 59.17 | 59.59 | 63.79 | 64.47 | 60.38
SimpleCart | 58.18 | 58.11 | 56.37 | 59.02 | 59.92 | 59.15

###### Remark 3

For the single tree method J48, It would appear that our choice of specific
wavelets within the MDWT might not be crucial as no evidence of consistent
additional gain between the two MDWT variations. However the choice of
additional attributes (as provided by the MDWT) to train upon would seem to
provide some minor gain over using a single Wavelet transform.

##  5 Conclusion

It has been shown previously that wavelets may be used for signal compression
with little loss of accuracy [5]. Our MWCSC methodology which makes use of the
NPES and MDWT provides us a method to determine suitable wavelets as well as
add additional information to the attribute space. This enables us to use
transformed data sets with smaller dimension than the original data yet still
provide similar or enhanced accuracy. From the NPES graphic, Figure 2, we note
that wavelet d4 is not as efficient at energy representation as wavelet s16,
for the arrowhead dataset. This is similarly represented in Table 3 by
comparing classification results, across the various classifiers of raw data
as well as the data transformed by the d4 or the s16 wavelet filters.

Construction of the MDWT from suitable wavelets enhances the accuracy while
offering an effective compressed representation of the signal to which the
classifiers my be applied to. Inclusion of “Extra” coefficients into the
construction of the MDWT, where such coefficients contain considerable signal
energy adds additional accuracy for little extra computation, as they are an
included class in the transform calculation where
$\\{X_{t}:t=1,\ldots,n\\},\;n\neq 2^{J}\;J\in\mathbb{Z^{+}}.$

###  5.1 Future Work

Within the construction of a MDWT, each separate DWT used to decompose the
time series had the level or scale $J_{0}$ of decomposition remain unchanged.
This may not be optimal as wavelet family, filter length and scale of
decomposition, may all be correlated with respect to how the
energy/information in the signal is represented. Hence wavelet decomposition
using different scales within a MDWT should be considered. The the number of
wavelet filters within a MDWT might be altered depending upon importance of
accuracy or compression (reduced number of attributes), in our experiment a
MDWT consisted of only two different wavelet filters.

## References

  * [1] P. Grant and Md. Zahidul Islam :2019. A novel approach for noisy signal classification through the use of multiple wavelets and ensembles of classifiers. In R. Goebel, Y. Tanaka, & W. Wahlster (Eds.), 15th International Conference on Advanced Data Mining and Applications (ADMA 2019) (Vol. 11888, pp. 195-203). Springer. https://doi.org/10.1007/978-3-030-35231-8_14
  * [2] P. Clark and T. Niblett: 1987. Induction in Noisy Domains. In Progress in Machine Learning (from the Proceedings of the 2nd European Working Session on Learning), 11-30, Bled, Yugoslavia: Sigma Press.
  * [3] S, Fong, Using Hierarchical Time Series Clustering Algorithm and Wavelet Classifier for Biometric Voice Classification Journal of Biomedicine and Biotechnology Volume 2012, Article ID 215019.
  * [4] Marco Grimaldi, Anil Kokaram, Pádraig Cunningham. 2002. Classifying Music by genre using wavelet packet transform and a round-robin ensemble, Comp Science Dept.; Electronic and Electrical Engineering Dept., Trinity College Dublin, Ireland.
  * [5] Daoyuan Li, Tegawend´e F. Bissyand´e, Jacques Klein and Yves Le Traon. 2016. Time Series Classification with Discrete Wavelet Transformed Data: Insights from an Empirical Study, The 28th International Conference on Software Engineering and Knowledge Engineering.
  * [6] Morteza Moazami-Goudarzi, Mohammad H. Moradi, Sara Abbasabadi, 2006. High Performance Method for Electrocardiogram Compression Using Two Dimensional Multiwavelet Transform, IEEE 7th Workshop on Multimedia Signal Processing.
  * [7] A. Graps, 1995. An Introduction to Wavelets, IEEE Computational Science and Engineering Summer Vol 2, num 2.
  * [8] D. B. Percival and A. T. Walden, 2000. Wavelet Methods for Time Series Analysis, Cambridge University Press.
  * [9] G.P. Nason, 2008. Wavelet Methods in Statistics with R, Springer, New York.
  * [10] R Core Team ,2013. R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria. URL http://www.R- project.org/.
  * [11] W. Constantine and D. Percival, 2017. wmtsa: Wavelet Methods for Time Series Analysis. R package version 2.0-3 http://CRAN.R-project.org/package = wmtsa.
  * [12] Eibe Frank, Mark A. Hall, and Ian H. Witten, 2016. The WEKA Workbench. Online Appendix for “Data Mining: Practical Machine Learning Tools and Techniques”, Morgan Kaufmann, Fourth Edition.
  * [13] Y. Chen, E. Keogh, B. Hu, N. Begum, A. Bagnall, A. Mueen, and G. Batista, “The ucr time series classification archive,” October 2018, https://www.cs.ucr.edu/ eamonn/time_series_data_2018
  * [14] R. Quinlan, 1993. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, San Mateo, CA.
  * [15] L. Breiman, Machine Learning (2001) 45:5. https://doi.org/10.1023/A:1010933404324
  * [16] Md Nasim Adnan, Md Zahidul Islam. 2017. Forest PA: Constructing a decision forest by penalizing attributes used in previous trees. Expert Systems With Applications. 89:389-403.
  * [17] Md Zahidul Islam and H. Giggins, 2011. Knowledge Discovery through SysFor: A Systematically Developed Forest of Multiple Decision Trees, In Proc. of the Ninth Australasian Data Mining Conference (AusDM 11).
  * [18] Leo Breiman, Jerome H. Friedman, Richard A. Olshen, Charles J.Stone, 1984. Classification and regression trees Boca Raton : CRC Press.


# Your Co-Workers Matter: Evaluating Collaborative Capabilities of Language
Models in Blocks World

Guande Wu1, Chen Zhao1,2, Claudio Silva1, He He1
1New York University, 2NYU Shanghai
{guandewu, cz1285, csilva<EMAIL_ADDRESS>

###### Abstract

Language agents that interact with the world on their own have great potential
for automating digital tasks. While large language model (LLM) agents have
made progress in understanding and executing tasks such as textual games and
webpage control, many real-world tasks also require collaboration with humans
or other LLMs in equal roles, which involves intent understanding, task
coordination, and communication. To test LLM’s ability to collaborate, we
design a blocks-world environment, where two agents, each having unique goals
and skills, build a target structure together. To complete the goals, they can
act in the world and communicate in natural language. Under this environment,
we design increasingly challenging settings to evaluate different
collaboration perspectives, from independent to more complex, dependent tasks.
We further adopt chain-of-thought prompts that include intermediate reasoning
steps to model the partner’s state and identify and correct execution errors.
Both human-machine and machine-machine experiments show that LLM agents have
strong grounding capacities, and our approach significantly improves the
evaluation metric.

Your Co-Workers Matter: Evaluating Collaborative Capabilities of Language
Models in Blocks World

Guande Wu1, Chen Zhao1,2, Claudio Silva1, He He1 1New York University, 2NYU
Shanghai {guandewu, cz1285, csilva<EMAIL_ADDRESS>

##  1 Introduction

Figure 1: Task Setting:  A human agent (Amy) and an LLM agent (Bob)
collaborate on building the block structure with diverse goals and
inventories. Sample Task Process:  In the shown task, Amy’s goal relies on
Bob’s, so they have to coordinate. To succeed on this task, Amy and Bob have
to 1) communicate their goals and figure out the immediate plan to complete;
2) Amy place the yellow blocks to complete the immediate plan; 3) Amy and Bob
coordinate to complete the remaining part of their goals.

As large language models (LLMs) evolve, they are increasingly expected to
collaborate closely with humans or other LLM agents, emphasizing the
importance of coordination and communication Radford et al. (2019). For
instance, an LLM assistant might need to work alongside human professionals to
plan tasks, manage projects, and ensure efficient execution. While multi-agent
collaboration is not a new area Leibo et al. (2021); Carroll et al. (2019); He
et al. (2017), there is limited study on how LLM agents collaborate with
humans in equal roles, rather than passively following human’s instructions.

To fill this gap, we introduce a collaborative blocks world environment
(CoBlock), to evaluate the collaboration ability of LLMs. In this environment,
two agents (either human or LLM), each equipped with complementary goals and
skills, collaborate to build a target structure without a designated leader.
For example, as shown in Figure 1, Amy is responsible for the top structure,
which must be built on top of the base structure that Bob needs to build
first. Meanwhile, Amy does not have the red blocks that are necessary to
complete her goal. Therefore, they must coordinate their actions, like
deciding what to build first and who builds what (e.g., Amy may ask Bob to
build the yellow pillar first).

We design three scenarios to progressively increase the level of interaction
and coordination required between the two agents, moving from independent
tasks to more complex, interdependent tasks (Figure 2).

  * •

Independent tasks: Each agent can complete its assigned partial structure
without the partner’s participation.

  * •

Skill-dependent tasks: One agent relies on the other’s “skill” or resources to
complete the task. For instance, Bob needs Amy’s help to build the yellow bar
because he doesn’t have any yellow blocks.

  * •

Goal-dependent tasks: This scenario involves dependence between the agents’
assigned partial structure (i.e. goal), requiring more advanced planning and
coordination.

To ground LLMs in CoBlock and enable them to complete the tasks, we prompt GPT
series models (GPT-3.5 and GPT-4) to make decisions about the next action
given the current observation. At each round, our basic prompt describes the
agent’s goal (the color and position of every block), the current state (the
structure built so far, the action and message history), and candidate actions
to choose from (place a block, send a message, wait or terminate the task).

To guide the model in choosing the right action, we additionally include
chain-of-thought prompts (CoT) Wei et al. (2022) to go through intermediate
reasoning steps: (1) analysis of the currently built structure and the agent’s
goal; (2) partner-state modeling to predict the current intent and state of
the partner; and (3) self-reflection that identifies and corrects any
execution error, and adjusts communication style accordingly.

We evaluate the LLM agents in CoBlock under both machine-machine and human-
machine settings, measured by task success rate, total steps, and workload
balance. First, we find that LLM agents have a high success rate when building
the structure independently, demonstrating strong grounding ability even
without multi-modal training. Second, adding partner-state modeling and self-
reflection prompting results in a 30% absolute increase in task completion
rate and leads to better workload balance. Finally, while human-machine
collaboration has a slightly higher success rate than machine-machine
collaboration, humans often take on more responsibility in challenging
scenarios when the LLM agent struggles. We hope our findings and the
evaluation environment will support future studies on communication and
coordination in multi-agent collaboration.111The code and data is available at
https://github.com/jnzs1836/coblocks.

##  2 The Collaborative Blocks World

In this section, we describe the collaborative blocks world environment
CoBlock (Section 2.1) and the three types of collaboration tasks (Section
2.2).

Figure 2: Three different collaboration tasks with increasing levels of
coordination. Top: The independent tasks that require little coordination
between agents; Middle: The skill-dependent tasks that at least one goal
requires both agents to complete; Bottom: The goal-dependent tasks that one
agent’s goal depends on prior completion of the partner’s goal.

###  2.1 The CoBlock Environment

As shown in Figure 1, in each task, two agents work together to build a target
structure by taking actions in the CoBlock. Specifically, either agent takes
one action in each round, we move to the next round after actions from both
agents are executed. The task is terminated when the target structure is
completed or either agent takes the end_task action.

#### Structure.

A structure $G$ consists of a set of blocks
$B=\\{b_{1},b_{2},\cdots,b_{m}\\}$, where each block $b$ is specified by a
color $c$ from a set of colors $C$ (we use a total of six colors), and a 3D
position given by coordinates $(x,y,z)$. To simulate real-world conditions, a
structure must adhere to the gravity restriction, where each block must be
adjacent to at least one other block or be on the ground plane (i.e. $y=0$). A
sub-structure of $G$ is a smaller structure formed from a subset of $G$’s
blocks.

#### Agent.

Each agent is given a goal $g$, which is a sub-structure of the target
structure $G$. The union of the sub-structures forms the target structure. For
example, in Figure 1, Amy is given the upper part of the target structure
while Bob is given the lower pillar. Additionally, each agent has an inventory
$e=\\{(c_{1},n_{1}),\cdots,(c_{k},n_{k})\\}$, where $n_{i}$ denotes the number
of blocks of color $c_{i}$. Each inventory contains a subset of colors present
in $G$. The goal and inventory of each agent are private so they must
communicate to figure out who needs what.

#### State.

The state of the world consists of all public information, including the
structure built so far, and the history of the agents’ utterances and actions.

#### Actions.

An agent can take one of the following actions: place a block from its
inventory at specific coordinates; remove a block that was placed at specific
coordinates (the block will not be used anymore); send messages to its
partner; wait without performing any action; and terminate the task.

###  2.2 Collaboration Tasks

To evaluate different aspects of collaboration, we design three types of tasks
with increasing levels of dependence between two agents. We ensure there
exists at least one solution to complete the task. Examples of the tasks are
shown in Figure 2.

#### Independent tasks.

These tasks require minimal coordination, as two agents can build their goals
separately to complete the target structure. However, the agents still need to
communicate initially to determine that they can each build their
substructures independently.

#### Skill-dependent tasks.

An agent cannot complete its goal without assistance from its partner, as it
lacks certain colors of blocks. For example, in Figure 2, Amy needs to
describe the green sub-structure to Bob so that Bob can build it using his
green blocks. To succeed in these tasks, an agent must communicate its needs,
understand the partner’s needs, and then coordinate the actions accordingly.

#### Goal-dependent tasks.

In these tasks, in addition to the dependence between agents’ skills, an
agent’s ability to complete their goal may depend on prior completion of the
partner’s goal due to the gravity restriction. For example, in Figure 2, Amy
must build her sub-structure first (which requires Bob’s help with the yellow
blocks), so that Bob can build his sub-structure on top of it later. These
tasks are the most challenging, as there are complex dependencies among the
steps to finish the target structure.

##  3 Building Collaborative Agents based on LLMs

We use an LLM as the base agent and query it at each round to predict the next
action given the current world state (e.g., the structure built so far and the
agent’s goal).

  * •

Input: The input consists of descriptions of the state of the world described
in XML (Figure 3 left), including the goal of each agent, the structure built
so far, the dialogue and action histories. We use a sequence of blocks (with
color and 3D position) to represent the structures.

  * •

Output: The output is the next action (place, break, send message, wait or
terminate). We instruct the model to use a specific format (e.g.,
send_message(message="Hello")) to ensure that it can be parsed for execution
in the environment.

To help the LLM agent decide the next action, we use CoT prompting to guide
the LLM agent through several intermediate steps designed to anticipate the
partner’s needs and adjust the construction plan given new observations. We
describe each step below and show examples in Figure 3.

Figure 3: World State consists of the agent’s goal, currently built structure,
dialogue, and action history. Prompt Text consists of four steps: 1) Analyze
the XML world state and summarize the useful information; 2) Infer both the
agent and the partner’s state; 3) Self-reflection which identifies the errors
and adjusts the communication strategies; 4) Predict the action. We use the
CoT prompts in all steps.

#### Step 1: understanding the world state.

The world state is represented using the XML format. Therefore, we prompt LLM
agent to first parse the state and describe it in natural language. For
example, given the <goal> and <built structure> field, the agent infers that
it should build the yellow blocks next.

#### Step 2: modeling the partner’s state.

Effective collaboration requires an agent to understand the partner’s needs
and coordinate with them to strike a balance between assisting others and
fulfilling their own goal. For example, in skill- and goal-dependent tasks,
the agent must identify which sub-structures their partner needs help with and
integrate it into the planning of their goals. Therefore, we incorporate
partner-state modeling Boutilier (1996); Chalkiadakis and Boutilier (2003)
into our prompts as an intermediate step. As shown in Figure 3, based on the
dialogue and action history, the agent predicts the intent and state of its
partner, including the goal, the inventory set, the immediate next plan (e.g.,
building the green sub-structure), and whether the plan has been executed.

#### Step 3: reflecting on past actions and dialogue.

Misunderstandings in collaboration can lead to incorrect actions, and if these
errors aren’t corrected promptly, they may result in higher expenses to
rectify them later. For instance, an agent might place a block of the wrong
color at a specified position. If this error isn’t corrected in the subsequent
round, it could take multiple backtracking actions to correct the mistake. To
address this issue, we adopt the self-reflection mechanism Fu et al. (2023) to
help the agent review the currently built structure and correct low-level
construction errors and high-level communication strategies.

Specifically, we compare the built structure and the agent’s goal to check if
there is an error using an external program (i.e. whether the built structure
is exactly a partial structure of the goal). The feedback is then sent to the
agent to correct the potential error. In addition, we instruct the agent to
adjust their communication strategies Hovland et al. (1953) based on the
feedback along three dimensions: team role (whether to take the lead and
assign tasks to the partner), altruism/egoism balance (whether to pursue their
own goals or assist the partner), and persuasion strategy (whether to be more
proactive and persuasive in communication).

#### Step 4: predicting the next action.

The final step generates the next action based on the world state, partner
state, and the reflection result in previous steps.

####

Our final prompt starts with a general description of the game and the
input/output format for the model to understand the XML and the action
functions. To guide the LLM agent to decide the next action through the above
reasoning steps, we then provide a CoT prompt that consists of a sequence of
reasoning examples, where each example consists of the current world state and
the four reasoning steps. A full prompt is shown in Appendix B.

##  4 Experiments

Successfully completing tasks in CoBlock requires both grounding and
collaboration abilities. Therefore, we first access whether LLMs are able to
execute instructions in CoBlock correctly through a single-agent experiment
(Section 4.2). Next, we evaluate whether LLM agents can effectively
collaborate with other LLM or human agents through communication and
coordination using a multi-agent experiment (Section 4.3 and 4.4).

###  4.1 Implementation Details

#### Environment.

We implement the CoBlock environment using a web interface based on React.js
Facebook Inc. (2023), and render the 3D world through THREE.js Danchilla and
Danchilla (2012). To generate target structures, we follow five common
structures used in Narayan-Chen et al. (2019): symbol, bridge, arch, tower,
and rectangle. We then use depth-first search to find combination of these
common structures and manually adjusted them if needed. To generate the goals
and skills for each agent, we manually split the target structures into two
sub-structures and assign inventories to make sure that the tasks can be
completed collaboratively. In total, we create 24 collaboration tasks in
CoBlock. The details of task creation can be found in Appendix A.1.

#### Agents.

We recruit human participants with experience playing Minecraft (which is
similar to CoBlock) via Amazon Mechanical Turk. Participants must complete a
tutorial and pass a qualification exam to perform the tasks. We pay
participants with an hourly rate of $18. Based on our pilot study, the tasks
are usually completed within thirty minutes. For LLM agents, we provide eight
in-context CoT examples covering three types of tasks: two independent tasks,
three skill-dependent tasks, and three goal-dependent tasks. we also include a
baseline LLM agent, using CoT prompts but without partner-state modeling (Step
2) and self-reflection mechanism (Step 3).

###  4.2 Single-Agent Experiment

Figure 4: Single-agent experiment settings including three parts. We represent
the blocks by the XML structure and the textual description. Part I: describe
the given XML into textual descriptions. Part II: convert the XML into a
sequence of commands. Part III: directly convert the textual description into
a sequence of commands.

We propose three single-agent tasks to evaluate the grounding abilities of LLM
agents (Figure 4): 1) Generate textual descriptions from XML-represented
structures; We manually evaluate these descriptions to verify the LLM agent’s
ability to describe the target structure. 2) Generate a sequence of actions
given the XML structures; This task measures the agent’s ability for task
planning. 3) Generate the action sequence from the textual descriptions. This
task combines the first two tasks and therefore requires both grounding and
planning capacities.

Evaluation Metrics. We use success rate to evaluate the proportion of tasks
completed by agents successfully (i.e. generate the correct description in
task 1 and the action plan in tasks 2 and 3):

$\text{Success Rate}=\frac{\text{Number of Success }}{\text{Total Number of
Tasks}}$ (1)

Results. According to Figure 5, both GPT-4 and GPT-3.5 agents successfully
complete almost all three tasks, which indicates that LLM agents have the
sufficient grounding and planning skills for the collaborative blocks world.
Therefore, the observed failures in the collaboration tasks (which we present
next) should not mainly come from the grounding and planning capacities of
agents.

###  4.3 Multi-Agent Experiment Setup

We propose two multi-agent task settings: Human-machine collaboration that a
human agent and an LLM agent build the structures. This setting aims to
evaluate the ability of LLM agents to act as proactive collaborators that
fulfill their own goals while assisting human partners; Machine-machine
collaboration that two LLM agents build the structures, primarily evaluates
the collaboration behaviors between two LLM agents.

Evaluation Metrics. Similar to the single-agent setting, we use success rate
(See Equation 1) to measure whether agent(s) can complete the target
structure. We propose two additional metrics targeting the effectiveness of
collaboration McEwan et al. (2017) during task execution:

Workload Balance measures how tasks are distributed evenly between two agents.
Since the agents have varying goals and skills, even optimal task assignments
result in different action numbers. Therefore, we normalize the number of
actions by comparing them with the optimal action number

$a_{1}=\frac{N_{a}\cdot N^{*}_{b}}{N^{*}_{a}};b=N_{b}$ (2)

where the $N_{a}$ and $N_{b}$ refer to the numbers of actions and $N^{*}_{a}$
and $N^{*}_{b}$ are the numbers of optimal actions. The final workload balance
$\gamma$ is computed as

$\gamma=\frac{a*b}{a^{2}+b^{2}}.$ (3)

The optimal value of $\gamma$ is $0.5$.

Task Completion Timesteps is defined as the total number of actions required
to complete the task. 222We do not use wallclock time because it can be
affected by the network latency and the participant’s response time.

Figure 5: Experiment results on single-agent experiments (Part I, II, III).
LLM agents successfully complete almost all tasks. Figure 6: Human-machine
experiment results. The experiments are conducted on the independent, skill-
dependent, and goal-dependent tasks with both GPT-3.5 and GPT-4. We include
both LLM agents and baseline LLM agents without partner-state modeling and
reflection. Figure 7: Machine-machine experiment results. Similar to human-
machine experiments, we include independent, skill-dependent, and goal-
dependent tasks with both GPT-3.5 and GPT-4. We include LLM agents, LLM agents
without reflection and baseline LLM agents without both partner-state modeling
and reflection.  Figure 8: A human-machine example in the skill-dependent
task. Our baseline LLM agents fail to complete their own goals due to the
priority of assisting the partner. Intermediate steps are omitted for clarity.

###  4.4 Multi-Agent Experiment Results

We present the human-machine experiment results in Figure 6 and machine-
machine results in Figure 7. In addition to quantitative results, we conduct
an error analysis by manually collecting all failure instances (73 in total)
from both human-machine and machine-machine experiments.

Baseline LLM agents struggle to complete the task.  According to Figure 6 (A)
and Figure 7 (A), the baseline agents suffer from a low task success rate in
the skill-dependent and goal-dependent tasks. The contrast with single-agent
experiment results suggests that collaboration presents significant
challenges. We find that LLM agents often prioritize assisting their partners
and neglecting their own goals (55.6% errors in the goal-dependent tasks and
37.5% errors in the skill-dependent tasks). In addition, LLM agents lack
initiative in seeking additional information from the partner (11.1% errors in
the skill-dependent tasks and 25.0% errors in the goal-dependent tasks). For
instance, in Figure 8, when a human’s intention (build blue blocks) conflicts
with the LLM agent (build green blocks), the LLM agent stops executing its own
goal, but decides to help human instead.

Figure 9: A human-machine example in the goal-dependent task. We show our LLM
agent on the left and the baseline LLM agent on the right. Our LLM agent
actively helps the partner to complete the task when the baseline keeps
waiting.

Both partner-state modeling and reflection enhance collaboration. First,
partner-state modeling significantly improves agents in the skill-dependent
and goal-dependent tasks in all metrics, as LLM agents are more adept at
negotiating with partners to achieve their own goals. The reflection mechanism
further helps adjust the communication strategy, especially when human
partners are less collaborative. In 33% skill-dependent tasks and 17% goal-
dependent tasks, human participants have a low engagement, and the LLM agents
change the communication stragetgy accordingly. For instance, one human
participant continuously works on his goal even when the LLM agent asks for
assistance. The LLM agent then prompts with a message that “Please build the
yellow blocks from (0, 0, 2) to (0, 3, 2), so I can proceed with the task.”.

LLM agents actively communicate with partners.  According to Figure 6 (B, C)
and Figure 7 (B, C), LLM agents outperform baseline agents on task workload
balance and timesteps. This is mainly due to more proactive communication. For
example, in Figure 9, the baseline LLM agent stops after its goal is fulfilled
(observed in 56% skill-dependent tasks and 42% goal-dependent tasks). However,
our LLM agent continues to engage, and asks, "I have finished my sub-
structure. What should we do next?".

Humans are smarter, but sometimes less collaborative. In the human-machine
experiment, a majority of humans are smarter than LLM agents—humans can
actively identify and rectify LLM agents’ errors (13% skill-dependent tasks,
and 8% goal-dependent tasks). However, a small portion of human collaborators
(14.6%) are not collaborative. In these scenarios, our reflection mechanism
pushes the LLM agents to adopt a more active role in engaging with human
partners.

##  5 Related Work

Multi-Agent Collaboration with Reinforcement Learning. Several approaches have
been proposed to use reinforcement learning for multi-agent collaboration
Bloembergen et al. (2015), including both value-based Chhogyal et al. (2019)
and policy-based methods Lowe et al. (2017). These methods aim to estimate the
expected value for every decision-making turn by considering both the agent
itself and partner agents Bloembergen et al. (2015). Unlike existing
approaches that model information exchange over a predetermined set of
primitives, we focus on a more generic scenario where agents communicate in
natural language.

Agents based on LLMs. Existing research for agents based on LLMs mainly
focuses on text-based, single-agent settings, such as web navigation and text
games Furuta et al. (2023); Yao et al. (2022); Zhou et al. (2023b); Kim et al.
(2023); Xi et al. (2023). Methods have been proposed to improve the planning
and reasoning capacities of these agents, including chain-of-thought Wei et
al. (2022); Kim et al. (2023); Zhang et al. (2023), self-consistency decoding
Wang et al. (2023), task decomposition Zhou et al. (2023a), and error
reflection Yao et al. (2023). Concurrent studies Zhou et al. (2023c); Gong et
al. (2023) extend LLM agents into multi-agent settings but are mainly
constrained to multiple LLM agents. We build upon the recent development of
LLM agents but mainly investigate the potential of multi-agent (especially
human-LLM) collaboration.

Theory of Mind Agents. Effective collaboration requires agents to infer the
intents of partner agents. Theory of Mind (ToM) refers to the agent’s ability
to impute mental states to the agent itself and other agents. With the help of
LLMs, there are a significant amount of discussions about whether ToM has
emerged by LLM agents Ma et al. (2023); Jamali et al. (2023); Kosinski (2023).
We follow the idea of ToM and propose to incorporate the partner-state
modeling approach into chain-of-thought prompts to build LLM agents.

##  6 Conclusion

In this paper, we introduce a new collaborative blocks environment (CoBlock),
where human or LLM agents collaborate to complete a target structure. We
prompt LLM agents to make decisions about the next action in CoBlock, and
further propose to enhance collaborative abilities by modeling partner agents’
state and intention and correcting errors and communication strategies from
feedback. Both human-machine and machine-machine experiments indicate the
effectiveness of our agents, especially on more challenging tasks that require
more advanced collaboration. We believe this work provides resources and
insights for future work in advancing multi-agent collaboration for social
good that requires different levels of collaboration strategies.

## Limitations

Multi-Agent Collaboration. A primary limitation of our study is that we focus
on a two-agent setting. While our framework serves as an initial study, it may
not fully capture the dynamics of multi-agent collaboration Wilsker (1996).
Future work should aim to expand our platform to accommodate more than two
agents and involve multiple human participants.

Generalizability of Agent-State Modeling. Our agent-state modeling approach
mainly focuses on information specific to the blocks world. To extend our
approach to other domains, we should reconfigure the agent-state format to
include more diverse information about agents’ states. Additionally, our
design overlooks the aspect of memory, which is crucial for long-term
collaboration. Incorporating a partner’s memory status into decision-making
can be helpful during collaboration.

Agents Capability. We define the agent’s capabilities primarily in terms of
block inventory. However, there are various other capabilities, such as
breaking, placing, or picking up resources, which could significantly enrich
the collaborative process. Future research should explore more diverse
capabilities to provide a better understanding of multi-agent collaboration.

## Ethical Consideration

We conduct a human-machine experiment, recruiting participants through Amazon
Mechanical Turk. We get an IRB-approved protocol, ensuring no personal
information from participants was recorded. We check the collected data to
ensure it contains no hate speech or personal information. We implement our
blocks world in the web portal with the 3D blocks world, therefore we require
that no participant suffers from 3D motion sickness and would be harmed by the
experiments.

There is a risk that the LLM agents might be assigned ethically questionable
or unjust goals by stakeholders. In our current platform that is centered
around block-building tasks, the possibility of assigning harmful goals is
greatly minimized. However, we recognize that our proposed agents could raise
ethical concerns if applied into more realistic settings like violence
investigation Hu et al. (2022). Therefore, we emphasize the importance of
designing LLM agents to be ethically responsible regarding their assigned
goals.

## References

  * Bloembergen et al. (2015) Daan Bloembergen, Karl Tuyls, Daniel Hennes, and Michael Kaisers. 2015.  Evolutionary dynamics of multi-agent learning: A survey.  _J. Artif. Intell. Res._ , 53:659–697.
  * Boutilier (1996) Craig Boutilier. 1996.  Learning conventions in multiagent stochastic domains using likelihood estimates.  In _UAI ’96: Proceedings of the Twelfth Annual Conference on Uncertainty in Artificial Intelligence, Reed College, Portland, Oregon, USA, August 1-4, 1996_ , pages 106–114. Morgan Kaufmann.
  * Carroll et al. (2019) Micah Carroll, Rohin Shah, Mark K. Ho, Thomas L. Griffiths, Sanjit A. Seshia, P. Abbeel, and Anca D. Dragan. 2019.  On the utility of learning about humans for human-ai coordination.  In _Neural Information Processing Systems_.
  * Chalkiadakis and Boutilier (2003) Georgios Chalkiadakis and Craig Boutilier. 2003.  Coordination in multiagent reinforcement learning: a bayesian approach.  In _The Second International Joint Conference on Autonomous Agents & Multiagent Systems, AAMAS 2003, July 14-18, 2003, Melbourne, Victoria, Australia, Proceedings_, pages 709–716. ACM.
  * Chhogyal et al. (2019) Kinzang Chhogyal, Abhaya C. Nayak, Aditya Ghose, and Hoa Khanh Dam. 2019.  A value-based trust assessment model for multi-agent systems.  In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019_ , pages 194–200. ijcai.org.
  * Danchilla and Danchilla (2012) Brian Danchilla and Brian Danchilla. 2012.  Three. js framework.  _Beginning WebGL for HTML5_ , pages 173–203.
  * Facebook Inc. (2023) Facebook Inc. 2023.  React - a javascript library for building user interfaces.  Accessed: 2023-04-01.
  * Fu et al. (2023) Yao Fu, Hao Peng, Tushar Khot, and Mirella Lapata. 2023.  Improving language model negotiation with self-play and in-context learning from AI feedback.  _CoRR_ , abs/2305.10142.
  * Furuta et al. (2023) Hiroki Furuta, Ofir Nachum, Kuang-Huei Lee, Yutaka Matsuo, Shixiang Shane Gu, and Izzeddin Gur. 2023.  Multimodal web navigation with instruction-finetuned foundation models.  _CoRR_ , abs/2305.11854.
  * Gong et al. (2023) Ran Gong, Qiuyuan Huang, Xiaojian Ma, Hoi Vo, Zane Durante, Yusuke Noda, Zilong Zheng, Song-Chun Zhu, Demetri Terzopoulos, Li Fei-Fei, and Jianfeng Gao. 2023.  Mindagent: Emergent gaming interaction.  _CoRR_ , abs/2309.09971.
  * He et al. (2017) He He, Anusha Balakrishnan, Mihail Eric, and Percy Liang. 2017.  Learning symmetric collaborative dialogue agents with dynamic knowledge graph embeddings.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, ACL 2017, Vancouver, Canada, July 30 - August 4, Volume 1: Long Papers_ , pages 1766–1776. Association for Computational Linguistics.
  * Hovland et al. (1953) Carl Iver Hovland, Irving Lester Janis, and Harold H Kelley. 1953.  _Communication and persuasion._ Yale University Press.
  * Hu et al. (2022) Yibo Hu, MohammadSaleh Hosseini, Erick Skorupa Parolin, Javier Osorio, Latifur Khan, Patrick T. Brandt, and Vito D’Orazio. 2022.  Conflibert: A pre-trained language model for political conflict and violence.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL 2022, Seattle, WA, United States, July 10-15, 2022_ , pages 5469–5482. Association for Computational Linguistics.
  * Jamali et al. (2023) Mohsen Jamali, Ziv M. Williams, and Jing Cai. 2023.  Unveiling theory of mind in large language models: A parallel to single neurons in the human brain.  _CoRR_ , abs/2309.01660.
  * Kim et al. (2023) Geunwoo Kim, Pierre Baldi, and Stephen McAleer. 2023.  Language models can solve computer tasks.  _CoRR_ , abs/2303.17491.
  * Kosinski (2023) Michal Kosinski. 2023.  Theory of mind might have spontaneously emerged in large language models.
  * Leibo et al. (2021) Joel Z. Leibo, Edgar A. Duéñez-Guzmán, Alexander Vezhnevets, John P. Agapiou, Peter Sunehag, Raphael Koster, Jayd Matyas, Charlie Beattie, Igor Mordatch, and Thore Graepel. 2021.  Scalable evaluation of multi-agent reinforcement learning with melting pot.  In _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 6187–6199. PMLR.
  * Lowe et al. (2017) Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. 2017.  Multi-agent actor-critic for mixed cooperative-competitive environments.  In _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 6379–6390.
  * Ma et al. (2023) Ziqiao Ma, Jacob Sansom, Run Peng, and Joyce Chai. 2023.  Towards A holistic landscape of situated theory of mind in large language models.  In _Findings of the Association for Computational Linguistics: EMNLP 2023, Singapore, December 6-10, 2023_ , pages 1011–1031. Association for Computational Linguistics.
  * McEwan et al. (2017) Desmond McEwan, Geralyn R Ruissen, Mark A Eys, Bruno D Zumbo, and Mark R Beauchamp. 2017.  The effectiveness of teamwork training on teamwork behaviors and team performance: a systematic review and meta-analysis of controlled interventions.  _PloS one_ , 12(1):e0169604.
  * Narayan-Chen et al. (2019) Anjali Narayan-Chen, Prashant Jayannavar, and Julia Hockenmaier. 2019.  Collaborative dialogue in minecraft.  In _Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Papers_ , pages 5405–5415. Association for Computational Linguistics.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9.
  * Wang et al. (2023) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023.  Self-consistency improves chain of thought reasoning in language models.  In _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. 2022.  Chain-of-thought prompting elicits reasoning in large language models.  In _NeurIPS_.
  * Wilsker (1996) Burt Wilsker. 1996.  _A study of multi-agent collaboration theories_.  University of Southern California, Information Sciences Institute.
  * Xi et al. (2023) Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, Rui Zheng, Xiaoran Fan, Xiao Wang, Limao Xiong, Yuhao Zhou, Weiran Wang, Changhao Jiang, Yicheng Zou, Xiangyang Liu, Zhangyue Yin, Shihan Dou, Rongxiang Weng, Wensen Cheng, Qi Zhang, Wenjuan Qin, Yongyan Zheng, Xipeng Qiu, Xuanjing Huan, and Tao Gui. 2023.  The rise and potential of large language model based agents: A survey.  _CoRR_ , abs/2309.07864.
  * Yao et al. (2022) Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan. 2022.  Webshop: Towards scalable real-world web interaction with grounded language agents.  In _NeurIPS_.
  * Yao et al. (2023) Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R. Narasimhan, and Yuan Cao. 2023.  React: Synergizing reasoning and acting in language models.  In _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net.
  * Zhang et al. (2023) Jintian Zhang, Xin Xu, and Shumin Deng. 2023.  Exploring collaboration mechanisms for LLM agents: A social psychology view.  _CoRR_ , abs/2310.02124.
  * Zhou et al. (2023a) Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V. Le, and Ed H. Chi. 2023a.  Least-to-most prompting enables complex reasoning in large language models.  In _The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023_. OpenReview.net.
  * Zhou et al. (2023b) Shuyan Zhou, Frank F. Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Yonatan Bisk, Daniel Fried, Uri Alon, and Graham Neubig. 2023b.  Webarena: A realistic web environment for building autonomous agents.  _CoRR_ , abs/2307.13854.
  * Zhou et al. (2023c) Xuhui Zhou, Hao Zhu, Leena Mathur, Ruohong Zhang, Haofei Yu, Zhengyang Qi, Louis-Philippe Morency, Yonatan Bisk, Daniel Fried, Graham Neubig, and Maarten Sap. 2023c.  SOTOPIA: interactive evaluation for social intelligence in language agents.  _CoRR_ , abs/2310.11667.

##  Appendix A Experiment Setting Details

###  A.1 Structure Preparation

|
---|---
Symbol | Bridge
|
Arch | Tower
Rectangle
Table 1: Common base structures.

We prepare the structures based on a semi-automatic pipeline. We first
identify five types of common structures: symbol, bridge, arch, tower, and
rectangle (Table 1). Then, we manually create rules for the structure types.
For example, the arch’s rule is <Two Pillars: height > 3 and width < 2; Two
pillars distance > 3 and width < 3>; We model each surface in the target
structure as the graph node and use the adjacency as the edges. Then, we
represent the complexity of the structure by the number of graph-spanning
trees. To generate the structures, we randomly initialize the structure with 3
blocks. Then, we run a depth-first search following the pre-defined rules and
the complexity constraint. For the independent tasks, we use 24 structures, 16
are manually created and 8 are created based on the pipeline. The skill-
dependent structures share the same structures but with different inventories;
For goal-dependent tasks, we use 24 structures, 16 are manually created and 8
are created based on the pipeline.

###  A.2 Steps in User Manual

|
---|---
Step 1 | Step 2
|
Step 3 | Step 4
Table 2: Selected steps in the user manual.

The following steps are outlined in the user manual. We also attach the
figures of the steps in table 2.

  1. 1.

Users are assigned a unique participant ID and a general web URL for access.
Upon opening the website, they should enter their assigned participant code to
begin the experiments. The webpage will display the assigned tasks.

  2. 2.

Users can then click on each task displayed on the page to start. In these
tasks, users are required to collaborate with LLM agents to complete
structure-building activities.

  3. 3.

Upon task completion, CoBlock will automatically notify the user, who then
closes the page to proceed to the next task. If the user claims a task is
impossible to complete (possibly due to issues with the LLM agent), they can
click the submit button and provide a reason for the task’s incompletion.

  4. 4.

After finishing a task, the rightmost icon on the page will turn green,
indicating completion. Once all tasks are completed, a success code will
appear. Users should copy this code and submit it to Amazon Mechanical Turk
for payment.

###  A.3 Institutional Review Board

Our study is conducted under the approval of our university’s Institutional
Review Board (IRB). We did not collect any identity or demographic information
about the crowd-sourcing workers. We will disclose the IRB information after
the paper is accepted.

###  A.4 Workload Balance Evaluation

To evaluate the workload balance, we need first to compute the optimal
assignment of the workload balance. Shown in Algorithm 1, we first identify
the mutual blocks ($e^{m}$) shared between the two agents’ inventories
($e^{1}$ and $e^{2}$). Unique blocks for each agent are then determined by
subtracting these mutual blocks from their respective inventories, resulting
in $e^{1}_{unique}$ and $e^{2}_{unique}$. These unique blocks are directly
assigned to the corresponding agent. The core of the algorithm focuses on the
equitable distribution of mutual blocks. Blocks are assigned from $e^{m}$ to
the agent with the lesser total block count, ensuring a balanced workload.
This process continues until all mutual blocks are evenly distributed or
depleted. The algorithm thus optimizes task allocation by balancing the number
of blocks each agent is responsible for, in alignment to achieve an optimal
workload balance ($\gamma$) between the agents in constructing the target
structure ($G$).

Algorithm 1 Compute Optimal Workload Assignment

1:Input: Agent inventories $e^{1}$, $e^{2}$; Target structure $G$

2:Output: Optimal assignment of blocks to agents

3:procedure OptimalAssignment($e^{1}$, $e^{2}$, $G$)

4: $e^{m}\leftarrow e^{1}\cap e^{2}$ $\triangleright$ Identify mutual blocks

5: $e^{1}_{unique}\leftarrow e^{1}\setminus e^{m}$ $\triangleright$ Unique
blocks for Agent 1

6: $e^{2}_{unique}\leftarrow e^{2}\setminus e^{m}$ $\triangleright$ Unique
blocks for Agent 2

7: Assign $e^{1}_{unique}$ and $e^{2}_{unique}$ to corresponding agents

8: while $e^{m}$ is not empty do

9: Calculate $count^{1}$ and $count^{2}$ $\triangleright$ Current block count
for each agent

10: if $count^{1}\leq count^{2}$ then

11: Assign block from $e^{m}$ to Agent 1

12: Remove the assigned block from $e^{m}$

13: else if $count^{2}<count^{1}$ then

14: Assign block from $e^{m}$ to Agent 2

15: Remove the assigned block from $e^{m}$

16: end if

17: end while

18: return Assignment of $e^{1}_{unique}$, $e^{2}_{unique}$, and balanced
$e^{m}$ to agents

19:end procedure

##  Appendix B Prompt Text

In this appendix, we present the prompt used in our study. It is important to
note that the concepts included in our actual prompt vary from those discussed
in the main paper. To clarify these differences, we have outlined the
relationships between the concepts used in the actual prompt and those in the
paper in Table 3.

Prompt | Paper |  Explanation
---|---|---
Minecraft | CoBlock World |  Initially, CoBlock was designed to mimic the Minecraft-styled blocks world, therefore, we use Minecraft to help LLM agents to understand our environment.
Motive | Goal |  The motive is identical to the goal used in the paper.
Visual Motive | N/A |  During the early phase of the design, we aim to support the visual and textual description of the goals. Therefore, we also prompt LLM agents to understand the textual goals. However, in the experiments, we did not use the textual description, which will be explored in the future.
Textual Motive | N/A |
Theory-of-mind Modeling | Partner-State Modeling |  The theory-of-mind modeling refers to partner-state modeling and the understanding of the self status. In the paper, we highlight the partner-state modeling because the self-status modeling obviously exists in the first step of the prompt and the baseline prompt.
Table 3: Concept comparison in the prompt text and paper.

###  B.1 Task Description Prompt

The task description is presented to all LLM agents of both the baseline
prompt and our approach. It details the environment input/output formats to
ensure the LLM agents understand our CoBlock environment. The task description
consists of the task summary, world state, inventory, message, and goal
formats.

Task Summary
I want you to act as a Minecraft player collaborating with another agent to
build a structure with a blueprint. You need to use the following commands to
interact with the Minecraft world:
# Place a red block at the position of (0, 1, 1).
place$\\_$block(block$\\_$type=red, pos=(0,1,1))
# chat with your partner
send$\\_$message(message=“Hello, partner”)
# destroy the block at the position of (3, 1, 3)
break$\\_$block(pos=(3, 1, 3))

World State Format
At each turn, you will receive the following information:
# World state: You will get the position of all blocks in the world in the
following format:
# Please note that the ground is the y=1 plane.
<World>
<block block$\\_$type =“red”, pos=(0, 1, 2)> <block block$\\_$type =“yellow”,
pos=(0, 1, 3)> <block block$\\_$type =“purple”, pos=(0, 1, 4)> <World>

Inventory Format
# You will get your inventory in the following format: (each time you place a
block from the inventory in the world, you will lose it in the inventory)
<Inventory>
<block block$\\_$type =“red”, count=3>
<block block$\\_$type =“yellow”, count=3>
<Inventory>

Message Format
# You will get the message history between you (ChatGPT) and your partner in
the following format:
<Dialogue>
<sender=“ChatGPT”, message=“Hello!”>
<sender=“Partner”, message=“Hi, I am your partner!”>
<Dialogue>

The goal is represented through a list of blocks that need to be constructed.
In our system development, we aim to represent goals using both textual and
visual modalities. However, this paper focuses on the visual representation of
goals. The goal is articulated as a motive in our prompts. The visual motive
is delineated by an optional description of the target structure and a
comprehensive list of the blocks constituting that structure. It is important
to note that although the structure’s shape must adhere to specified
guidelines, its location can be decided by the agent.

Goal (Motive) Format
<Motives>
# You will get a list of motives you need to fulfill. There can be two types
of motives, i.e. visual and textual.
<Motives>
<VisualMotive>
<Description> A simple two-layer structure consisting of red and yellow blocks
</Description>
<block block$\\_$type =“red”, pos=(0, 1, 2)> <block block$\\_$type =“red”,
pos=(1, 1, 2)> <block block$\\_$type =“red”, pos=(0, 1, 3)> <block
block$\\_$type =“red”, pos=(1, 1, 3)> <block block$\\_$type =“yellow”, pos=(0,
2, 2)> <block block$\\_$type =“yellow”, pos=(1, 2, 2)> <block block$\\_$type
=“red”, pos=(0, 2, 3)> <block block$\\_$type =“yellow”, pos=(1, 2, 3)>
</VisualMotive>

###  B.2 In-Context Examples

Below, we present the in-context examples used in our prompt. Since CoBlock is
a multi-round game, our examples span three rounds, enabling LLM agents to
plan across multiple rounds. Please notice that the prompt will be provided
after the task description when querying LLMs.

Round 1 Input
<Input>
<Motive><TextualMotive text="Construct a bridge with a span of 12 blocks using
green blocks. Place two green block pillars, each consisting of 4 blocks. Add
4 yellow blocks as the bridge surface. ” /> </Motive>
<World>
</World>
<Inventory>
<block $block\\_type$=“yellow”, count=20>
<block $block\\_type$=“green”, count=20>
<block $block\\_type$=“purple”, count=20>
</Inventory>
<Dialogue>
</Dialogue>
</Input>

Round 1 Expected Output
# Partner Modelling
# Long-term goal: Unknown
# Short-term goal: Unknown
# Partner inventory: Unknown
# Explanation: I do not know anything about my partner.
# Self Modelling
# Long-term goal: creating the target structure
# Short-term goal: Build the green pillars
# My inventory: [yellow: 20, green: 20, purple: 20]
# Explanation: Since my long-term goal is to build the bridge, I need to
decompose it into different small parts. The first part I can build is the
pillars.
# Since I do not have any access to the partner’s information, I need to let
him know my intention and inventory when asking for it.
send$\\_$message(message=“Hi, I need to build a bridge with the yellow deck
and green pillars. I have green, yellow and purple. How about you?”)

Round 2 Input
<Input>
<Motives>
<TextualMotive text=“Construct a bridge with a span of 8 blocks and a width of
3 blocks using yellow blocks. Place two green block pillars, each consisting
of 4 blocks. Add 4 yellow blocks as the bridge surface.” />

</Motives> <World> <block block$\\_$type =“red”, pos=(0, 1, 2)> <block
block$\\_$type =“red”, pos=(1, 1, 2)> <block block$\\_$type =“red”, pos=(0, 1,
3)> <block block$\\_$type =“red”, pos=(1, 1, 3)> </World>
<Inventory>
<block block$\\_$type =“yellow”, count=20> <block block$\\_$type =“green”,
count=20> <block block$\\_$type =“purple”, count=20> </Inventory>
<Dialogue> <chat sender=“Agent 1”, message=“Hi, I need to build a bridge with
the yellow deck and green pillars. I have green, yellow and purple. How about
you?”/> <chat sender=“Agent 2”, message=“Hi, I have red, green, and black. I
need to build the black fence upon your deck.”/> </Dialogue>
</Input>

Round 2 Expected Output
# Partner Modelling
# Long-term goal: Build the fence on the deck
# Short-term goal: Wait until the fence is built
# Partner inventory: [red: unknown, green: unknown, black: unknown]
# Explanation: I have extracted the partner information from the partner’s
response.
# Self Modelling
# Long-term goal: creating the target structure
# Short-term goal: Build the green pillars. Ask for the partner’s help with
the pillars
# My inventory: [green: 20, red: 20, purple: 20]
# Explanation: Since my long-term goal is to build the bridge, I need to
decompose it into different small parts. The first part I can build is the
pillars. I can ask for the partner’s help because it has the green block in
the inventory.
$send\\_message$(message="Hi, I need to build the two pillars first. My bridge
spans 12 and I need to have 2 pillars. So it would be reasonable to put the
two pillars at (4, 0, 0) and (8, 0, 0). I will start with the (4, 0, 0) one
and could you please build the pillar at (8, 0, 0) ?")
# Since the motive does not specify the locations of the pillars, I need to
first decide them. Given the fact that the partner is waiting and can help me
build the pillar, it is also reasonable to ask for its help.
# Build the yellow pillar on (4, 0, 0).
$place\\_block$($block\\_type$="yellow", pos=(4, 0, 0))

Round 3 Input
<Input>
<Motives>
<TextualMotive text="Construct a bridge with a span of 8 blocks and a width of
3 blocks using yellow blocks. Place two green block pillars, each consisting
of 4 blocks. Add 4 yellow blocks as the bridge surface. ” />
</Motives>
<World>
<block block$\\_$type =“yellow”, pos=(4, 0, 0)> <block block$\\_$type
=“yellow”, pos=(4, 1, 0)> <block block$\\_$type =“yellow”, pos=(4, 2, 0)>
<block block$\\_$type =“yellow”, pos=(8, 1, 0)> <block block$\\_$type
=“yellow”, pos=(8, 2, 0)> <block block$\\_$type =“yellow”, pos=(8, 3, 0)>
</World>
<Inventory>
<block block$\\_$type =“yellow”, count=20> <block block$\\_$type =“green”,
count=20> <block block$\\_$type =“purple”, count=20> </Inventory>
<Dialogue>
<chat sender=“Agent 1", message="Hi, I need to build a bridge with the yellow
deck and green pillars. I have green, yellow and purple. How about you?”/>
<chat sender=“Agent 2", message="Hi, I have red, green and black. I need to
build a black fence upon your deck”/>
<chat sender=“Agent 3", message="Sure, I will build the yellow pillar as you
requested.”/>
</Dialogue>
</Input>

Round 3 Expected Output
# Partner Modelling
# Long-term goal: Build the fence on the deck
# Short-term goal: Building the pillar at (8, 0, 0) as I requested.
# Partner inventory: [red: unknown, green: unknown, black: unknown]
# Explanation: I have extracted the partner’s information from the partner’s
response.
# Self Modelling
# Long-term goal: creating the target structure
# Short-term goal: Build the yellow pillar on (4, 0, 0)
# Explanation: Since the yellow pillar has not been finished, I need to
continue building it.
$place\\_block$($block\\_type$=“yellow”, pos=(4, 4, 0))
# Build the last block of the pillar as it is my short-term goal.
$place\\_block$($block\\_type$=“yellow”, pos=(4, 0, 0))
$send\\_message$(message“I have completed my pillar. Then I will start
building the green deck.!”)
$place\\_block$($block\\_type$=“green”, pos=(4, 5, 0))
$place\\_block$($block\\_type$=“green”, pos=(3, 5, 0))
# Since I have finished the pillar and can assume my partner will finish his
assigned pillar. I can start building the green deck.