text:
\section{Experimental evaluation}
\input{tex/discussion}

\section*{Acknowledgment}
This research was supported by Ahold Delhaize. All content represents the opinion of the author(s), which is not necessarily shared or endorsed by their respective employers and/or sponsors.

\appendices
\input{tex/appendix}

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi

\section{Theoretical analysis}
\label{sec:Analysis}
\subsection{Analysis of convergence}
\label{sec:Analysis_DoA}
We provide a theoretical analysis of the proposed control architecture. There are two possible scenarios that might occur at run-time. Specifically, the environment might or might not differ from what has been planned offline trough BTs. These two cases are analysed in the following to study the convergence to the desired goal of our proposed solution.

\subsubsection{The dynamic environment IS as planned}
In a nominal execution, where the environment in which a robot is operating is the same as the one at planning time, there is a one to one equivalence between our approach and a classical BT formulation. This follows directly by the fact that the BT is defined according to Section \ref{sec:subsecPlanOffline}, so each subsequent state is achievable by means of one single action. At any point of the task the robot finds itself in the planned state and has only one preference over the next state given by the BT through $\bm C$. The only action which can minimise the expected free-energy is the one used during offline planning. In a nominal case, then, we maintain all the properties of BTs, which are well explained in \cite{Colledanchise2017}. In particular, the behavior will be Finite Time Successful (FTS) \cite{Colledanchise2017} if the atomic actions are assumed to return success after finite time. Note that so far we did not consider actions with the same postconditions. However, in this case Algorithm~\ref{alg:idea} would sequentially try all the alternatives following the given order at design time. This can be improved for instance by making use of semantic knowledge at runtime to inform the action selection process about preferences over actions to achieve the same outcome. This information can be stored for instance in a knowledge base and can be used to parametrize the generative model for active inference.

\subsubsection{The dynamic environment IS NOT as planned}
The most interesting case is when a subsequent desired state is not reachable as initially planned. As explained before, in such a case we push the missing preconditions of the selected action into the current prior $\bm C$ to locally and temporarily modify the goal. We analyse this idea in terms of sequential controllers (or actions) composition as in \cite{Burridge1999}, and we show how Algorithm~\ref{alg:idea} generates a policy that will eventually converge to the initial goal. First of all we provide some assumptions and definitions that will be useful for the analysis.
\paragraph*{Assumption 1} The action templates with pre- and postconditions provided to the agent are correct;
\paragraph*{Assumption 2} A given desired goal (or a prior $\bm C$) is achievable by at least one atomic action;
\paragraph*{Definition 1} The domain of attraction (DoA) of an action $a_i$ is defined as the set of its preconditions. The DoA of $a_i$ is indicated as $\mathcal{D}(a_i)$;
\paragraph*{Definition 2} We say that an action $a_1$ \textit{prepares} action $a_2$ if the postconditions $\mathcal{P}_c$ of $a_2$ lie within the DoA of $a_1$, so $\mathcal{P}_c(a_2)\subseteq \mathcal{D}(a_1)$;

Following Algorithm~\ref{alg:idea} each time a prior leaf node is ticked in the BT, active inference is used to define a sequence of actions to bring the current state towards the goal. It is sufficient to show, then, that the asymptotically stable equilibrium of a generic generated sequence is the initial given goal.

\begin{lemma}
\label{lemma:2}
Let $\mathcal{L}_c$ be the current logic state of the world, and $\mathcal{A}$ the set of available actions. An action $a_i\in\mathcal{A}$ can only be executed within its DoA, so when $\mathcal{D}(a_i)\subseteq \mathcal{L}_c$. Let us assume that the goal $\bm C$ is a postcondition of an action $a_1$ such that $\mathcal{P}_c(a_1)= \bm C$, and that $\mathcal{L}_c\ne \bm C$. If $\mathcal{D}(a_1)\not\subseteq \mathcal{L}_c$, Algorithm~\ref{alg:idea} generates a sequence $\pi=\{a_1,\dots,a_N\}$ with domain of attraction $\mathcal{D}(\pi)$ according to the steps below.
\begin{enumerate}
    \item Let the initial sequence contain $a_1\in\mathcal{A}$, $\pi(1)=\{a_1\}$, $\mathcal{D}(\pi)=\mathcal{D}(a_1)$, set $N = 1$ and $\pi(N)=\mathcal{P}_c(a_1)$
    \item Remove $a_N$ from the available actions, and add unmet preconditions $\bm C =
    \bm C\cup\mathcal{D}(a_N)$
    \item Select $a_{N+1}$ through active inference (Algorithm~\ref{alg:AIC}). Then,  $a_{N+1}$ prepares  $a_{N}$ by construction, $\pi(N+1)=\pi(N)\cup \{a_N\}$, $\mathcal{D}_{N+1}(\pi)=\mathcal{D}_{N}(\pi)\cup\mathcal{D}(a_{N+1})$, and $N = N+1$
    \item Repeat 2, 3 until $\mathcal{D}(a_N)\subseteq \mathcal{L}_c$ \texttt{OR $a_N==$ Idle}
\end{enumerate}
If $\mathcal{D}(a_N)\subseteq \mathcal{L}_c$ and $\mathcal{D}(a_1) \subseteq \bigcup \mathcal{P}_c(\pi \backslash a_1)$, the sequential composition $\pi$ stabilizes the system at the given desired state $\bm C$. If $a_i\in\mathcal{A}$ are FTS, then $\pi$ is FTS.
\end{lemma}

\begin{proof}
Since $\mathcal{D}(a_N)\subseteq \mathcal{L}_c$ and $\mathcal{P}_c(a_N)\subseteq\mathcal{D}(a_{N-1})$, it follows that $\mathcal{L}_c$ is moving towards $\bm C$. Moreover, when $\mathcal{D}(a_1) \subseteq \bigcup \mathcal{P}_c(\pi \backslash a_1)$, after action completion $\mathcal{L}_c\equiv \bm C$ since by definition $\mathcal{P}_c(a_1)= \bm C$.
\end{proof}

Note that if $\mathcal{D}(a_N)\subseteq \mathcal{L}_c$ does not hold after sampling all available actions, it means that the algorithm is unable to find a set of actions which can satisfy the preconditions of the initial planned action. This situation is a major failure which need to be handled by the overall BT.
\textit{Lemma} \ref{lemma:2} is a direct consequence of the sequential behavior composition of FTS actions where each action has effects within the DoA of the action below. The asymptotically stable equilibrium of each controller is either the goal $\bm C$, or it is within the region of attraction of another action earlier in the sequence, see \cite{Colledanchise2017,Burridge1999, Najafi2015}. One can visualize the idea of sequential composition in Fig.~\ref{fig:funnels}.

\begin{figure}[!htb]
    \centering
    \includegraphics[width=0.43\textwidth]{images/funnels.pdf}
    \caption{DoA of different controllers around the current logical state $\mathcal{L}_c$, as well as their postconditions within the DoA of the controller below.}
    \label{fig:funnels}
\end{figure}

\subsection{Analysis of robustness}
It is not easy to find a common and objective definition of robustness to analyse the characteristics of algorithms for task execution. One possible way is to describe robustness in terms of domains or regions of attraction as in past work \cite{Burridge1999,Colledanchise2017}. When considering task planning and execution with classical behavior trees, often these regions of attraction are defined offline leading to a complex and extensive analysis of the possible contingencies that might eventually happen \cite{Colledanchise2017}, and these are specific to each different task. Alternatively, adapting the region of attraction requires either re-planning \cite{Paxton2019} or dynamic BT expansion \cite{Colledanchise2019}.
Our solution does not require to design complex and large regions of attractions offline, rather these are automatically generated by Algorithm~\ref{alg:idea}, according to the minimisation of free-energy. We then measure robustness according to the size of these regions, such that a robot can achieve a desired goal from a plurality of initial conditions. With our approach we achieve robust behavior by \textit{dynamically} generating a suitable region of attraction which is biased towards a desired goal. We then cover only the necessary region in order to be able to steer the current state to the desired goal, changing prior preferences at run-time.

\begin{corollary}
\label{cor:robustness}
When an executable action $a_N$ is found during task execution such that $\pi = \{a_1,\dots,a_N\}$, Algorithm~\ref{alg:idea} has created a region of attraction towards a given goal that includes the current state $\mathcal{L}_c$. If $\mathcal{D}(a_1) \subseteq \bigcup \mathcal{P}_c(\pi \backslash a_1)$ the region is asymptotically stable.
\end{corollary}

\begin{proof}
The corollary follows simply from \textit{Lemma} \ref{lemma:2}.
\end{proof}

\begin{example} \textit{Let us assume that Algorithm~\ref{alg:idea} produced a policy $\pi=\{a_1,\ a_2\}$, a set of FTS actions, where $a_2$ is executable so $\mathcal{D}(a_2)\subseteq\mathcal{L}_c$, and its effects are such that $\mathcal{P}_c(a_2)\equiv \mathcal{D}(a_1)$. Since $a_2$ is FTS, after a certain running time $\mathcal{P}_c(a_2)\subseteq \mathcal{L}_c$. The next tick after the effects of $a_2$ took place, $\pi = \{a_1\}$ where this time $a_1$ is executable since $\mathcal{D}(a_1)\subseteq\mathcal{L}_c$ and $\mathcal{P}_c(a_1)= \bm C$. The overall goal is then achieved in finite time.}
\end{example}

Instead of looking for globally asymptotically stable policies from each initial state to each possible goal, which can be unfeasible or at least very hard \cite{Burridge1999}, we define smaller regions of attractions dynamically, according to current state and goal.

\section{Generative models}
\label{sec:AppendixP}
In active inference \cite{friston2017active} the generative model is chosen to be a Markov process which allows to infer the states of the environment and to predict the effects of actions as well as future observations. This can very well be expressed as a joint probability distribution $P(\bar{o},\bar{s},\bm \eta,\pi)$, where $\bar{o}$ is a sequence of observations, $\bar{s}$ is a sequence of states, $\bm \eta$ represents model parameters, and $\pi$ is a policy. Using the chain rule, this joint probability is rewritten as:
\begin{equation}
   P(\bar{o},\bar{s},\bm \eta,\pi) = P(\bar{o}|\bar{s},\bm \eta,\pi)P(\bar{s}|\bm \eta,\pi)P(\bm \eta|\pi)P(\pi)
\end{equation}
Note that $\bar{o}$ is conditionally independent from $\bm \eta$ and $\pi$ given $\bar{s}$. In addition, under the Markov property, the next state and current observations depend only on the current state:
\begin{equation}
     P(\bar{o}|\bar{s},\bm \eta, \pi) = \prod_{\tau=1}^T{P(o_\tau|s_\tau)}
\end{equation}
The model is further simplified considering that $\bar{s}$ and $\bm \eta$ are conditionally independent given $\pi$:
\begin{equation}
    P(\bar{s}|\bm \eta,\pi) = \prod_{\tau=1}^T{P(s_\tau|s_{\tau-1}, \pi)}
\end{equation}
Finally, consider the model parameters explicitly:
\begin{align}
    \nonumber
    &P(\bar{o},\bar{s},\bm \eta,\pi) = P(\bar{o},\bar{s},\bm A,\bm B,\bm D,\pi) =  &\\
    & P(\pi)P(\bm A)P(\bm B)P(\bm D)\prod_{\tau=1}^T P(s_\tau|s_{\tau-1},\pi)P(o_\tau|s_\tau) &
\end{align}
The parameters in the joint distribution include $(\bm A,\bm B,\bm D)$. In details:
\begin{itemize}
    \item $\bm A$ is the likelihood matrix. It indicates the probability of outcomes being observed given a specific state. Each column $i$ of $\bm A$ is a categorical distribution $P(o_t^i|s_t^i)=Cat(\bm A_i)$. In general $P(o_t|s_t)=Cat(\bm A)$.
    \item $\bm B_{a_t}$ is the transition matrix. It indicates the probability of state transition under action $a_t$. The columns of $\bm B_{a_t}$ are categorical distributions which define the probability of being in state $s_{t+1}$ while applying $a_t$ from state $s_t$. $\bm B_{a_t}$ is also indicated simply as $\bm B$, and $P(s_{t+1}|s_t,\ a_t)=\bm B$.
    \item $\bm D$ defines the probability or belief about the initial state at $t=1$. So $P(s_1|s_0)=Cat(\bm D)$.
    \item $\pi$ contains policies that are action sequences over a time horizon $T$. $\bm \pi$ is the posterior expectation, a vector holding the probability of policies. These probabilities depend on the expected free-energy in future time steps under policies given the current belief: $P(\pi) = \sigma(-G(\pi))$. Here, $\sigma$ indicates the softmax function used to normalise probabilities.
\end{itemize}
Given the generative model above, we are interested in finding the posterior about hidden causes of sensory data. For the sake of these derivations, we consider that the parameters associated with the task are known and do not introduce uncertainty. Using Bayes rule:
\begin{equation}
    \label{eq:app_bayes}
    P(\bar{s},\pi|\bar{o}) = \frac{P(\bar{o}|\bar{s},\pi)P(\bar{s},\pi)}{P(\bar{o})}
\end{equation}
Computing the model evidence $P(\bar{o})$ exactly is a well known and often intractable problem in Bayesian statistics. The exact posterior is then computed minimising the Kullback-Leibler divergence ($D_{KL}$, or KL-Divergence) with respect to an approximate posterior distribution $Q(\bar{s},\pi)$. Doing so, we can define the free-energy as a functional of approximate posterior beliefs which result in an upper bound on surprise. By definition $D_{KL}$ is a non-negative quantity given by the expectation of the logarithmic difference between $Q(\bar{s},\pi)$ and $P(\bar{s},\pi|\bar{o})$. Applying the KL-Divergence:
\begin{align}
\label{eq:app_dkl}
\nonumber
    &D_{KL}\left[ Q(\bar{s},\pi)||P(\bar{s},\pi|\bar{o}) \right] = & \\
    &\mathbb{E}_{Q(\bar{s},\pi)}\left[\ln{Q(\bar{s},\pi)}-\ln{P(\bar{s},\pi|\bar{o})}\right]\geq 0&
\end{align}
$D_{KL}$ is the information loss when $Q$ is used instead of $P$. Considering equation \eqref{eq:app_bayes} and the chain rule, equation \eqref{eq:app_dkl} can be rewritten as:
\begin{equation}
    D_{KL}\left[\cdot\right] = \mathbb{E}_{Q(\bar{s},\pi)}\left[    \ln{Q(\bar{s},\pi)}-\ln{\frac{P(\bar{o},\bar{s},\pi)}{P(\bar{o})}}
\right]
\end{equation}
And finally:
\begin{equation}
    \label{eq:app_Fupper}
    D_{KL}\left[\cdot\right] = \underbrace{\mathbb{E}_{Q(\bar{s},\pi)}\left[\ln{Q(\bar{s},\pi)}-\ln{P(\bar{o},\bar{s},\pi)}\right]}_{F\left[Q(\bar{s},\pi)\right]}+\ln{P(\bar{o})}
\end{equation}
We have just defined an upper bound on surprise, the free-energy:
\begin{equation}
    F\left[Q(\bar{s},\pi)\right] \geq - \ln{P(\bar{o})}
\end{equation}

\section{Variational Free-energy}
\label{sec:AppendixF}
To fully characterize the free-energy in equation \eqref{eq:app_Fupper}, we need to specify a form for the approximate posterior $Q(\bar{s},\pi)$. There are different ways to choose a family of probability distributions \cite{schwobel2018active}, compromising between complexity and accuracy of the approximation. In this work we choose the mean-field approximation. It holds:
\begin{equation}
    Q(\bar{s},\pi) = Q(\bar{s}|\pi)Q(\pi) = Q(\pi)\prod_{\tau=1}^TQ(s_\tau|\pi)
\end{equation}
Under mean-field approximation, the policy dependant states at each time step are approximately independent of the states at any other time step. We can now find an expression for the variational free-energy. Considering the mean-field approximation, and the generative model with known task-associated parameters as:
\begin{equation}
    P(\bar{o},\bar{s},\pi) = P(\pi)\prod_{\tau=1}^T P(s_\tau|s_{\tau-1},\pi)P(o_\tau|s_\tau)
\end{equation}
we can write:
\begin{eqnarray}
    \nonumber
    F\left[Q(\bar{s},\pi)\right] = \mathbb{E}_{Q(\bar{s},\pi)}\bigg[\ln{Q(\pi)} + \sum_{\tau=1}^T\ln{Q(s_\tau|\pi)}\\
    -\ln{P(\pi)} -\sum_{\tau=1}^T\ln{P(s_\tau|s_{\tau-1},\pi)} -\sum_{\tau=1}^T\ln{P(o_\tau|s_\tau)}\bigg]
\end{eqnarray}
Since $Q(\bar{s},\pi) = Q(\bar{s}|\pi)Q(\pi)$, and since the expectation of a sum is the sum of the expectation, we can write:
\begin{equation}
\label{eq:app_Ftot}
    F\left[\cdot\right] = D_{KL}\left[Q(\pi)||P(\pi)\right] +  \mathbb{E}_{Q(\pi)}\left[F(\pi)\left[Q(\bar{s}|\pi)\right] \right]
\end{equation}
where
\begin{align}
    \label{eq:app_Fpi}
    \nonumber
    & F(\pi)\left[Q(\bar{s}|\pi)\right] = \mathbb{E}_{Q(\bar{s}|\pi)}\bigg[\sum_{\tau=1}^T\ln{Q(s_\tau|\pi)}&\\
    &-\sum_{\tau=1}^T\ln{P(s_\tau|s_{t-\tau}, \pi)} -\sum_{\tau=1}^T\ln{P(o_\tau|s_\tau)}\bigg]&
\end{align}
One can notice that $F(\pi)$ is accumulated over time, or in other word it is the sum of free-energies over time and policies:
\begin{equation}
\label{eq:app_Fpitau}
    F(\pi) = \sum_{\tau=1}^TF(\pi,\tau)
\end{equation}
Substituting the agent's belief about the current state at time $\tau$ given $\pi$ (i.e. $Q(\bar{s}|\pi)$), with its sufficient statistics $\bm s_\tau^\pi$, we obtain a matrix form for $F(\pi,\tau)$ that we can compute given the generative model:
\begin{eqnarray}
    F(\pi) = \sum_{\tau=1}^T \bm s_\tau^\pi \cdot \bigg[\ln{\bm s_\tau^\pi} - \ln{(\bm B_{\tau-1}^{\pi})}\bm s_{\tau-1}^{\pi} - \ln{\bm A}\cdot \bm o_\tau \bigg]
\end{eqnarray}
Given a policy $\pi$, the probability of state transition $P(s_\tau|s_{t-\tau},\pi)$ is given by the transition matrix under policy $\pi$ at time $\tau$, multiplied by the probability of the state at the previous time step. In the special case of $\tau=1$, we can write:
\begin{equation}
    F(\pi,1) =  \bm s_1^\pi \cdot \big[\ln{\bm s_1^\pi} - \ln{\bm D} - \ln{\bm A}\cdot \bm o_1 \big]
\end{equation}
Finally, we can compute the expectation of the policy dependant variational free-energy $F(\pi)$ as
\begin{equation}
   \mathbb{E}_{Q(\pi)} \big[F(\pi)\big] = \bm\pi \cdot \bm F_{=\pi}
\end{equation}
Where we indicate $\bm F_{\pi} = (F(\pi_1),F(\pi_2)...)$ for every allowable policy.

To derive state and policy updates which minimise free-energy, $F$ in equation \eqref{eq:app_Ftot} is partially differentiated and set to zero, as we will see in the next appendixes.
\section{State estimation}
\label{sec:AppendixS}
We differentiate $F$ with respect to the sufficient statistics of the probability distribution of the states. Note that the only part of $F$ dependent on the states is $F(\pi)$. Then:
\begin{align}
    \nonumber
    &\frac{\partial F}{\partial\bm s_{\tau}^{\pi}} = \frac{\partial F}{\partial F(\pi)}\frac{\partial F(\pi)}{\partial\bm s_{\tau}^{\pi}} = \bm\pi \cdot \big[ \bm 1 + \ln{\bm s_\tau^\pi}
    - \ln{(\bm B_{\tau-1}^{\pi})}\bm s_{\tau-1}^{\pi} & \\
    &- \ln{(\bm B_{\tau}^{\pi})}\cdot \bm s_{\tau+1}^{\pi}
    - \ln{\bm A}\cdot \bm o_\tau \big]&
\end{align}
Setting the gradient to zero and using the softmax function to normalize the probability distribution over states:
\begin{align}
    \nonumber
    &\frac{\partial F}{\partial\bm s_{\tau}^{\pi}} = 0 \Rightarrow  &\\
    &\bm s_{\tau}^{\pi} = \sigma(\ln{(\bm B_{\tau-1}^{\pi})}\bm s_{\tau-1}^{\pi}
    + \ln{(\bm B_{\tau}^{\pi})}\cdot \bm s_{\tau+1}^{\pi}
    + \ln{\bm A}\cdot \bm o_\tau)&
\end{align}
Note that the softmax function is insensitive to the constant $\bm 1$. Also, for $\tau=1$ the term $\ln{(\bm B_{\tau-1}^{\pi})}\bm s_{\tau-1}^{\pi}$ is replaced by $\bm D$. Finally, $\ln{\bm A}\cdot \bm o_\tau$ contributes only to past and present time steps, so for this term is null for $t<\tau\leq T$ since those observations are still to be received.
\section{Expected Free-energy}
\label{sec:AppendixG}
We indicate with  $G(\pi)$ the expected free-energy obtained over future time steps until the time horizon $T$ while following a policy $\pi$. Basically, this is the variational free-energy of future trajectories which measures the plausibility of policies according to future predicted outcomes \cite{sajid2021active}. To compute it we take the expectation of variational free-energy under the posterior predictive distribution $P(o_\tau|s_\tau)$. Following \cite{sajid2021active} we can write:
\begin{equation}
    G(\pi) = \sum_{\tau=t+1}^T G(\pi,\tau)
\end{equation}
then:
\begin{eqnarray}
\nonumber
    G(\pi,\tau) = \mathbb{E}_{\tilde{Q}}\big[\ln{Q(s_\tau|\pi)}- \ln{P(o_\tau,s_\tau|s_{\tau-1})}\big]\\
   = \mathbb{E}_{\tilde{Q}}\big[\ln{Q(s_\tau|\pi)}- \ln{P(s_\tau|o_\tau,s_{\tau-1})} - \ln{P(o_\tau)} \big]
\end{eqnarray}
where $\tilde{Q} = P(o_\tau|s_\tau)Q(s_\tau|\pi)$.
The expected free energy is then:
\begin{equation}
    G(\pi,\tau) \geq  \mathbb{E}_{\tilde{Q}}\big[\ln{Q(s_\tau|\pi)}- \ln{Q(s_\tau|o_\tau,s_{\tau-1}, \pi)} - \ln{P(o_\tau)} \big]
\end{equation}
Equivalently, we can express the expected free-energy in terms of preferred outcomes \cite{DaCosta2020}:
\begin{equation}
    G(\pi,\tau) =  \mathbb{E}_{\tilde{Q}}\big[\ln{Q(o_\tau|\pi)}- \ln{Q(o_\tau|s_\tau, s_{\tau-1}, \pi)-\ln{P(o_\tau)}}\big]
\end{equation}
Making use of $Q(o_\tau|s_\tau,\pi)=P(o_\tau|s_\tau)$ since the predicted outcomes in the future are only based on $\bm A$ which is policy independent given $s_\tau$, we have:
\begin{equation}
\label{eq:app_G}
    G(\pi,\tau) = \underbrace{D_{KL}\left[Q(o_\tau|\pi)||P(o_\tau)\right]}_{Expected\  cost}+\underbrace{\mathbb{E}_{Q(s_\tau|\pi)}\left[H(P(o_\tau|s_\tau))\right]}_{Expected\ ambiguity}
\end{equation}
were $H[P(o_\tau|s_\tau)]=\mathbb{E}_{P(o_\tau|s_\tau)}\left[-\ln{P(o_\tau|s_\tau)}\right]$ is the entropy. We are now ready to express the expected free-energy in matrix form, such that we can compute it. From the previous equation one can notice that policy selection aims at minimizing the expected cost and ambiguity. The latter relates to the uncertainty about future outcomes given hidden states. In a sense, policies tend to bring the agent to future states that generate unambiguous information over states. On the other hand, the cost is the difference between predicted and prior beliefs about final states. Policy are more likely if they minimize cost, so lead to outcomes which match prior desires. Minimising $G$ leads to both exploitative (cost minimizing) and explorative (ambiguity minimizing) behavior. This results in a balance between goal oriented and novelty seeking behaviours.

Substituting the sufficient statistics in equation \eqref{eq:app_G}, and recalling that the generative model specifies $\ln P(o_\tau) = \bm C$
\begin{equation}
     G(\pi,\tau) = \bm o_\tau^\pi\cdot \left[\ln{\bm o_\tau^\pi}-\bm C\right] + \bm s_\tau^\pi\cdot\bm A\cdot \ln{\bm A}
\end{equation}

\section{Updating policy distribution}
\label{sec:AppendixPi}
The update rule for the distribution over possible policies follows directly from the definition of the variational free-energy:
\begin{equation}
F\left[\cdot\right] = D_{KL}\left[Q(\pi)||P(\pi)\right] +  \bm \pi \cdot \bm F_\pi
\end{equation}
The first term of the equation above can be further specified as:
\begin{equation}
    D_{KL}\left[Q(\pi)||P(\pi)\right] = \mathbb{E}_{Q(\pi)}\left[\ln{Q(\pi)}-\ln{P(\pi)}\right]
\end{equation}
Recalling that the generative model defines $P(\pi)=\sigma(-G(\pi))$, it results:

\begin{eqnarray}
\nonumber
    D_{KL}\left[Q(\pi)||P(\pi)\right] = \bm \pi \cdot (\ln{\bm \pi} + \bm G_\pi) + \\ \mathbb{E}_{Q(\pi)}\left[\ln{Q(\pi)}-\ln{\sum_i e^{G(\pi_i)}}\right]
\end{eqnarray}

Taking the gradient with respect to $\bm \pi$:
\begin{equation}
    \frac{\partial F}{\partial \bm\pi} = \ln{\bm \pi} + \bm G_\pi + \bm F_\pi + \bm 1
\end{equation}
where $\bm F_\pi = (F(\pi_1),F(\pi_2),...)$ and $\bm G_\pi = (G(\pi_1),G(\pi_2),...)$
Finally, setting the gradient to zero and normalizing through softmax, the distribution over policies is obtained:
\begin{equation}
    \bm \pi = \sigma(-\bm G_\pi - \bm F_\pi)
\end{equation}
The policy that an agent should pursue is the most likely one.

\section{Background on Active Inference and BTs}
\label{sec:Background}
\subsection{Background on Active Inference}
Active inference provides a powerful architecture for the creation of reactive agents which continuously update their beliefs about the world and act on it, to match specific desires. This behavior is automatically generated through free-energy minimization, which provides a metric for meaningful decision making in the environment.
Active inference provides a unifying theory for perception, action, decision-making and learning in biological or artificial agents \cite{DaCosta2020}. The core idea is that these processes can be described in terms of optimization of two complementary objective functions, namely the variational free-energy $F$, and the expected free-energy $G$. Creatures are assumed to have a set of sensory observations $o$ and an internal generative model to represent the world which is used to build  internal probabilistic representations, or Bayesian beliefs, of the environment's dynamics. Agents can also act on the environment to change its states, and thus the sensory observations. External states are internally represented through the so called hidden states $s$. Variational free-energy measures the fit between the internal model and past and current sensory observations, while expected free-energy scores future possible courses of action according to prior preferences. In this subsection we report
the necessary theory for planning and decision making with discrete active inference from the vast literature. All the necessary mathematical derivations are added in the appendix.

\subsubsection{Discrete state-space generative models}
Usually, agents do not have access to the true states but they can only perceive the world via possibly noisy sensory observations \cite{friston2017active, friston2017graphical}, and have an internal representation, or model, of the world. The problem can then be framed as a variant of a Markov decision process where the internal generative model is a joint probability distribution over possible hidden states and sensory observations. This is used to predict sensory data, and to infer the causes of these data \cite{friston2017active}:
\begin{align}
    \nonumber
    & P(\bar{o},\bar{s},\bm A,\bm B,\bm D,\pi) = &\\
    & P(\pi)P(\bm A)P(\bm B)P(\bm D)\prod_{\tau=1}^T P(s_\tau|s_{\tau-1},\pi)P(o_\tau|s_\tau)&
    \label{eq:factorizedModel}
\end{align}
This factorization takes into account the Markov property, so the next state and current observation depend only on the current state. In eq.~\eqref{eq:factorizedModel}, $\bar{o}$ and $\bar{s}$ represent sequences of observations and states from time $\tau=1$ to the current time $t$. Regarding the parameters of the model: $\bm A$ is the likelihood matrix, so the probability of an outcome to be observed given a specific state; $\bm B_{a_t}$, or simply $\bm B$, is the transition matrix, so the probability of state $s_{t+1}$ while applying action $a_t$ from state $s_t$; $\bm D$ is the probability or initial belief about the state at $\tau=1$. Each column of $\bm A$, $\bm B$, $\bm D$ is a categorical distributions, $Cat(\cdot)$; finally, $\pi$ is a policy, defined as sequence of actions over a time horizon $T$. The full derivation of the generative model in eq.~\eqref{eq:factorizedModel}, the assumptions under its factorization, and how this joint probability is used to define the free-energy $F$ as an upper bound on surprise, can be found in Appendix \ref{sec:AppendixP}.
\subsubsection{Variational (negative) Free-energy}
Given the generative model as before, one can show how free-energy becomes an upper bound on the atypicality of observations, defined as surprise in information theory. By minimising variational free-energy an agent can determine the most likely hidden states given sensory information. An expression for $F$ is given by:
\begin{eqnarray}
    F(\pi) = \sum_{\tau=1}^T \bm s_\tau^\pi \cdot \bigg[\ln{\bm s_\tau^\pi} - \ln{(\bm B_{\tau-1}^{\pi})}\bm s_{\tau-1}^{\pi} - \ln{\bm A}\cdot \bm o_\tau \bigg]
    \label{eq:free-energy}
\end{eqnarray}
where $F(\pi)$ is a policy specific free-energy. For the derivations please refer to Appendix \ref{sec:AppendixF}.
\begin{table}[ht]
\caption{Notation for Active Inference
\centering
\begin{tabular}{C{1.5cm} C{5.5cm}}
\hline\hline
\textbf{Symbol} & \textbf{Description}\\ [0.5ex]
\hline
$s_\tau,\ \bm s_\tau^\pi$ & Hidden state at time $\tau$, and expected value of posterior estimate under a policy \\
$o_\tau, \ \bm o_\tau^\pi$ & Outcome at time $\tau$, and expected value of posterior estimate under a policy \\
$\bm A$ &  Likelihood matrix mapping from hidden states to
outcomes $P(o_t|s_t)= Cat(\bm A)$ \\
$\bm B$ & Transition matrix $P(s_{t+1}|s_t,\ a_t)= Cat(\bm B)$\\
$\bm C$ & Logarithm of prior preferences over outcomes $\ln P(o_\tau) = \bm C$\\
$\bm D$ & Prior over initial states $P(s_1|s_0)= Cat(\bm D)$\\
$F$ & Variational free-energy \\
$G$ & Expected free-energy\\
$\pi$, $\bm \pi$ & Policy specifying action sequences, and posterior expectation\\
$\sigma$ & Softmax function \\
$a_t$ & Action at time $t$\\

\hline
\end{tabular}
\label{tab:Symbols}
\end{table}
\subsubsection{Perception}
According to active inference, both perception and decision making are based on the minimisation of free-energy. This is achieved through a gradient descent on $F$. In particular, for state estimation we take partial derivatives with respect to the states and set the gradient to zero. The expected value of the posterior estimate of the state, conditioned by a policy, is given by:
\begin{equation}
\label{eq:s_taupi}
    \bm s_{\tau}^{\pi} = \sigma(\ln{(\bm B_{\tau-1}^{\pi})}\bm s_{\tau-1}^{\pi} + \ln{(\bm B_{\tau}^{\pi})}\cdot \bm s_{\tau+1}^{\pi} + \ln{\bm A}\cdot \bm o_\tau)
\end{equation}
where $\sigma$ is the softmax function. For the complete derivation, please refer to Appendix \ref{sec:AppendixS}. Note that when $\tau = 1$ the first term is simply $\ln{\bm D}$.

\subsubsection{Expected Free-energy}
Active inference unifies action selection and perception by assuming that action fulfills predictions based on inferred states. Since the internal model can be biased towards preferred states or outcomes (\textit{prior desires}), active inference induces actions that will bring the current beliefs towards the preferred states. More specifically, the generative model entails beliefs about future states and policies, where policies that lead to preferred outcomes are more likely. Preferred outcomes are specifies in the model parameter $\bm C$. This enables action to realize the next (proximal) \textit{outcome} predicted by the policy that leads to (distal) goals. By minimising expected free-energy the agents gives higher plausibility to actions that will achieve those sensations. The expected free-energy for a policy $\pi$ at time $\tau$ is given by (see Appendix \ref{sec:AppendixG}) :
\begin{equation}
     G(\pi,\tau) = \bm o_\tau^\pi\cdot \left[\ln{\bm o_\tau^\pi}-\bm C\right] + \bm s_\tau^\pi\cdot\bm A\cdot \ln{\bm A}
     \label{eq:expectedF}
\end{equation}

\paragraph{Planning and decision making}
Taking a gradient descent of $F$ with respect to policies, and recalling that the generative model specifies $P(\bm \pi)=\sigma(-G(\pi))$, it holds that the approximate posterior over policies is given by:
\begin{equation}
    \bm \pi = \sigma(-\bm G_\pi - \bm F_\pi)
\end{equation}
See Appendix \ref{sec:AppendixPi} for the details. The vector $\bm \pi$ contains the probability for each policy.
\paragraph{Policy independent state-estimation}
Given the probability over possible policies, and the policy dependant states $\bm s_\tau^\pi$, we can compute the overall probability distribution for the states over time through Bayesian Model Average:
\begin{equation}
    \label{eq:s_tau}
    \bm s_\tau = \sum_p{\pi_p\cdot \bm s_\tau^{\pi_p}}
\end{equation}
were $\bm s_\tau^{\pi_p}$ is the probability of a state at time $\tau$ under policy $p$. This is the average prediction for the state at a certain time, so $\bm s_\tau$, according to the probability of each policy. In other words, this is a weighted average over different models. Models with high probability receive more weight, while models with lower probabilities are discounted.
\paragraph{Action selection}
The action for the agent at the current time $t$ is determined from the most likely policy:
\begin{equation}
\label{eq:a_t}
    a = \Myargmin_u \left( \sum_p{\delta_{u,\pi_{p}}\bm \pi}\right)
\end{equation}
were $\delta$ is the Kronecker delta, and $\pi_{p}$ is the probability of policy $p$.

The pseudo-code for action selection and belief updating, once given the model parameters $\bm A,\ \bm B,\ \bm D$, is reported in Algorithm \ref{alg:AIC}.
\begin{algorithm}
\caption{Action selection with active inference}\label{alg:AIC}
\begin{algorithmic}[1]
    \State \texttt{Set} $\bm C$ \Comment{prior preferences}
\For{$\tau=1:T$}
    \State Sample state from $\bm B$ if not specified
    \State Sample outcome from $\bm A$ if not specified
    \State Compute free-energy \Comment{eq. \eqref{eq:free-energy}}
    \State Update posterior state $\bm s_\tau^\pi$ \Comment{eq. \eqref{eq:s_taupi}}
    \State Compute expected free-energy \Comment{eq. \eqref{eq:expectedF}}
    \State Bayesian model averaging \Comment{eq. \eqref{eq:s_tau}}
    \State Action selection \Comment{eq. \eqref{eq:a_t}}
\EndFor
\State \textbf{Return} $\bm a$ \Comment{Preferred policy}
\end{algorithmic}
\end{algorithm}

\subsection{Background on Behavior Trees}
We now describe the high level concepts at the basis of Behavior Trees according to previous work such as \cite{Colledanchise2018, Colledanchise2017}. These concepts will be useful to understand the novel hybrid scheme proposed in the next section. A Behavior Tree is a directed tree composed of nodes and edges that can be seen as a graphical modeling language. It provides a structured representation for execution of actions which are based on conditions and observations in a system. The nodes in a BT follow the classical definition of parents and children. The root node is the only node without a parent, while the leaf nodes are all the nodes without children. In a BT, the nodes can be divided in control flow nodes (\textit{Fallback}, \textit{Sequence}, \textit{Parallel}, or \textit{Decorator}), and in execution nodes (\textit{Action} or \textit{Condition}) which are the leaf nodes of the tree. When executing a given behavior tree in a control loop, the root node sends a \textit{tick} to its child.  A tick is nothing more than a signal that allows the execution of a child. The tick propagates in the tree following the rules dictated by each control node. A node returns a status to the parent, that can be \textit{running} if its execution has not finished yet, \textit{success} if the goal is achieved, or \textit{failure} in the other cases. At this point, the return status is propagated back up the tree, which is traversed again following the same rules. The most important control nodes are:
\paragraph*{Fallback nodes} A fallback node ticks its children from left to right. It returns \textit{\textit{success}} (or \textit{running}) as soon a one of the children returns \textit{success} (or \textit{running}). When a child returns \textit{success} or \textit{running}, the fallback does not tick the next child, if present. If all the children return \textit{failure}, the fallback returns \textit{failure}. This node is graphically identified by a gray box with a question mark "$?$";
\paragraph*{Sequence nodes} The sequence node ticks its children from left to right. It returns \textit{running} (or \textit{failure}) as soon as a child returns \textit{running} (or \textit{failure}). The sequence returns \textit{success} only if all the children return \textit{success}. If a child returns \textit{running} or \textit{failure}, the sequence does not tick the next child, if present. In the library we used to implement our BTs \cite{bt_library} the \textit{sequence} node, indicated with [$\rightarrow$], keeps ticking a running child, and it restarts only if a child fails. \cite{bt_library} provides also \textit{reactive sequences} [$\rightarrow^R$] where every time a sequence is ticked, the entire sequence is restarted from the first child.

The execution nodes are \textit{Actions} and \textit{Conditions}:
\paragraph*{Action nodes} An Action node performs an action in the environment. While an action is being executed, this node returns \textit{running}. If the action is completed correctly it returns \textit{success}, while if the action cannot be completed it returns \textit{failure}. Actions are represented as  red rectangles;
\paragraph*{Condition nodes} A Condition node determines if a condition is met or not, returning \textit{success} or \textit{failure} accordingly. Conditions never return \textit{running} and do not change any states or variables. They are represented as orange ovals;

An example BT is given in Fig.~\ref{fig:btBackground}.

\begin{figure}[!htb]
    \centering
    \includegraphics[width=0.4\textwidth]{images/btBackground_shadow.pdf}
    \caption{Example of BT. The \textit{tick} traverses the tree starting from the \textit{Root}. If $Condition$ is true $Action_1$ is executed. If both of them return success, the \textit{Root} returns success, otherwise $Action_2$ is executed.}
    \label{fig:btBackground}
\end{figure}

\section{Conclusions}
\label{sec:Conclusions}

In this work, we proposed a new control architecture for reactive robot behavior based on the hybrid combination of active inference and behavior trees. We showed how robotic tasks can be described in terms of free-energy minimization, using behavior trees to specify prior preferences. This allowed different robots to be reactive to unforeseen situations at run-time, while still being able to follow offline plans. We introduced action preconditions and conflict resolution for active inference by means of dynamic priors. This means that a robot can locally set its own sub-goals to resolve a local inconsistency, and then return to the initial plan specified in the BT. We presented a theoretical analysis of convergence and robustness of the algorithm, and the effectiveness of the approach is demonstrated on two different mobile manipulators, with simulation and real experiments. Future work will focus on the expansion of this algorithm to include more powerful reasoning capabilities.

\section{Discussion and conclusion}
\label{sec:Discussion}
The focus of this paper is on the runtime adaptability and reactivity in dynamic environments with partially observable initial state, and not on the generation of complex offline plans. The core idea in this paper is to enhance offline plans with online decision making in specific parts of the behavior to be able to quickly repeat, skip, or stop actions. We proposed a combination of BTs and active inference to achieve so, but one should notice that the core principle is independent from the techniques chosen both for the offline planning part and the online adaptation. One could use a different probabilistic search approach in combination with BTs, or substitute BTs with other methods.

Another interesting aspect of this approach is that the online decision making relies on symbolic actions that can be improved over time independently of the action planner. New actions can easily be added, modified, extended, as long as the correct models are added (only once) in the current active inference model.

The main limitation of this approach, which will be addressed in future work, is that a more powerful reasoning method to choose among different alternatives of achieving the same goal is still missing. At the current stage, the order (or preference) among different alternatives is fixed a priori in the generative model.
One could however parametrize this preference to include the the likelihood of success of the available alternatives, and then choose the appropriate values at runtime through reasoning, for instance using semantic knowledge, or learning methods. The likelihood of an action could also be decreased if that action is failing repeatedly such that other alternatives become more appealing.

Also, in the current formulation the behavior trees were manually designed but future work can enhance the potential of this work, for example by including automated planning with translation to BTs such as \cite{martin2021}.

To conclude, in this work, we tackled the problem of action planning and execution in real world robotics with partially observable initial state. We addressed two open challenges in the robotics community, namely hierarchical deliberation and continual online planning, by combining behavior trees and active inference.
The proposed algorithm and its core idea are general, and independent of the particular robot platform, task, and even the techniques chosen to structure the offline plan or the online action selection process. Our solution provides local reactivity to unforeseen situations while keeping the initial plan intact. In addition, it is possible to easily add safety guarantees to override the online decision making process thanks to the properties of BTs. We showed how robotic tasks can be described in terms of free-energy minimization, and we introduced action preconditions and conflict resolution for active inference by means of dynamic priors. This means that a robot can locally set its own sub-goals to resolve a local inconsistency, and then return to the initial plan specified in the BT. We performed a theoretical analysis of convergence and robustness of the algorithm, and the effectiveness of the approach is demonstrated on two different mobile manipulators and different tasks, both in simulation and real experiments.

\section{Experimental evaluation}
\label{sec:Experiments}
In this section we evaluate our algorithm in terms of robustness, safety, and conflicts resolution in two validation scenarios with two different mobile manipulators and tasks. We also provide a comparison with classical and dynamically expanded BTs.

\subsection{Experimental scenarios}
\subsubsection{Scenario 1} The task is to pick one object from a crate, and place it on top of a table. This object might or might not be reachable from the initial robot configuration, and the placing location might or might not be occupied by another movable box. We suppose that other external events, or agents, can interfere with the execution of the task, resulting in either helping or adversarial behavior.
The robot used for the first validation scenario is a mobile manipulator consisting of a Clearpath Boxer mobile base, in combination with a Franka Emika Panda arm. The experiment for this scenario was conducted in a Gazebo simulation in a simplified version of a real retail store, see Fig.~\ref{fig:gazebo}.
\begin{figure}[!htb]
    \centering
    \includegraphics[width=0.4\textwidth]{images/gazebo.pdf}
    \caption{Simulation of the mobile manipulation task.}
    \label{fig:gazebo}
\end{figure}

\subsubsection{Scenario 2} The task is to fetch a product in a mockup retail store and stock it in a shelf using the real mobile manipulator TIAGo, as in Fig.~\ref{fig:tiago}.

Importantly, the behavior tree for completing the task in the real store with TIAGo is the same used for simulation with the Panda arm and the mobile base, just parametrised with a different object and place location. The code developed for the experiments and more theoretical examples are publicly available.\footnote{\url{https://github.com/cpezzato/discrete_active_inference}}.
\begin{figure}[!htb]
    \centering
    \includegraphics[width=0.4\textwidth]{images/robot_experiments.pdf}
    \caption{Experiments with TIAGo, stocking a product in the shelf.}
    \label{fig:tiago}
\end{figure}

\subsection{Implementation}
In order to program the tasks for\textit{ Scenarios 1} and \textit{2}, we extended  the robot skills defined in our theoretical Example \ref{ex:movePick}. We added then two extra states and their relative observations: \texttt{isPlacedAt(loc, obj)} called $s_p$, and \texttt{isLocationFree(loc)} called $s_f$. The state $s_p$ indicates whether or not \texttt{obj} is at \texttt{loc}, with associated probability, while $s_f$ indicates whether \texttt{loc} is occupied by another object. Then, we also had to add three more actions, which are 1) \texttt{Place(obj, loc)}, 2) \texttt{Push(obj)} to free a placing location, and 3) \texttt{PlaceOnPlate(obj)}, to place the object held by the gripper on the robot's plate. We summarise states and skills for the mobile manipulator in Table~\ref{tab:States}.

\begin{table}[ht]
\caption{Notation for states and actions
\centering
\begin{tabular}{C{2.8cm} C{4.7cm}}
\hline\hline
\textbf{State, Boolean State} & \textbf{Description}\\ [0.5ex]
\hline
$s_g,\ l_g$ & Belief about being at the goal location \\
$s_h,\ l_h$ & Belief about holding an object\\
$s_r,\ l_r$ & Belief about reachability of an object\\
$s_p,\ l_p$ & Belief about an object being at a location\\
$s_f,\ l_f$ & Belief about a location being free\\

\hline
\end{tabular}
\label{tab:States}
\end{table}

\begin{table}[h]
\centering
\begin{tabular}{l l l}
    \textbf{Actions}& \textbf{Preconditions}& \textbf{Postconditions}\\
    \texttt{moveTo(goal)} & \texttt{-} & $l_g = [1\ 0]^\top$ \\
    & & $l_r = [1\ 0]^\top$ \\
    \texttt{Pick(obj)} & \texttt{isReachable(obj)}& $l_h = [1\ 0]^\top$\\
     & \texttt{!isHolding} & \\
    \texttt{Place(obj,loc)} & \texttt{isLocationFree(loc)}& $l_p = [1\ 0]^\top$\\
    \texttt{Push()} & \texttt{!isHolding} & $l_f = [1\ 0]^\top$\\
    \texttt{PlaceOnPlate()} & - & $l_h = [0\ 1]^\top$\\
\end{tabular}
\end{table}

The likelihood matrices are just the identity, while the transition matrices simply map the postconditions of actions, similarly to Example~\ref{ex:movePick}. Note that the design of actions and states is not unique, and other combinations are possible. One can make atomic actions increasingly more complex, or add more preconditions. The plan, specified in a behavior tree, contains the desired sequence of states to complete the task, leaving out from the offline planning other complex fallbacks to cope with contingencies associated with the dynamic nature of the environment. The behavior tree for performing the tasks in both \textit{Scenario~1} and \textit{Scenario~2} is reported in Fig.~\ref{fig:bt_experimets}. Note that the fallback for the action \texttt{moveTo} could be substituted by another prior node as in Fig.~\ref{fig:btSimple}, however we opted for this alternative solution to highlight the hybrid combination of classical BTs and active inference. Design principles to choose when to use prior nodes and when normal fallbacks are reported in Sec.\ref{sec:comparison}.

\begin{figure}[!htb]
    \centering
    \includegraphics[width=0.42\textwidth]{images/btDemo_hybrid.pdf}
    \caption{BT with prior nodes to complete the mobile manipulation task in the retail store, \textit{Scenario 1} and 2. $loc_s$, $loc_p$ are respectively the location in front of the shelf in the store and the desired place location of an item}
    \label{fig:bt_experimets}
\end{figure}

The implementation of the algorithm for mobile manipulation described so far was developed for \textit{Scenario 1}, and then it was entirely reused in \textit{Scenario 2}, with the only adaptation of the desired object and locations in the BT. In Sec.~\ref{sec:robustness} and Sec.~\ref{sec:runtimeconflicts}, robustness and run-time conflicts resolution are analysed for \textit{Scenario 1}, but similar considerations can be derived for the \textit{scenario 2}.

\subsection{Robustness: Dynamic regions of attraction}\label{sec:robustness}
The initial configuration of the robot is depicted in Fig.~\ref{fig:gazebo}. The first node which is ticked in the behavior tree is the node containing the prior \texttt{isHolding(obj)}. According to the current world's state, Algorithm~\ref{alg:idea} will select different actions, to generate a suitable DoA. An example is reported below.
\begin{example}
\label{ex:doa}
\textit{Supposing the initial conditions are such that the object is not reachable. Let $s_h \in [0,\ 1]$ be the probabilistic belief of holding an object, and $s_r \in [0,\ 1]$ the probabilistic belief of its reachability. The DoA generated by Algorithm~\ref{alg:idea} at runtime is depicted in Fig.~\ref{fig:bt_pp} using phase portraits as in \cite{Colledanchise2017}. Actions, when performed, increase the probability of their postconditions.}

\begin{figure}[htb]
    \centering
    \includegraphics[width=0.42\textwidth]{images/phasePortrait.pdf}
    \caption{Dynamic DoA generated by Algorithm \ref{alg:idea} for Example \ref{ex:doa}. (a) relates to the action \texttt{Pick(obj)}, and (b) is the composition of \texttt{moveTo(loc)} and \texttt{Pick(obj)} after automatically updating the prior preferences}
    \label{fig:bt_pp}
\end{figure}
\end{example}
From Fig.~\ref{fig:bt_pp}, we can see that the goal of the active inference agent is to hold \texttt{obj} so $C_h = [1\ 0]$. The first selected action is then \texttt{Pick(obj)}. However, since the current logical state is not contained in the domain of attraction of the action, the prior preferences are updated with the missing (higher priority) precondition according to the action template provided, that is \texttt{isReachable} so $C_r = [2, 0]$. This results in a sequential composition of controllers with a stable equilibrium corresponding to the postconditions of \texttt{Pick(obj)}. On the other hand, to achieve the same domain of attraction with a classical behavior tree, one would require several additional nodes, as explained in Sec.~\ref{sec:comparison} and visualized in Fig.~\ref{fig:bt_comparison}. Instead of extensively programming fallback behaviors, Algorithm~\ref{alg:idea} endows our actor with deliberation capabilities, and allows the agent to reason about the current state of the environment, the desired state, and the available action templates.

\subsection{Resolving run-time conflicts}
\label{sec:runtimeconflicts}
Perturbations affecting the system during action selection can lead to conflicts with the initial offline plan. This is the case in the manipulation task in Fig.~\ref{fig:gazebo} after picking the object and moving in front of the table, and then sensing that the place location is not free.
\begin{example}
\label{ex:conflict}\textit{
The situation just described can be represented schematically by considering the priors and the logical states of the quantities of interest (see tab.~\ref{tab:States} for notation). For completing the task, the robot should hold the object, be at the desired place location, and then have the object placed \eqref{eq:priors}. On the other hand, there is a mismatch between the current logical belief about the state $l_p$ and the desired $\bm C_p$ \eqref{eq:logicalStates}.}
\begin{subequations}
\begin{equation}
\label{eq:priors}
    \bm C_h = \begin{bmatrix} 1 \\ 0
    \end{bmatrix},\  \bm C_g = \begin{bmatrix} 1 \\ 0
    \end{bmatrix},\  \bm C_p = \begin{bmatrix} 1 \\ 0
    \end{bmatrix}
\end{equation}
\begin{equation}
\label{eq:logicalStates}
    l_h = \begin{bmatrix} 1 \\ 0
    \end{bmatrix},\  l_g = \begin{bmatrix} 1 \\ 0
    \end{bmatrix},\  l_p = \begin{bmatrix} 0 \\ 1
    \end{bmatrix}
\end{equation}
\end{subequations}
The only remaining state to be reached is the last state, so the action selected by active inference is \texttt{Place(obj,loc)}. The missing precondition on the place location to be free is then added to the prior $\bm C_f$. According to Algorithm~\ref{alg:idea}, active inference is ran again. This lead to the next action which can minimise free-energy, that is \texttt{Push}. Again, the missing precondition \texttt{!isHolding} is pushed in the current prior with higher priority.
\begin{equation}
    \bm C_h = \begin{bmatrix} 1 \\ \textcolor{tudelft-fuchsia}{2}
    \end{bmatrix},\  \bm C_f = \begin{bmatrix} 2 \\ 0
    \end{bmatrix}
\end{equation}
\vspace{0mm}
\end{example}
In this situation, a conflict with the offline plan arises, as can be seen in $\bm C_h$. Even though the desired state specified in the BT is \texttt{isHolding(obj)}, in this particular moment there is a higher preference in having the gripper free due to a missing precondition to proceed with the plan. Algorithm~\ref{alg:idea} selects then the action that best matches the current prior desires, or equivalently that minimises expected free-energy the most, that is \texttt{PlaceOnPlate} to obtain $l_h = [0,\ 1]^\top$. This allows then to perform the action \texttt{Push}. At this point, there are no more preferences with high priority, thus the prior over the state $l_h$ is only set by the BT as  $\bm C_h = [1,\ 0]^\top$. Now the object can be picked again and placed on the table since no more conflicts are present.

The simulations of \textit{Scenario 1} and the experiments of \textit{Scenario 2}, as well as the behavior of the mobile manipulator from Examples \ref{ex:doa} and \ref{ex:conflict}, can be visualized in the recorded video\footnote{\url{https://youtu.be/dEjXu-sD1SI}}. The Behavior trees to encode priors for active inference are implemented using a standard library \cite{bt_library}.

\subsection{Safety}
When designing adaptive behaviors for autonomous robots, attention should be paid to \textit{safety}. The proposed algorithm allows to retain control over the general behavior of the robot, and to force a specific routine in case something goes wrong leveraging the structure of BTs. In fact, we are able to include adaptation through active inference only in the parts of the task that require that, keeping all the properties of BTs intact. Safety guarantees can easily be added by using a sequence node where the leftmost part is the safety criteria to be satisfied \cite{Colledanchise2017}, as shown in Fig.~\ref{fig:safety}.
\begin{figure}[!htb]
    \centering
    \includegraphics[width=0.4\textwidth]{images/btsafety_bis.pdf}
    \caption{BT with safety guarantees while allowing runtime adaptation.}
    \label{fig:safety}
\end{figure}
In this example, the BT allows to avoid battery drops below a safety critical value while performing a task. The sub-tree on the right can be any other behavior tree, for instance the one used to solve \textit{Scenario 1} and \textit{Scenario 2} from Fig.~\ref{fig:bt_experimets}.

Since, by construction, a BT is executed from left to right, one can assure that  the robot is guaranteed to satisfy the leftmost condition first before proceeding with the rest of the behavior. In our specific case, this allows to easily override the online decision making process with active inference where needed, in favour of safety routines.

\subsection{Comparison and design principles}
\label{sec:comparison}
\begin{figure*}
    \centering
    \includegraphics[width=0.9\textwidth]{images/bt_comparison.pdf}
    \caption{Possible standard BT to perform \textit{Scenario 1} and \textit{Scenario 2} without prior nodes for active inference. Parts of the behavior that require several fallbacks can be substituted by prior nodes for online adaptation instead.}
    \label{fig:bt_comparison}
\end{figure*}

\subsubsection{Comparison with similar approaches}
The hybrid scheme of active inference and BTs aims at providing a framework for reactive action planning and execution in robotic systems. For this reason, we compare the properties of our approach with standard BTs \cite{Colledanchise2017} and with BTs generated through expansion from goal conditions \cite{Colledanchise2019}.
\textit{Scenario 1} and \textit{Scenario 2} can be tackled, for instance, by explicitly planning every fallback behavior with classical BTs, as in Fig.~\ref{fig:bt_comparison}. Even if this provides the same reactive behavior as the one generated by Fig.~\ref{fig:bt_experimets}, far more (planning) effort is needed: to solve the same task one would require 12 control nodes, 8 condition nodes, and 7 actions, for a total of 27 nodes compared to the 6 needed in our approach that is an $\sim88\%$ compression.

Importantly, the development effort of a prior node in a BT is the same as a standard action node. It is true that active inference requires to specify the likelihood and transition matrices encoding actions pre- and postconditions, but this has to be done only once while defining the available skills of a robot, and it is independent of the task to be solved. Thus, a designer is not concerned with this when adding a prior node in a BT.

Instead of planning several fallbacks offline, \cite{Colledanchise2019} dynamically expands a BT from a single goal condition, through backchaining, to blend planning and acting online. To solve \textit{Scenario 1} and \textit{Scenario 2} with this approach, one needs to define a goal condition \texttt{isPlacedAt(obj, loc)} similarly to our solution, and define the preconditions of the action \texttt{Place(obj, loc)} such that they contain the fact that the robot is holding the object, that the place location is reachable, and it is free. Then, to solve \textit{Scenarios 1} and \textit{2} one needs to define only the final goal condition and run the algorithm proposed in \cite{Colledanchise2019}. Even though this allows to complete the tasks similarly to what we propose, \cite{Colledanchise2019} comes with a fundamental theoretical limitation: adaptation cannot be selectively added only in specific parts of the tree. The whole behavior is indeed determined at runtime based on preconditions and effects of actions starting from a goal condition. The addition of safety guarantees in specific parts of the tree is not possible explicitly unlike in our approach, which might be a deal breaker for safety critical applications. To conclude, the hybrid combination of active inference and BTs allows to combine the advantages of both offline design of BTs and online dynamic expansion. In particular: it drastically reduces the number of necessary nodes in a BT planned offline, it can handle partial observability of the initial state, it allows to selectively add adaptation in specific parts of the tree, it allows to add safety guarantees while being able to adapt to unforeseen contingencies.

Another important difference between our approach and other BTs solutions is that we introduced the concept of \textit{state} in a BT through the \textit{prior} node for which a probabilistic belief is built, updated, and used for action planning at runtime with uncertain action outcomes.

Additionally, one may argue that other solutions such as ROSPlan \cite{cashmore2015rosplan} could also be used for planning and execution in robotics in dynamic environments. ROSPlan leverages automated planning with PDDL2.1, but it is not designed for fast reaction in case of dynamic changes of the environment caused by external events. Moreover, it is based on the assumption that the initial state is fully observable and its reactivity is limited to re-planning of the whole task, which might be a waste of resources.

Table~\ref{tab:comparison} reports a summary of the comparison with standard BTs and BT with dynamic expansion for \textit{Scenario 1} and \textit{2}.

\begin{table}[ht]
\caption{Summary of comparison} \centering
\begin{tabular}{C{1.2cm} C{1cm} C{1.5cm} C{1.5cm} C{1.5cm}}
\hline\hline
 \textbf{Approach} & \textbf{\# Nodes}& \textbf{Unforeseen contingen.} & \textbf{Selective adaptation} & \textbf{Safety guarantees} \\ [0.5ex]
\hline
Standard BT & 27 & \xmark & \xmark & \cmark\\
\hline
Dynamic BT \cite{Colledanchise2019} & 1 & \cmark & \xmark & \xmark \\
\hline
Ours & 6 & \cmark & \cmark & \cmark \\
\hline
\end{tabular}
\label{tab:comparison}
\end{table}

\subsubsection{Design principles}
We position our work in between two extremes, namely fully offline planning and fully online dynamic expansion of BTs.
In our method, a designer can decide if to lean towards a fully offline approach or a fully online synthesis, depending on the task at hand and the modelling of the actions pre- and postconditions. Even though the design of behaviors is still an art, we give some design principles which can be useful in the development of robotic applications using this hybrid BTs and active inference method. Take for instance Fig.~\ref{fig:bt_comparison} and Fig.~\ref{fig:bt_experimets}. Prior nodes for local adaptation can be included in the behavior when there are several contingencies to consider or action preconditions to be satisfied in order to achieve a sub-goal. A designer can: 1) plan offline where the task is certain or equivalently where a small number of things can go wrong; 2) use prior nodes implemented with active inference to decide at runtime the actions to be executed whenever the task is uncertain. This is a compromise in between a fully defined plan where the behavior of the robot is predefined in every part of the state space, and a fully dynamic expansion of BTs which can result in sub-optimal action sequence \cite{Colledanchise2019}. This is illustrated in Fig.\ref{fig:bt_experimets} for instance, where the actions for holding and placing an object are chosen online due to various possible unexpected contingencies, whereas the \texttt{moveTo} action is planned since it is only based on one precondition. Prior nodes should be used whenever capturing the variability of a part of a certain task would require much effort during offline planning.
\section{Introduction}
\IEEEPARstart{D}{eliberation} and reasoning capabilities for acting are crucial parts in online robot control, especially when operating in dynamic environments to complete long term tasks. Over the years, researchers developed many task planners with various degrees of optimality, but little attention has been payed to actors \cite{ghallab2014,nau2015}, i.e. algorithms endowed with reasoning and deliberation tools during plan execution. Works as \cite{ghallab2014,nau2015} advocate a change in focus, explaining why this lack of actors could be one of the main causes of the limited spread of automated planning applications. Works such as \cite{Colledanchise2017,Colledanchise2019,safronov2020task} proposed the use of Behavior Trees as graphical models for more reactive task execution, showing promising results. Other authors also tried to answer the call for actors \cite{Paxton2019, Garrett2020}, but there are still open challenges to be addressed. These challenges have been identified and highlighted by many researchers, and can be summarised as in \cite{ghallab2014, Colledanchise2019} in two properties that an actor should possess:
\begin{itemize}
    \item \textit{Hierarchical deliberation}: each action in a plan may be a task that an actor may need to further refine online.
    \item \textit{Continual online planning and reasoning}: an actor should monitor, refine, extend, update, change, and repair its plans throughout the acting process, generating activities dynamically at run-time.
\end{itemize}

Actors should not be mere action executors then, but they should be capable of intelligently taking decisions. This is particularly useful for challenging problems such as mobile manipulation in dynamic environments, where actions planned offline are prone to fail. In this paper we consider mobile manipulation tasks in a retail environment with partially observable initial state, and we propose an actor which is capable of following a task planned offline while still being able of taking autonomous decisions at run-time to resolve unexpected situations.

To achieve so, we propose the use of active inference, a neuroscientific theory which has recently shown its potential in control engineering and robotics \cite{anil_colored_noise, baioumy2020active,Corrado2,baioumy2021fault}, in particular in real world experiments for low level adaptive control \cite{Pezzato2019, oliver}. Active inference describes a biologically plausible algorithm for perception, action, planning, and learning. This theory has been initially developed for continuous processes \cite{friston2, buckley, tutorial} where the main idea is that the brain's cognition and motor control functions could be described in terms of \textit{free-energy minimization} \cite{friston1}. In other words we, as humans, take actions in order to fulfill prior expectations about a \textit{desired prior} sensation \cite{friston3}. Active inference has also been extended to Markov Decision Processes (MDP) for discrete decision making  \cite{friston2012active}, recently gathering more and more interest \cite{friston2017active, sajid2021active, schwartenbeck2019computational, Kaplan2018}. In this formulation, active inference is proposed as a unified framework to solve the exploitation-exploration dilemma by acting to minimize the free-energy. Agents can solve complicated problems once provided a \textit{context sensitive prior} about preferences. Probabilistic beliefs about the state of the world are built through Bayesian inference, and a finite horizon policy is selected in order to maximise the evidence for a model that is biased towards the agent's preferences. At the time of writing, the use of discrete Active Inference for symbolic action planning is limited to low dimensional and simplified simulations \cite{schwartenbeck2019computational, Kaplan2018}. In addition, current solutions rely on fundamental assumptions such as instantaneous actions without preconditions, which do not hold in real robotic situations.

To tackle these limitations of active inference and to address the two main open challenges of hierarchical deliberation and continual planning, we propose a hybrid combination of active inference and Behavior Trees. We then apply this new idea to mobile manipulation in a dynamic retail environment.

\subsection{Related Work}
In this section we mainly focus on related work on \textit{reactive action planning and execution}, a class of methods that exploits reactive plans, which are stored structures that contain the behaviour of an agent. To begin with, Behavior Trees \cite{Colledanchise2018, Colledanchise2017} gathered increasing popularity in robotics to specify reactive behaviors. BTs are graphical representations for actions execution. The general advantage of BTs is that they are modular and can be composed in more complex higher-level behaviours, without the need to specify how different BTs relate to each other. They are also an intuitive representation which modularizes other architectures such as FSM and decision trees, with proven robustness and safety properties \cite{Colledanchise2017}. These advantages and the structure of BTs make them particularly suitable for the class of dynamic problems we are considering in this work, as explained later on in Section \ref{sec:Background}. However, in classical formulations of BTs, the plan reactivity still comes from hard-coded recovery behaviors. This means that highly reactive BTs are usually big and complex, and that adding new robotic skills would require revising a large tree. To partially cope with these problems, Colledanchise et al.~\cite{Colledanchise2019} proposed a blended reactive task and action planner which dynamically expands a BT at runtime through back-chaining. The solution can compensate for unanticipated scenarios, but cannot handle partially observable environments and uncertain action outcomes. Conflicts due to contingencies are handled by prioritizing (shifting) sub-trees. Authors in \cite{safronov2020task} extended \cite{Colledanchise2019} and showed how to handle uncertainty in the BT formulation as well as planning with non-deterministic outcomes for actions and conditions. Other researchers tried to combine the advantages of behavior trees with the theoretical guarantees on performance of PDDL planning \cite{Paxton2019}. Even though this results in a more concise problem description with respect to using BTs only, online reactivity is again limited to the scenarios planned offline. For unforeseen contingencies re-planning would be necessary, which is more resource demanding than reacting as shown in the experimental results in \cite{Paxton2019}.

Goal Oriented Action Planning (GOAP) \cite{Orkin2003}, instead, focuses on online action planning. This technique is used for non-player-characters (NPC) in video-games \cite{Orkin2006}. Goals in GOAP do not contain predetermined plans. Instead, GOAP considers atomic behaviors which contain preconditions and effects. The general behavior of an agent can then be specified through very simple Finite State Machines (FSMs) because the transition logic is separated from the states themselves. GOAP generates a plan at run-time by searching in the space of available actions for a sequence that will bring the agent from the starting state to the goal state. However, GOAP requires hand-designed heuristics that are scenario specific, and is computationally expensive for long term tasks.

Hierarchical task Planning in the Now (HPN) \cite{Kaelbling2011} is an alternate plan and execution algorithm where a plan is generated backwards starting from the desired goal, using A*. HPN recursively executes actions and re-plans. To cope with the stochasticity of the real world, HPN has been extended to belief HPN (BHPN) \cite{PackKaelbling2013}. A follow up work \cite{Levihn2013} focused on the reduction of the computational burden implementing \textit{selective re-planning} to repair to local poor-choices or exploit new opportunities without the need to re-compute the whole plan which is very costly since the search process is exponential in the length of the plan.

A different method for generating plans in a top-down manner is Hierarchical Task Network (HTN) \cite{Erol1994,Georgievski2014}. At each step, a high-level task is refined into lower-level tasks. In practice \cite{Ghallab2016}, the planner exploits a set of standard operating procedures for accomplishing a given task. The planner decomposes the given task choosing among the available ones, until the chosen primitive is directly applicable to the current state. Tasks are then iteratively replaced with new task networks. An important remark is that reaction to failures, time-outs, and external events are still a challenge for HTN planners. Besides, current interfaces for HTN planning are often cumbersome and not user-friendly \cite{Georgievski2014}. The drawbacks of this approach are that it requires the designer to write and debug potentially complex domain specific recipes, and that in very dynamic situations re-planning might occur too often.

Finally, active inference is a normative principle underwriting perception, action, planning, decision-making and learning in biological or artificial agents. Active inference on discrete state-spaces \cite{DaCosta2020} is a promising approach to solve the exploitation-exploration dilemma and empowers agents with continuous deliberation capabilities. The application of this theory, however, is still in an early stage for discrete decision making where current works only focus on simplified simulations as proof of concept \cite{friston2017active, Kaplan2018, sajid2021active, schwartenbeck2019computational}. In \cite{Kaplan2018}, for instance, the authors simulated an artificial agent which had to learn and to solve a maze given a set of simple possible actions to move (\textit{up, down, left, right, stay}). Actions were assumed instantaneous and always executable. In general, current discrete active inference solutions lack a systematic and task-independent way of specifying prior preferences, which is fundamental to achieve a meaningful agent behavior, and they never consider action preconditions which are crucial in real world robotics. As a consequence, policies with conflicting actions which might arise in dynamic environments are never addressed in the current state-of-the-art.

\subsection{Contributions}
In this work, we propose the hybrid combination of BTs and active inference to obtain more reactive actors with hierarchical deliberation and continual online planning capabilities. We introduce a method to include action preconditions and conflicts resolution in active inference, as well as a systematic way of providing prior preferences through BTs. The proposed hybrid scheme leverages the advantages of online action selection with active inference and it removes the need for complex predefined fallback
behaviors while providing convergence guarantees. In addition, with this paper we want to facilitate the use of active inference in robotics by making it more accessible to a plurality or researchers, thus we provide extensive mathematical derivations, examples, and code.

\subsection{Paper structure}
The remainder of the paper is organized as follows. In Section \ref{sec:Background} we provide an extensive background on active inference and BTs. Our novel hybrid approach is presented in Section \ref{sec:Solution}, and its properties in terms of robustness and stability
are analysed in Section \ref{sec:Analysis}. In Section \ref{sec:Experiments} we report the experimental evaluation, showing how our solution can be used with different mobile manipulators for different tasks in a retail environment. Finally, Section \ref{sec:Discussion} contains discussion, conclusions, and future work.
\section{Active Inference and BTs for Reactive Action Planning and Execution}
\label{sec:Solution}
In this section we introduce our novel approach using behavior trees and active inference. Even though active inference is a very promising theory, from a computational perspective computing the expected free-energy for each possible policy that a robot might take is cost-prohibitive. This curse of dimensionality is due do the combinatorial explosion when looking deep into the future \cite{DaCosta2020}. To solve this problem, we propose to replace \textit{deep policies} with \textit{shallow decision trees} that are \textit{hierarchically composable}. This will allow us to simplify our offline plans, exploit opportunities, and act intelligently to resolve local unforeseen contingencies. Our idea consists in two main intuitions:
\begin{itemize}
    \item To avoid combinatorial explosion while planning and acting with active inference for long term tasks we specify the nominal behavior of an agent through a BT, used as a prior. Doing so, Behavior Trees provide \textit{global reactivity to foreseen situations}
    \item To avoid coding every possible contingency in the BT, we program only desired states offline, and we leave action selection to the online active inference scheme. Active inference provides then \textit{local reactivity to unforeseen situations}.
\end{itemize}
To achieve such a hybrid integration, and to be able to deploy this architecture on real robotic platforms, we addressed the following three fundamental problems: 1) how to define the generative models for active inference in robotics, 2) how to use BTs to provide priors as desired states to active inference, 3) how to handle action preconditions in active inference, and possible conflicts which might arise at run-time in a dynamic environment.

\subsection{Definition of the models for active inference}
The world in which an agent operates needs to be abstracted such that the active inference agent can perform its reasoning processes. In this work, we operate in a continuous environment with the ability of sensing and acting through symbolic decision making. We model the skills of a robot as a set of atomic actions $a_j\subset \mathcal{A}$ with $j=1...k$ which have associated \textit{parameters}, \textit{pre-} and \textit{postconditions}:
\begin{table}[ht]
\centering
\begin{tabular}{l c c}
    \textbf{Action} $a_j$& \textbf{Preconditions}& \textbf{Postconditions}\\
    \texttt{action\_name(}$par$\texttt{)}&\texttt{prec}$_{a_j}$ & \texttt{post}$_{a_j}$
\end{tabular}
\end{table}

where \texttt{prec}$_{a_j}$ and \texttt{post}$_{a_j}$ are \textit{first-order logic predicates} that can be evaluated at run-time. A logical predicate is a boolean-valued function $\mathcal{P}:\mathcal{X}\rightarrow\{$\texttt{true}, \texttt{false}$\}$.

We define $x\subset\mathcal{X}$ the continuous states of the world and the internal states of the robot are accessible through the symbolic perception system. The role of this perception system is to discretize the continuous states $x$ into symbolic observations $o_i\subset \mathcal{O}$ with $i=1...n$ that can be manipulated by the discrete active inference agent. Observations $o$ are used to build a probabilistic belief about the current state, indicated with $s_i\subset \mathcal{S}$ with $i=1...n$. Each belief for a state $i$ is $s_i\in\mathbb{R}^{m_i}$ where $m_i$ is the number of mutually exclusive symbolic values that a state can have. Each entry of a particular belief $s_i$ can take any value in between 0 and 1 ($\in [0,1]$), while each entry of a particular observation $o_i$ is a binary value $\in \{0,1\}$, indicating if a particular state is sensed or not.  Finally, we define $l\subset\mathcal{L}$ as the most probable logical state based on the belief $s$. Defining a logic state based on the probabilistic belief $s$ built with active inference, instead of directly using the observation of the states $o$, increases robustness against noisy sensor readings.

Given the model of the world just introduced, we can now define the likelihood matrix $\bm A$, the transition matrix $\bm B$ and the prior over states $\bm C$. When an observation is available, $\bm A$ provides information about the corresponding value of a state.
Thus, for a particular state $s_i$, the probability of a state outcome pair $o_i$, $s_i$ at the current time $t$ is:
\begin{equation}
   P(o_{i,t}|s_{i,t})= Cat(\bm A_i),\hspace{5mm} \bm A_i = I_d\in \mathbb{R}^{m_i \times m_i}
\end{equation}
Note that knowing the mapping between observations and states does not necessarily mean that we can observe all the states at all time. Observations can be present or not, and when they are the likelihood matrix indicates that a specific state is sensed.

To define the transition matrices, we need to encode in a matrix form the effects of each action on the relevant states. The probability of a ending up in a state $s_{t+1}$, given $s_{t}$ and action $a_i$ is given by:
\begin{equation}
       P(s_{t+1}|s_{t},a_i) = Cat(\bm B_{a_i}),\hspace{5mm} \bm B_{a_i} \in \mathbb{R}^{m_i \times m_i}
\end{equation}
In other words, we define $\bm B_{a_i}$ as a square matrix encoding the post-conditions of action $a_i$.
\begin{example}
\label{ex:obs_states}
\textit{Consider a mobile manipulator in a retail environment. The first skill that we provide to the robot is the ability to navigate to a specified goal location such as} \texttt{moveTo(goal)}.
\begin{table}[h]
\centering
\begin{tabular}{l l l}
    \textbf{Actions}& \textbf{Preconditions}& \textbf{Postconditions}\\
    \texttt{moveTo(goal)} & \texttt{-} & $l_g = [1\ 0]^\top$ \\
\end{tabular}
\end{table}

\textit{During an execution, the current position in space of the robot $\subset \mathcal{X}$, the robot is given an observation $o_g$ which indicates simply if the} \texttt{goal} \textit{has been reached or not. The agent is then constantly building a probabilistic belief $s_g$ encoding the chances of being at the} \texttt{goal}. \textit{In case the robot has not yet reached the goal, a possible configuration at time $t$ is the following:}
\begin{equation}
\nonumber
    o_g = \begin{bmatrix} \texttt{isAt(goal)}\\ \texttt{!isAt(goal)}
    \end{bmatrix} = \begin{bmatrix} 0 \\ 1
    \end{bmatrix},\ s_g = \begin{bmatrix} 0.08 \\ 0.92
    \end{bmatrix},\ l_g = \begin{bmatrix} 0 \\ 1
    \end{bmatrix},
\end{equation}
\begin{equation}
   \bm B_g = \begin{bmatrix}
        0.95 & 0.9 \\
        0.05 & 0.1
    \end{bmatrix}\hspace{5mm} \bm B_{idle} = \begin{bmatrix}
        1 & 0 \\
        0 & 1
    \end{bmatrix}
\end{equation}
\vspace{0mm}
\end{example}
The transition matrix $\bm B_g$ encodes the probability of reaching a goal location through the action \texttt{moveTo(goal)}, which might fail with a certain probability. We also encode an \texttt{Idle} action, which does not modify any state, but it provides information on the outcome of the action selection process as we will see in the next subsections.

Using the proposed problem formulation for the active inference models, we can abstract redundant information which is not necessary to make high-level decisions. For instance, in the example above we are not interested in building a probabilistic belief of the current robot position. To decide if to use the action \texttt{moveTo(goal)} or not, it is sufficient to encode if the \texttt{goal} has been reached or not. One has also to define the vector $\bm D_i \in \mathbb{R}^{m_i}$ encoding the initial belief about the probability distribution of the states. When no prior information is available, each entry of $\bm D_i$ will be $1/m_i$. In this work, we assume the  likelihood and transition matrices, so the model parameters, to be known. However, one could use the free-energy minimisation to learn them \cite{friston2016AILearning}. Finally, the prior preferences over outcomes (or states), need to be encoded in $\bm C_i\in \mathbb{R}^{m_i}$. Each entry contains a real value for a particular state. The higher the value of a preference, the more preferred the state is, and vice-versa. Priors are formed according to specific desires and they will be used to interface active inference and Behavior Trees.

\subsection{BTs integration: planning preferences, not actions}
\label{sec:subsecPlanOffline}
To achieve a meaningful behavior in the environment through active inference, we need to encode specific desires into the agent's brain, so populate $\bm C_i$ appropriately.

\paragraph*{A prior as Behavior Tree}
We propose to extend the available BT nodes in order to be able to specify desired states to be achieved as leaf nodes. We introduce a new type of leaf nodes called \textit{prior nodes}, indicated with green hexagon. These nodes can be seen as standard action nodes but instead of commanding an action, they simply set the desired value of a state in $\bm C$ and they run active inference for action selection. The prior node is then just a leaf node in the Behavior Tree which returns: \texttt{Success} if a state is achieved, \texttt{Running} while trying to achieve it, or \texttt{Failure} if for some reasons it is not possible to reach the desired state. The return statuses are according to the outcome of our reactive action selection process as explained in Section \ref{sec:completeControlSheme}.

\paragraph*{Sub-goals through BTs}
To reach a distal goal state, we plan achievable sub-goals in the form of desired logical states $l$, according to the available actions that a robot possesses. This idea of using sub-goals was already used in \cite{Kaplan2018}, but in our solution with BTs we provide a task independent way to define sub-goals which is only based on the set of available skills of the robot, such that we can make sure that it can complete the task. At planning time, we define the ideal sequence of states and actions to complete a task such that subsequent sub-goals (or logical desired states) are achievable by means of one action.  This can be done manually or through automated planning. At run-time, however, we only provide the sequence of states to the algorithm, as in Fig.~\ref{fig:planning}.
\begin{figure}[!htb]
    \centering
    \includegraphics[width=0.42\textwidth]{images/planning.pdf}
    \caption{The path among states is planned offline using the available set of actions but only the sequence of states is provided at run-time. Actions are chosen online from the available set with active inference.}
    \label{fig:planning}
\end{figure}

\begin{example}
\label{ex:simpleBT}
\textit{We would like to program the behavior of a our mobile manipulator to navigate to a goal location in a retail store. Example \ref{ex:obs_states} provides the necessary models. To induce a goal oriented behavior with active inference, the BT will set the prior over $s_g$ to $C_g = [1, 0]^\top$ meaning that the robot would like to sense to be at} \texttt{goal}.
\end{example}
A classical BT and a BT for active inference with prior nodes are reported in Fig.~\ref{fig:btSimple}. Note that the action is left out in the BT for active inference because these are selected at runtime. In this particular case, the condition \texttt{isAt(goal)} can be seen as the desired observation to obtain.
\begin{figure}[!htb]
    \centering
    \includegraphics[width=0.4\textwidth]{images/btSimpleBis.pdf}
    \caption{BT to navigate to a location using a classical BT and a BT for active inference. One action \texttt{moveTo(goal)} is available and one condition \texttt{isAt(goal)} provides information if the current location is at the goal. The prior node for active inference (green hexagon) sets the desired prior and runs the action selection process.}
    \label{fig:btSimple}
\end{figure}
\begin{figure*}
    \centering
    \includegraphics[width=0.85\textwidth]{images/newscheme.pdf}
    \caption{Overview of the control architecture for reactive action planning and execution using active inference. Adaptive action selection is performed according to Algorithm \ref{alg:idea}.}
    \label{fig:scheme}
\end{figure*}

Note that the amount of knowledge (i.e. number of states and actions) which is necessary to code a classical BT or our active inference version in Example \ref{ex:simpleBT} is the same. However, we abstract the fallback by planning in the state space and not in the action space. Instead of programming the action \texttt{moveTo(goal)} we only set a prior preference over the state \texttt{isAt(goal)} since the important information is retained in the state to be achieved rather than in the sequence of actions to do so. Action selection through active inference will then select the appropriate skills to match the current state of the world with the desired one, minimizing this discrepancy through free-energy minimization.

\subsection{Action preconditions and conflicts}
Past work on active inference, such as \cite{Kaplan2018}, was based on the assumption that actions were always executable and non-conflicting, but these do not hold in more realistic scenarios.

\paragraph*{Action preconditions in active inference} We propose to encode action preconditions as desired logical states that need to hold to be able to execute a particular action. This is illustrated in the next example.

\begin{example}
\label{ex:movePick}
\textit{We add one more action to the set of skills of our mobile manipulator:} \texttt{Pick(obj)} \textit{and the relative transition matrix $\bm B_h$. The action templates with are extended as follows:}
\begin{table}[h]
\centering
\begin{tabular}{l l l}
    \textbf{Actions}& \textbf{Preconditions}& \textbf{Postconditions}\\
    \texttt{moveTo(goal)} & \texttt{-} & $l_g = [1\ 0]^\top$ \\
    & & $l_r = [1\ 0]^\top$ \\
    \texttt{Pick(obj)} & \texttt{isReachable(obj)}& $l_h = [0\ 1]^\top$\\
\end{tabular}
\end{table}
\begin{align}
\nonumber
     & o_h = \begin{bmatrix} \texttt{isHolding(obj)}\\ \texttt{!isHolding(obj)} \end{bmatrix}\hspace{5mm}
    B_{h} = \begin{bmatrix} 0.95 & 0.9 \\ 0.05 & 0.1
    \end{bmatrix} & \\
    & o_r = \begin{bmatrix} \texttt{isReachable(obj)}\\ \texttt{!isReachable(obj)} \end{bmatrix} &
\end{align}
\vspace{0mm}
\end{example}
where we added a new logical state $l_h$, the relative belief $s_h$ and observation $o_h$, which indicates if the robot is holding the object \texttt{obj}. In the simplest case, we suppose that the only precondition for a successful grasping is that \texttt{obj} is reachable. We then add a logical state $l_r$, as well as $s_r$ and $o_r$, to provide active inference with information about this precondition. $o_r$ can be built for instance trying to compute a grasping pose for a given object. The robot can act on the state $l_h$ through \texttt{Pick}, and it can act on $l_r$ through \texttt{moveTo}.

\paragraph*{Conflicts in active inference}
Given the current belief about the states $\mathcal{L}$ and a prior preference $\bm C$, active inference will select the most appropriate action to execute among the available ones. The preconditions of the selected action are then checked, and if one or more preconditions are not satisfied, the relative logical states are pushed into the corresponding prior with a high preference (i.e. $> 1$). Action selection is then performed again with the updated prior $\bm C$, such that actions that will satisfy missing action preconditions are more likely, as explained in Algorithm~\ref{alg:idea}. This can however lead to conflicts with the original BT \cite{Colledanchise2019}, that is the robot might want to simultaneously achieve two conflicting states. With active inference though, we can represent \textit{which} state is important, but also \textit{when}. Since missing preconditions are added to the current prior with a higher preference with respect to the offline plan, this will induce a behavior that can initially go against the initial BT because the new desire is more appealing to be satisfied. Conflict resolution is then achieved by \textit{locally updating} prior desires about a state, giving them higher preference. The convergence analysis of this approach is reported in Section~\ref{sec:Analysis}.

\subsection{Complete control scheme}
\label{sec:completeControlSheme}
Our solutions is summarised in Algorithm~\ref{alg:idea} and Fig.~\ref{fig:scheme}. At run-time, the BT for a certain task is ticked at a given frequency. The symbolic perception layer takes the sensory readings and translates these continuous quantities into logical observations. This can be achieved through user defined models according to the specific environment and sensors available. The logical observations are used to perform belief updating to keep a probabilistic representation of the world in $\mathcal{S}$. Then, the logical state $\mathcal{L}$ is formed. Every time a \textit{prior} node in the BT is ticked, the corresponding priors in $\bm C$ are set.

For both missing preconditions and conflicts, high priority priors are removed from the preferences $\bm C$ whenever the preconditions are satisfied or the conflicts resolved (lines \texttt{6-10}), allowing to resume the nominal flow of the BT. Active inference from Algorithm~\ref{alg:AIC} is then ran for action selection. If no action is required since the logical state corresponds to the prior, the algorithm returns \texttt{Success}, otherwise the selected action's preconditions are checked and eventually pushed with higher priority. Then, action selection is performed with the updated prior. This procedure is repeated until either an executable action is found, returning \texttt{Running}, or no action can be executed, returning \texttt{Failure}. The case of \texttt{Failure} is handled through the global reactivity provided by the BT. This creates dynamic and stable regions of attraction as explained in Section~\ref{sec:Analysis_DoA}, by means of sequential controller composition \cite{Burridge1999} (lines \texttt{17-31} of Algorithm~\ref{alg:idea}).

The new idea of of using \textit{dynamic priors} instead of static ones as in previous active inference schemes, allows for precondition checking and conflict resolution. A robot can follow a long programmed routine while autonomously taking decisions to locally compensate for unexpected events. This reduces considerably the need for hard-coded fallbacks, allowing to compress the BT to a minimal number of nodes.

\begin{algorithm}
\caption{Pseudo-code for Adaptive Action Selection} \label{alg:idea}
\begin{algorithmic}[1]
\State \textit{Get desired prior and parameters from BT:}
    \State $\bm C$, \texttt{param} $\leftarrow$ BT
\State \textit{Set current observations, beliefs and logical state:}
    \State \texttt{Set} $\mathcal{O},\ \mathcal{S},\ \mathcal{L}$
\State \textit{Remove preferences with high-priority if satisfied:}
\For{all high priority prior $\bm C_i\in \bm C$} {
    \If{ $\bm C_i \subset \mathcal{L}$}
        \State \texttt{Remove pushed priors};
    \EndIf}
\EndFor
\State \textit{Run active inference given} $\mathcal{O},\ \mathcal{S},\ \mathcal{L}$ \textit{and} $\bm C$:
    \State $a_t$ $\leftarrow$ \texttt{Action\_selection($\mathcal{O},\ \mathcal{S},\ \mathcal{L},\ \bm C$)}\Comment{Alg. \ref{alg:AIC}}
    \If{$a_t$ == \texttt{Idle}}
        \State \textbf{return} \texttt{Success}; \Comment{No action required}
   \Else
   \State \textit{Check action preconditions:}
    \While{$a_t$ \texttt{!=Idle}}
            \If{ $l_i \equiv$ \texttt{prec}$_{a_t}$}
                \State \texttt{Execute($a_t$)};
               \State \textbf{return} \texttt{Running}; \Comment{Executing action}
            \Else
            \State \textit{Push missing preconditions in} $\bm C$:
                \State $\bm C \leftarrow$ \texttt{prec}$_{a_t}$;
                \State \textit{Exclude $a_t$ and re-run Alg. \ref{alg:AIC}}:
                \State \texttt{Remove($a_t$)};
                \State $a_t$ $\leftarrow$ \texttt{Action\_selection($\mathcal{O},\ \mathcal{S},\ \mathcal{L},\ \bm C$)}
                \If{\texttt{$a_t==$ Idle }}
                    \State \textbf{return} \texttt{Failure}; \Comment{No solution}
                \EndIf
            \EndIf
     \EndWhile
   \EndIf
\end{algorithmic}
\end{algorithm}

redpajama_set_name: RedPajamaArXiv


New York is now one of a handful of states to put an end to forcing nurses to work overtime. Nurse members from the New York State Public Employees Federation and the New York State United Teachers have been working with several other unions for years to lobby their state legislators to ban mandatory overtime, often sharing their stories of being forced to work double shifts. On June 18, Gov. David Paterson and the state Assembly and Senate agreed on a measure to end mandatory overtime. When the measure takes effect on July 1, 2009, hospitals will no longer be able to require nurses to work more than their regular schedule, except in emergencies or healthcare disasters. The abuses of staff have occurred for far too long, and now it is time to have healthcare managers do the job of staffing, says Anne Goldman, special representative for the Federation of Nurses/United Federation of Teachers. This is a great victory for patients and the nursing workforce.


text:
Home Business Dar holds meeting with LCCI delegation
Dar holds meeting with LCCI delegation
APP110-21 ISLAMABAD: December 21 - Finance Minister Senator Mohammad Ishaq Dar chairing the meeting with the delegation of LCCI. APP
ISLAMABAD, Dec 21 (APP): Minister for Finance Senator Muhammad Ishaq Dar Wednesday held a meeting with a delegation of the Lahore Chamber of Commerce and Industry (LCCI) led by Abdul Basit, President LCCI here and discussed matters pertaining to national economy and the business community.
Welcoming the delegation, Finance Minister recalled that when the present government assumed office in 2013, Pakistan's economy was in a precarious situation and international experts were predicting that it would take Pakistan's economy five years to stabilize.
The Minister highlighted that, contrary to those predictions, Pakistan had managed to achieve macroeconomic stability within two and a half years due to the efforts of the present government.
He said that the government was now focused on achieving higher, sustainable and inclusive economic growth.
Abdul Basit, President of the Lahore Chamber of Commerce and Industry congratulated the Minister over his remarkable achievements in achieving macro-economic stability, structural reforms, merger of three stock exchanges, Companies Bill 2016 and uninterrupted electricity supply to the Industry.
He said the business community highly appreciated these developments and making sincere efforts to boost industrial growth and exports.
He stressed upon the need of focusing on food industry which had huge potential to enhance exports and provide relief to the agriculture sector.
He also extended an invitation to the Finance Minister to visit Lahore Chamber of Commerce and Industry in the near future.
The Finance Minister accepted the LCCI's invitation and briefed the delegation on the turnaround of Pakistan's economy in the last three years, macroeconomic stability, and improvement of energy and security situation in the country, which had provided a conducive atmosphere for foreign direct investment.
The Government had built confidence of the business community and country's outlook is positive, he maintained.
The Finance Minister said that the government was implementing all those things which were promised in the PML (N) election manifesto.
Dar informed the delegation that the OECD (Multilateral Convention on Mutual Administrative assistance in Tax Matters), which he signed on September 14, 2016 in Paris had been ratified by the Pakistani Cabinet.
Pakistani Cabinet also authorized the processing of Pakistan's membership to Open Government Partnership (OGP), he added.
Accordingly, he handed over Pakistan's Letter of Intent for joining OGP to the French President Francois Hollande in the OGP Global Summit held in Paris.
All these measures showed Prime Minister, Muhammed Nawaz Sharif governments' commitment to usher in transparency and good governance in Pakistan, he maintained.
He viewed that these steps had enhanced Pakistan image as a sovereign and prestigious country in the international arena.
The Minister said that world's economists applauded Pakistan's economic performance and British economist Jim O'Neill said in his report that Pakistan had had potential to become the 18th largest economy by 2050 but he was determined to achieve this target much earlier.
He assured the delegation that government would make every possible effort to promote investment and exports.
The delegation also discussed problems being faced in further growth of industry in the country.
Previous articleMinister asks LBs representatives to serve people
Next articleNew election bill to ensure free, fair polls in 2018: Dar
President for merit, transparency in civil awards nominations
Pakistan, France sign MoU to promote bilateral trade, investment

redpajama_set_name: RedPajamaCommonCrawl


With modern technology it is very easy to answer the age old question, "how much longer until we are there?" However this requires a continual, and a bit annoying interaction between parents and kids. We discovered that if Lily can track our progress along a route, she is much more content.
Our first iteration of the follow along map was really basic. If you followed the advice of our blog post titled Finding Our Way, this map will be very easy to create. Simply take a screenshot of the map and place the image in a Word document. Then add in some waypoint markers (I usually use numbers) and print it out. I find the easiest way to add the waypoint markers is to add a text box in the Word document with the number or letter in it and then just place it on the image where you want it.
For a bit more advanced version you and add in small facts or interesting history about the various locations. As RVers, we drive through a ton of towns and places and all of them have a bit of a story. By bringing up a bit of the history of the places you are traveling through it can help spur conversation or even envoke some great imagination time thinking about what life would have been like.