# The Solecki Dichotomy and the Posner-Robinson Theorem are Almost Equivalent

Patrick Lutz  University of California, Los Angeles<EMAIL_ADDRESS>
###### Abstract.

The Solecki dichotomy in descriptive set theory and the Posner-Robinson
theorem in computability theory bear a superficial resemblance to each other
and can sometimes be used to prove the same results, but do not have any
obvious direct relationship. We show that in fact there is such a relationship
by formulating slightly weakened versions of the two theorems and showing
that, when combined with determinacy principles, each one yields a short proof
of the other. This relationship also holds for generalizations of the Solecki
dichotomy and the Posner-Robinson theorem to higher levels of the
Borel/hyperarithmetic hierarchy.

##  1\. Introduction

This paper is about the relationship between two theorems: the Solecki
dichotomy from descriptive set theory, which says that every Borel function on
the reals is either a countable union of continuous functions or at least as
complicated as the Turing jump [12], and the Posner-Robinson theorem in
computability theory, which says that every real is either computable or looks
like $0^{\prime}$ relative to some oracle [13]. We will give formal statements
of both theorems later.

Superficially, these theorems are very similar. Recall that every continuous
function on the reals is computable relative to some oracle. So, allowing for
some poetic license, we might summarize both theorems as saying that every
object of some sort is either computable or at least as complicated as the
jump.

However, it is not apparent whether this similarity is more than superficial.
In the Solecki dichotomy, the objects under consideration are second-
order—functions from the real numbers to the real numbers—while in the Posner-
Robinson theorem they are first order—individual real numbers. Note that this
difference is distinct from the observation that the Solecki dichotomy is a
“bold-face” statement while the Posner-Robinson theorem is a “light-face” one.
Additionally, the superficial analogy seems to suggest that the Solecki
dichotomy should simply say that every function is either continuous (rather
than a countable union of continuous functions) or at least as complicated as
the jump, but this is false.

One indication that there might be something mathematically significant behind
this similarity can be found in work by Kihara. First, Kihara observed [6]
that the Solecki dichotomy could be used to prove a special case of Martin’s
conjecture that had previously been proved by Slaman and Steel in [15] using
the Posner-Robinson theorem. Second, work by Gregoriades, Kihara and Ng [3]
used a version of the Posner-Robinson theorem to prove results related to the
decomposability conjecture that had previously been proved using the Solecki
dichotomy [12, 11].

The goal of this paper is to show that this is no accident—there is a
meaningful technical relationship between the Solecki dichotomy and the
Posner-Robinson theorem. In particular, we will formulate slightly weakened
versions of the Solecki dichotomy and the Posner Robinson theorem111Both of
which suffice to prove the results of Kihara and others mentioned above. and
show that each one can be used to give a short proof of the other222Although
for one direction—proving the Posner-Robinson theorem using the Solecki
dichotomy—we will need to use $\mathbf{\Pi}^{1}_{1}$-determinacy, which is not
provable in $\mathsf{ZFC}$.. The fact that this is possible, along with the
details of the proofs, support the view that the Solecki dichotomy is morally
(though not literally) a bold-face version of the Posner-Robinson theorem.

There are also generalizations of the Solecki dichotomy and the Posner-
Robinson theorem to higher levels of the Borel/hyperarithmetic hierarchy and
all of our results go through for these generalizations, with the proofs more
or less unchanged. We discuss this further in Section 4.

In the remainder of the introduction, we will introduce the Solecki dichotomy
and the Posner-Robinson theorem, as well as the weakened versions that we will
use in this paper. We will also briefly discuss determinacy principles, which
provide the main technical tool that we will use in our proofs.

### The Solecki dichotomy

Informally, the Solecki dichotomy says that every sufficiently definable
function from reals to reals is either a countable union of continuous
functions or at least as complicated as the Turing jump333Actually, most
published statements of the Solecki dichotomy use a function called
“Pawlikowski’s function” in place of the Turing jump, but it is not hard to
see that these two versions of the theorem are equivalent. To state it
formally, we must first state precisely what we mean by “a countable union of
continuous functions” and “at least as complicated as the Turing jump.”

######  Definition 1.1.

A function $f\colon\omega^{\omega}\to\omega^{\omega}$ is _$\sigma$
-continuous_ if there is a partition $\\{A_{n}\\}_{n\in\omega}$ of
$\omega^{\omega}$ into countably many pieces such that for each $n$,
$f\operatorname{\upharpoonright}_{A_{n}}$ is continuous with respect to the
subspace topology on $A_{n}$.

Note that there is a small subtlety here: just because
$f\operatorname{\upharpoonright}_{A_{n}}$ is continuous with respect to the
subspace topology on $A_{n}$ does not mean that
$f\operatorname{\upharpoonright}_{A_{n}}$ can be extended to a continuous
function defined on all of $\omega^{\omega}$. We will also refer to a partial
function which is continuous with respect to the subspace topology on its
domain as a _partial continuous function_.

######  Definition 1.2.

A function $f\colon\omega^{\omega}\to\omega^{\omega}$ _topologically embeds_
into a function $g\colon\omega^{\omega}\to\omega^{\omega}$ if there are
topological embeddings $\varphi,\psi\colon\omega^{\omega}\to\omega^{\omega}$
such that $\psi\circ f=g\circ\varphi$. In other words, the following diagram
commutes.

${\omega^{\omega}}$${\omega^{\omega}}$${\omega^{\omega}}$${\omega^{\omega}}$$\scriptstyle{g}$$\scriptstyle{f}$$\scriptstyle{\varphi}$$\scriptstyle{\psi}$

######  Definition 1.3.

The _Turing jump_ is the function $J\colon\omega^{\omega}\to\omega^{\omega}$
defined by

$J(x)(n)\vcentcolon=\begin{cases}0&\text{if }\Phi^{x}_{n}(n)\uparrow\\\
m+1&\text{if }\Phi^{x}_{n}(n)\downarrow\text{ in exactly $m$
steps}.\end{cases}$

Note that our official definition of the Turing jump is slightly different
from the standard one, in which $J(x)(n)$ only indicates whether or not
$\Phi^{x}_{n}(n)$ converges, not how many steps it takes to converge. This is
necessary for Theorem 1.4, but it doesn’t matter anywhere else in this
paper—in other words, after the statement of Theorem 1.4, the entire remainder
of the paper can be read as if we had defined $J$ in the usual way instead of
the definition given above.

######  Theorem 1.4 (Solecki dichotomy).

For every Borel function $f\colon\omega^{\omega}\to\omega^{\omega}$, either
$f$ is $\sigma$-continuous or the Turing jump topologically embeds into $f$.

Theorem 1.4 was first proved by Solecki in [16] in the special case where $f$
is of Baire class $1$. It was extended to all Borel functions by Zapletal in
[17] and to all analytic functions by Pawlikowski and Sabok in [12]. It is
also known to hold for all functions under $\mathsf{AD}$ [17].

We will now state two weaker versions of the Solecki dichotomy, obtained by
replacing topological embeddability with weaker notions of reducibility
between functions.

######  Definition 1.5.

A function $f\colon\omega^{\omega}\to\omega^{\omega}$ is _reducible_ 444This
notion of reducibility has also been called _strong continuous Weihrauch
reducibility_ [1] and _continuous reducibility_ (by Carroy [2]). to a function
$g\colon\omega^{\omega}\to\omega^{\omega}$, written $f\leq g$, if there are
partial continuous functions
$\varphi,\psi\colon\omega^{\omega}\to\omega^{\omega}$ such that for all
$x\in\omega^{\omega}$, $f(x)=\psi(g(\varphi(x)))$. In other words, the
following diagram commutes

${\omega^{\omega}}$${\omega^{\omega}}$${\omega^{\omega}}$${\omega^{\omega}}$$\scriptstyle{g}$$\scriptstyle{\psi}$$\scriptstyle{f}$$\scriptstyle{\varphi}$

Note that this definition implies that $\varphi$ is actually total and that
$\operatorname{range}(g\circ\varphi)\subseteq\operatorname{dom}(\psi)$.

######  Theorem 1.6 (Solecki dichotomy, version 2).

For every Borel function $f\colon\omega^{\omega}\to\omega^{\omega}$, either
$f$ is $\sigma$-continuous or $J\leq f$.

Note that if $f$ topologically embeds into $g$ then $f$ is also reducible to
$g$: if $\varphi$ and $\psi$ are topological embeddings such that $\psi\circ
f=g\circ\varphi$ then by definition, $\psi^{-1}$ is a partial continuous
function and $f=\psi^{-1}\circ g\circ\varphi$. Hence version 2 of the Solecki
dichotomy above really is a weakened version of the original Solecki
dichotomy.

Before going further, let’s try to understand this notion of reducibility a
little better. Suppose that $f$ is reducible to $g$ via partial continuous
functions $\varphi$ and $\psi$—i.e. that $f=\psi\circ g\circ\varphi$. Then the
task of evaluating $f$ at a given point can be achieved by evaluating $g$ at a
single point, together with some continuous pre- and post-processing using
$\varphi$ and $\psi$, respectively.

This way of understanding reducibility suggests another, slightly weaker,
notion: instead of only allowing $\psi$ to use $g(\varphi(x))$ in the post-
processing step, why not allow it to use the original input, $x$, as well?
Using this weakened notion of reducibility yields our final version of the
Solecki dichotomy, which is the version we will use for the rest of the paper.

######  Definition 1.7.

A function $f\colon\omega^{\omega}\to\omega^{\omega}$ is _weakly reducible_
555Also known as _continuous Weihrauch reducible_. to a function
$g\colon\omega^{\omega}\to\omega^{\omega}$, written $f\leq_{w}g$, if there are
partial continuous functions $\varphi\colon\omega^{\omega}\to\omega^{\omega}$
and $\psi\colon\omega^{\omega}\times\omega^{\omega}\to\omega^{\omega}$ such
that for all $x\in\omega^{\omega}$, $f(x)=\psi(g(\varphi(x)),x)$.

######  Theorem 1.8 (Solecki dichotomy, version 3).

For every Borel function $f\colon\omega^{\omega}\to\omega^{\omega}$, either
$f$ is $\sigma$-continuous or $J\leq_{w}f$.

### The Posner-Robinson theorem

Informally, the Posner-Robinson theorem says that every real $x$ is either
computable or “looks like” $0^{\prime}$ relative to some real $y$. Formally
stated, it reads as follows.

######  Theorem 1.9 (Posner-Robinson theorem).

For every real $x$, either $x$ is computable or there is some real $y$ such
that $x\oplus y\geq_{T}y^{\prime}$.

This theorem was first proved by Posner and Robinson in [13] and extended by
Jockusch and Shore [4] and Shore and Slaman [14]. As usual, there is also a
relativized version of this theorem.

######  Theorem 1.10 (Posner-Robinson theorem, relativized version).

For every real $z$ and every real $x$, either $x\leq_{T}z$ or there is some
real $y$ such that $x\oplus y\oplus z\geq_{T}(y\oplus z)^{\prime}$.

We can weaken this relativized version of the Posner-Robinson theorem by
requiring the conclusion to hold not for every $z$, but only for all $z$ in
some cone of Turing degrees.

######  Definition 1.11.

A _cone of Turing degrees_ is a set of the form $\\{x\in\omega^{\omega}\mid
x\geq_{T}y\\}$ for some fixed real $y$, called the _base_ of the cone.

######  Theorem 1.12 (Posner-Robinson theorem, cone version).

There is a cone of Turing degrees, $C$, such that for every $z\in C$ and every
real $x$, either $x\leq_{T}z$ or there is some real $y$ such that $x\oplus
y\oplus z\geq_{T}(y\oplus z)^{\prime}$.

### Determinacy principles

As we mentioned earlier, determinacy principles are the main technical tool in
our proofs. In this section, we will state the main theorems about determinacy
that we need, as well as a useful corollary of these theorems.

Recall that determinacy principles involve games of the following form: two
players, called player 1 and player 2, alternate playing natural numbers. Each
player can see all previous moves by the other player. At the end, they have
jointly formed a sequence $x\in\omega^{\omega}$. To determine the winner, we
have some fixed set $A\subseteq\omega^{\omega}$, called the _payoff set_.
Player 1 wins if $x\in A$ and otherwise player 2 wins. The game with payoff
set $A$ is sometimes denoted $G(A)$.

In principle, it is possible that for a fixed payoff set $A$, neither player
has a winning strategy. When one of the two players does have a winning
strategy, the game $G(A)$ is said to be _determined_. Determinacy principles
assert that when $A$ is sufficiently definable, $G(A)$ must be determined. For
example, Martin proved that whenever $A$ is Borel, $G(A)$ is determined [9].

######  Theorem 1.13 (Borel determinacy).

For every Borel set $A\subseteq\omega^{\omega}$, $G(A)$ is determined.

Determinacy principles for sets which are not Borel are typically not provable
in $\mathsf{ZFC}$. However, they are usually provable from large cardinal
principles. For example, Martin proved that if there is a measurable cardinal
then all games with $\mathbf{\Pi}^{1}_{1}$ payoff sets are determined [10].

######  Theorem 1.14 (Analytic determinacy).

Assume that there is a measurable cardinal. Then for every
$\mathbf{\Pi}^{1}_{1}$ set $A\subseteq\omega^{\omega}$, $G(A)$ is determined.

There is also an axiom, known as the _Axiom of Determinacy_ and abbreviated
$\mathsf{AD}$, which states that for _all_ sets $A\subseteq\omega^{\omega}$,
$G(A)$ is determined. This axiom is incompatible with the axiom of choice, but
it is consistent with $\mathsf{ZF}$ [5].

######  Theorem 1.15.

Assuming that $\mathsf{ZF}+\text{``there are infinitely many Woodin
cardinals''}$ is consistent, so is $\mathsf{ZF}+\mathsf{AD}$.

Martin has also proved a corollary of determinacy which is often useful in
computability theory and which we will use below. To state it we need a few
more definitions.

######  Definition 1.16.

A set $A\subseteq\omega^{\omega}$ is _cofinal in the Turing degrees_ (or
sometimes just _cofinal_) if for every $x\in\omega^{\omega}$ there is some
$y\in A$ such that $y\geq_{T}x$.

Note that if a set $A\subseteq\omega^{\omega}$ does not contain a cone of
Turing degrees then its complement must be cofinal (and vice-versa).

######  Definition 1.17.

A _pointed perfect tree_ is a tree $T$ on $\omega$ such that

  1. (1)

$T$ has no dead ends—i.e. every node has at least one child.

  2. (2)

$[T]$ has no isolated paths—i.e. every node has incomparable descendants.

  3. (3)

Every path $x\in[T]$ computes $T$.

It is not too hard to show that if $T$ is a pointed perfect tree then $[T]$ is
cofinal in the Turing degrees. Martin showed that determinacy implies a
partial converse of this: if $A$ is cofinal then there is some pointed perfect
tree $T$ such that $[T]\subseteq A$ [8, 15]. Moreover, the amount of
determinacy required to prove this matches the complexity of $A$.

######  Theorem 1.18.

Suppose $A\subseteq\omega^{\omega}$ is cofinal in the Turing degrees. Then:

  * •

If $A$ is Borel, $A$ contains $[T]$ for some pointed perfect tree $T$.

  * •

If $\mathbf{\Pi}^{1}_{1}$-determinacy holds and $A$ is $\mathbf{\Pi}^{1}_{1}$
then $A$ contains $[T]$ for some pointed perfect tree $T$.

  * •

If $\mathsf{AD}$ holds and $A$ is any set then $A$ contains $[T]$ for some
pointed perfect tree $T$.

There is a simple observation that yields a useful strengthening of this
theorem. Namely, suppose $\\{A_{n}\\}_{n\in\omega}$ is a countable sequence of
subsets of $\omega^{\omega}$ whose union is cofinal in the Turing degrees.
Then there must be some $n$ such that $A_{n}$ is cofinal in the Turing
degrees. Thus we have the following theorem.

######  Theorem 1.19.

Suppose $\langle A_{n}\rangle_{n\in\omega}$ is a countable sequence such that
$\bigcup_{n\in\omega}A_{n}$ is cofinal in the Turing degrees. Then:

  * •

If each $A_{n}$ is Borel then there is some $n$ and pointed perfect tree $T$
such that $A_{n}$ contains $[T]$.

  * •

If $\mathbf{\Pi}^{1}_{1}$-determinacy holds and each $A_{n}$ is
$\mathbf{\Pi}^{1}_{1}$ then there is some $n$ and pointed perfect tree $T$
such that $A_{n}$ contains $[T]$.

  * •

If $\mathsf{AD}$ holds then there is some $n$ and pointed perfect tree $T$
such that $A_{n}$ contains $[T]$.

##  2\. Posner-Robinson $\implies$ Solecki

In this section, we will assume a version of the Posner-Robinson theorem
(specifically Theorem 1.12) and use it to prove a version of the Solecki
dichotomy (specifically Theorem 1.8). Here’s a brief outline of the proof.
First, for any functions $f,g\colon\omega^{\omega}\to\omega^{\omega}$, we will
introduce a game, $G(f,g)$, and show that player 2 has a winning strategy in
this game if and only if $f\leq_{w}g$. We will then show that in the special
case of the game $G(J,f)$, player 1 has a winning strategy if and only if $f$
is $\sigma$-continuous. It is in this step that we will make use of the
Posner-Robinson theorem. Finally, it will be clear from the definition of
$G(f,g)$ that as long as $f$ and $g$ are both Borel functions then the payoff
set of $G(f,g)$ is also Borel. Thus by Borel determinacy, if
$f\colon\omega^{\omega}\to\omega^{\omega}$ is Borel then either player 1 wins
$G(J,f)$ or player 2 does. In the first case, $f$ is $\sigma$-continuous and
in the second case, $J\leq_{w}f$ and so we have reached the dichotomy in the
statement of Theorem 1.8.

The game $G(f,g)$ is played as follows: player 2 first plays a code
$e\in\omega$ for a three place Turing functional666Here we use the phrase
_Turing functional_ to indicate a partial computable function on real
numbers.. For the rest of the game, player 1 plays a real $x$ and player 2
plays two reals, $y$ and $z$. On every turn, player 1 will play one more digit
of the real $x$ and player 2 will play one more digit of the the real $z$ and
either one or zero more digits of the real $y$. Player 2 wins if they
eventually play all digits of $y$ (in other words, player 2 can delay
arbitrarily long between playing one digit of $y$ and the next but if they
delay forever then they forfeit the game) and $f(x)=\Phi_{e}(g(y),x,z)$.
Otherwise, player 1 wins. The game can be pictured as follows.

$\displaystyle\begin{array}[]{c | c c c c c c c c c c l}\text{player }1&&x_{0}&&x_{1}&&\ldots&x_{n}&&\ldots&&x=x_{0}x_{1}x_{2}\ldots\\\ \cline{1-10}\cr\text{player }2&e&&y_{0},z_{0}&&z_{1}&\ldots&&y_{1},z_{n}&\ldots&&y=y_{0}y_{1}y_{2}\ldots,\quad z=z_{0}z_{1}z_{2}\ldots\end{array}$

We can understand this game as follows. First recall that $f\leq_{w}g$ means
that there are partial continuous functions $\varphi$ and $\psi$ such that for
all $x$, $f(x)=\psi(g(\varphi(x)),x)$. Further, recall that a continuous
function is just a computable function relative to some oracle. Hence for some
code $e\in\omega$ for a Turing functional and some $z\in\omega^{\omega}$,
$\psi(x,y)=\Phi_{e}(x,y,z)$.

In the game $G(f,g)$, player 2 is trying to convince player 1 that
$f\leq_{w}g$. The natural number $e$ and real $z$ played by player 2 should be
thought of as specifying the continuous function $\psi$. Player 1’s moves
consist of a challenge input $x$ for $f$ and the real $y$ played by player 2
corresponds to $\varphi(x)$. The winning condition for player 2—that player 2
plays infinitely many digits of $y$ and that
$f(x)=\Phi_{e}(g(y),x,z)$—corresponds to the reduction procedure implicitly
specified by player 2 working successfully on input $x$.

######  Lemma 2.1.

Player 2 wins $G(f,g)$ if and only if $f\leq_{w}g$.

###### Proof.

$(\implies)$ Suppose that player 2 wins $G(f,g)$ via the strategy $\tau$. Then
the following two procedures describe partial continuous functions
$\omega^{\omega}\to\omega^{\omega}$ and
$\omega^{\omega}\times\omega^{\omega}\to\omega^{\omega}$, respectively.

  1. (1)

Given $x$ as input: play the game $G(f,g)$, using the digits of $x$ as player
1’s moves and using $\tau$ to generate player 2’s moves. Output the first of
the two reals played by player 2 (the real referred to as $y$ in the
description of the game above).

  2. (2)

Given $w$ and $x$ as input: play the game $G(f,g)$ using the digits of $x$ as
player 1’s moves and using $\tau$ to generate player 2’s moves. Let $e$ be
number played by $\tau$ on the first move of the game and let $z$ be the
second of the two reals played by player 2. Output $\Phi_{e}(w,x,z)$.

Let $\varphi$ and $\psi$, respectively, denote these two continuous functions.
Then the fact that $\tau$ is a winning strategy for player 2 in the game
$G(f,g)$ ensures that for all $x$, $f(x)=\psi(g(\varphi(x)),x)$.

$(\impliedby)$ Suppose that $f\leq_{w}g$ via partial continuous functions
$\varphi$ and $\psi$. Let $e\in\omega$ and $z\in\omega^{\omega}$ be such that
$\psi$ is computed by the $e^{\text{th}}$ Turing functional with oracle $z$.
Then the following is a winning strategy for player 2 in the game $G(f,g)$. On
the first turn, play the number $e$. On each subsequent turn, play one more
digit of $z$. Also on each of these turns, if player 1 has played enough
digits of $x$ to determine one more digit of $\varphi(x)$, play that as well.
∎

We now turn to the case where player 1 wins and the game is of the form
$G(J,f)$ for some $f$. We will show that in this case, $f$ must be
$\sigma$-continuous. To prove this, we first need the following observation
about $\sigma$-continuity.

######  Observation 2.2.

A function $f\colon\omega^{\omega}\to\omega^{\omega}$ is $\sigma$-continuous
if and only if there is some real $z$ such that for all $x$,
$f(x)\leq_{T}x\oplus z$.

###### Proof.

If $f$ is $\sigma$-continuous then it can be written as a countable union of
partial continuous functions. Each partial continuous function on
$\omega^{\omega}$ is a partial computable function relative to some oracle, so
we can find a countable sequence of codes for Turing functionals
$\\{e_{n}\\}_{n\in\omega}$ and oracles $\\{z_{n}\\}_{n\in\omega}$ such that
for each $x$, $f(x)=\Phi_{e_{n}}(x,z_{n})$ for some $n$. So if we take
$z=\bigoplus_{n\in\omega}z_{n}$ then for each $x$, $f(x)\leq_{T}x\oplus z$.

Conversely, suppose there is some $z$ such that for all $x$,
$f(x)\leq_{T}x\oplus z$. For each $n$, define $A_{n}=\\{x\mid
f(x)=\Phi_{n}(x,z)\\}$. Then $\\{A_{n}\\}_{n\in\omega}$ is a countable
sequence of sets whose union covers $\omega^{\omega}$. Also, for each $n$,
$f\operatorname{\upharpoonright}_{A_{n}}$ is computable relative to $z$ via
$\Phi_{n}$ and hence continuous. So $f$ is $\sigma$-continuous. ∎

######  Lemma 2.3.

Player 1 wins $G(J,f)$ if and only if $f$ is $\sigma$-continuous.

###### Proof.

$(\implies)$ Suppose that player 1 wins $G(J,f)$ via the strategy $\sigma$.
Let $w$ be the base of a cone for which the conclusion of Theorem 1.12 applies
(i.e. such that the Posner-Robinson theorem holds relative to every real which
computes $w$).

We claim that for every $y$, $f(y)\leq_{T}y\oplus\sigma\oplus w$ and hence $f$
is $\sigma$-continuous by Observation 2.2. To prove this, we will show that if
not then $\sigma$ is not actually a winning strategy for player 1. So suppose
that there is some $y$ such that $f(y)\nleq_{T}y\oplus\sigma\oplus w$. Since
the Posner-Robinson theorem holds relative to $y\oplus\sigma\oplus w$, we can
find some real $v$ such that $f(y)\oplus v\oplus y\oplus\sigma\oplus
w\geq_{T}(v\oplus y\oplus\sigma\oplus w)^{\prime}$.

We will now explain how to win while playing as player 2 in $G(J,f)$ against
the strategy $\sigma$. We will play as follows: first we play some number
$e\in\omega$, which we will explain how to choose later. Then we ignore player
1’s moves entirely and play the reals $y$ and $z=v\oplus y\oplus\sigma\oplus
w$. Note that from $z$ we can compute player 1’s moves since $z$ computes both
player 1’s strategy $\sigma$ and all of player 2’s moves. In other words, if
$x$ is the real played by player 1 then $x\leq_{T}z$. Hence by our choice of
$z$ we have

$x^{\prime}\leq_{T}z^{\prime}\leq_{T}f(y)\oplus z.$

This is almost what we want, but there is one problem: for player 2 to win, we
need not just that $f(y)\oplus z$ computes $x^{\prime}$, but that it does so
via the Turing functional specified by player 2. And the only problem with
this is that the Turing functional which computes $x^{\prime}$ from $f(y)$ and
$z$ depends on the code $e$ played by player 2. However, we can get around
this by using the recursion theorem.

In precisely, note that while the computation of $x^{\prime}$ from $f(y)\oplus
z$ depends on the value of $e$ (because the value of $x$ itself depends on
$e$), the dependence is uniform in $e$777This is because the computation of
$z^{\prime}$ from $f(y)\oplus z$ does not depend on $e$ and the computation of
$x$ from $z$, and hence $x^{\prime}$ from $z^{\prime}$ is uniform in $e$.. In
other words, there is some $a\in\omega$ such that for all $e$,

$\Phi_{a}(f(y),z,e)=(\sigma*(e,y,z))^{\prime}$

where by $(\sigma*(e,y,z))$ we mean the real played by the strategy $\sigma$
in response to player 2 playing $e$ along with the reals $y$ and $z$. Thus by
the recursion theorem, we can find some $e$ such that

$\Phi_{e}(f(y),z)=\Phi_{a}(f(y),z,e)=(\sigma*(e,y,z))^{\prime}.$

Thus by playing this $e$ as our first move as player 2 (and then playing $y$
and $z$), we can win against $\sigma$.

$(\impliedby)$ Suppose that $f$ is $\sigma$-continuous. Thus by our
observation, there is some $w$ such that for all $x$, $f(x)\leq_{T}x\oplus w$.
Consider the following strategy for player 1 in the game $G(J,f)$: alternate
playing digits of $w$ and copying the moves played by player 2. We can picture
this strategy as follows.

$\displaystyle\begin{array}[]{c | c c c c c c c c c}\text{player }1&&w_{0}&&\langle y_{0},z_{0}\rangle&&w_{1}&&\langle z_{1}\rangle&\ldots\\\ \cline{1-10}\cr\text{player }2&e&&y_{0},z_{0}&&z_{1}&&y_{1},z_{2}&&\ldots\end{array}$

We claim this is a winning strategy for player 1. To see why, suppose player 1
follows this strategy and that player 2 plays $e\in\omega$ and
$y,z\in\omega^{\omega}$. Then the real $x$ played by player 1 will compute
$w\oplus y\oplus z$. Player 2 can only win if $\Phi_{e}(f(y),x,z)=J(x)$, but
this is impossible since we have

$f(y)\leq_{T}y\oplus w\leq_{T}x$

and hence $\Phi_{e}(f(y),x,z)\leq_{T}x$, but $J(x)\nleq_{T}x$. ∎

We can now finish our proof of the Solecki dichotomy from the Posner-Robinson
theorem.

###### Proof of Theorem 1.8 from Theorem 1.12.

Let $f\colon\omega^{\omega}\to\omega^{\omega}$ be a Borel function and
consider the game $G(J,f)$. By Borel determinacy, either player 1 or player 2
has a winning strategy for this game. In the former case, $f$ is
$\sigma$-continuous by Lemma 2.3. In the latter case, $J\leq_{w}f$ by Lemma
2.1. ∎

The results of this section raise an obvious question. Namely, is it possible
to use the Posner-Robinson theorem to prove the full Solecki dichotomy (i.e.
either Theorem 1.4 or Theorem 1.6)? Let us mention one possible route to such
a proof. In this section, we described a game, $G(f,g)$, which can be used to
characterize weak reducibility of $f$ to $g$ and this game was the key to our
proof of Theorem 1.8. It seems plausible that finding a game which
characterizes reducibility of $f$ to $g$, rather than weak reducibility, would
yield a proof of Theorem 1.6. Finding such a game might also be of independent
interest.

######  Question 2.4.

Can the Posner-Robinson theorem together with Borel determinacy be used to
prove either Theorem 1.4 or Theorem 1.6?

######  Question 2.5.

Is there a game characterizing reducibility in the same way that the game
$G(f,g)$ described above characterizes weak reducibility?

##  3\. Solecki $\implies$ Posner-Robinson

In this section we will assume a version of the Solecki dichotomy
(specifically Theorem 1.8) and use it to prove a version of the Posner-
Robinson theorem (specifically Theorem 1.12). We will do so by proving the
contrapositive: we will show that if Theorem 1.12 fails then so does Theorem
1.8. Also, as we mentioned in the introduction, our proof is carried out
assuming $\mathbf{\Pi}^{1}_{1}$-determinacy, a statement which is not provable
in $\mathsf{ZFC}$, but which is provable from $\mathsf{ZFC}$ plus the
existence of a measurable cardinal.

The core idea of the proof is very simple—it essentially consists of the
observation that if $f$ is a function which takes each real $x$ to a witness
of the failure of the Posner-Robinson theorem relative to $x$ then $f$ does
not satisfy the conclusion of the Solecki dichotomy. However, this simple idea
is complicated by the need to make sure $f$ is Borel (otherwise we cannot
invoke Theorem 1.8). Most of the details of the proof will be devoted to
overcoming this obstacle.

We will now go into the details of the proof. Suppose that Theorem 1.12 fails.
In other words, the set

$A=\\{x\in\omega^{\omega}\mid\text{the Posner-Robinson theorem holds relative
to }x\\}$

does not contain any cone of Turing degrees. Hence its complement, the set

$B=\\{x\in\omega^{\omega}\mid\text{the Posner-Robinson theorem fails relative
to }x\\},$

is cofinal in the Turing degrees.

Now suppose that we can find a function $f\colon B\to\omega^{\omega}$ such
that for each $x$ in $B$, $f(x)$ is a witness to the failure of the Posner-
Robinson theorem relative to $x$—i.e. $f(x)\nleq_{T}x$ and there is no $y$
such that $f(x)\oplus y\oplus x\geq_{T}(y\oplus x)^{\prime}$. Extend $f$ to a
total function on $\omega^{\omega}$ by setting $f(x)=0$ for all $x\notin B$.
Note that this modified version of $f$ has the following two properties.

  1. (1)

For cofinally many $x$, $f(x)\nleq_{T}x$.

  2. (2)

For all $x$, there is no $y$ such that $f(x)\oplus y\oplus x\geq_{T}(y\oplus
x)^{\prime}$. When $x\in B$ this is by assumption and when $x\notin B$ this is
because $f(x)$ is computable.

The next two lemmas show that these properties imply that $f$ is a
counterexample to the Solecki dichotomy.

######  Lemma 3.1.

Suppose that $f\colon\omega^{\omega}\to\omega^{\omega}$ is a function such
that for a set of $x$ which is cofinal in the Turing degrees,
$f(x)\nleq_{T}x$. Then $f$ is not $\sigma$-continuous.

###### Proof.

For contradiction, assume $f$ is $\sigma$-continuous. By Observation 2.2,
there must be some $z$ such that for every $x$, $f(x)\leq_{T}x\oplus z$. By
assumption, we can find some $x\geq_{T}z$ such that $f(x)\nleq_{T}x$. But
since $x\equiv_{T}x\oplus z$, this implies $f(x)\nleq_{T}x\oplus z$, which
contradicts our choice of $z$. ∎

######  Lemma 3.2.

Suppose that $f\colon\omega^{\omega}\to\omega^{\omega}$ is a function such
that for all $x$, there is no $y$ such that $f(x)\oplus y\oplus
x\geq_{T}(y\oplus x)^{\prime}$. Then $J\nleq_{w}f$.

###### Proof.

For contradiction, assume that $J\leq_{w}f$. Thus there are partial continuous
functions $\varphi$ and $\psi$ such that for all $x$,
$J(x)=\psi(f(\varphi(x)),x)$. Let $z$ be an oracle relative to which $\psi$
and $\varphi$ are computable. Let $x=\varphi(z)$. By assumption, there is no
$y$ such that $f(x)\oplus y\oplus x\geq_{T}(y\oplus x)^{\prime}$. We claim
this is contradicted by taking $y=z$.

To see why, note that since $\varphi$ and $\psi$ are computable relative to
$z$, we have

$x=\varphi(z)\leq_{T}z\qquad\text{and}\qquad\psi(f(x),z)\leq_{T}f(x)\oplus z$

and by our choice of $\varphi$ and $\psi$ we have

$z^{\prime}=\psi(f(\varphi(z)),z)=\psi(f(x),z).$

Hence we have

$(z\oplus x)^{\prime}\equiv_{T}z^{\prime}=\psi(f(x),z)\leq_{T}f(x)\oplus
z\leq_{T}f(x)\oplus z\oplus x.$

which yields the contradiction. ∎

We are now left with the problem of finding some $f\colon B\to\omega^{\omega}$
with the properties described above. Of course, it is easy to find such an $f$
using the Axiom of Choice, but there is no reason to believe that a function
chosen in this way will be Borel and hence we cannot apply Theorem 1.8.
Instead of using choice, we could try to appeal to a uniformization theorem
from descriptive set theory. However, the relation that we need to uniformize,
namely

$\\{(x,y)\mid y\nleq_{T}x\text{ and }\forall z\,(y\oplus z\oplus
x\ngeq_{T}(z\oplus x)^{\prime}\\},$

is $\Pi^{1}_{1}$ and thus too complicated for any of the standard
uniformization theorems to give us a Borel—or even analytic—uniformizing
function.

We will now see how to find some $f$ with the necessary properties which is
Borel (in fact, Baire class 1). The key step is the following lemma.

######  Lemma 3.3.

Suppose that for cofinally many $x$, the Posner-Robinson theorem fails
relative to $x$. Then for cofinally many $x$, there is some
$y\leq_{T}x^{\prime}$ which witnesses this failure—i.e. such that
$y\nleq_{T}x$ and there is no $z$ such that $y\oplus z\oplus x\geq_{T}(z\oplus
x)^{\prime}$.

###### Proof.

Let $w\in\omega^{\omega}$ be arbitrary. We need to show that there is some
$x\geq_{T}w$ such that the Posner-Robinson theorem fails relative to $x$ and
such that this failure is witnessed by some $y\leq_{T}x^{\prime}$. By
increasing $w$ if necessary (and invoking our assumption that the Posner-
Robinson theorem fails cofinally), we may assume the Posner-Robinson theorem
fails relative to $w$. Let $y$ be a witness to the failure of the Posner-
Robinson theorem relative to $w$.

The key observation is that it is sufficient to find some $x\geq_{T}w$ such
that $x^{\prime}$ computes $y$ but $x$ does not. Suppose we can find such an
$x$. We claim that the Posner-Robinson theorem fails relative to $x$ and that
this failure is witnessed by $y$. If not, then we can find some $z$ such that
$y\oplus z\oplus x\geq_{T}(z\oplus x)^{\prime}$. But since $x\geq_{T}w$, this
gives us

$y\oplus z\oplus x\oplus w\equiv_{T}y\oplus z\oplus x\geq_{T}(z\oplus
x)^{\prime}\equiv_{T}(z\oplus x\oplus w)^{\prime}$

and hence $y$ is _not_ a witness to the failure of the Posner-Robinson theorem
relative to $w$.

We will now explain how to construct $x$. In fact, we will actually construct
a real $x_{0}$ such that $(x_{0}\oplus w)^{\prime}$ computes $y$ but
$x_{0}\oplus w$ does not and then set $x=x_{0}\oplus w$. The construction is
similar to the proof of Friedberg jump inversion. We will construct $x_{0}$ by
finite initial segments. On step $e$ of the construction, we will make sure
that $\Phi_{e}^{x_{0}\oplus w}$ does not correctly compute $y$ and then code
one more digit of $y$.

Suppose we are on step $e$ of the construction and the initial segment of
$x_{0}$ that we have built so far is $\sigma_{e}$. There are two cases to
consider.

  1. (1)

There is some $n\in\omega$ and strings $\tau_{0},\tau_{1}$ such that
$\Phi_{e}^{\sigma_{e}^{\smallfrown}\tau_{0}\oplus
w}(n)\downarrow\neq\Phi_{e}^{\sigma_{e}^{\smallfrown}\tau_{1}\oplus
w}(n)\downarrow$. In this case, one of these two values must disagree with
$y(n)$. Let $\langle n,\tau_{0},\tau_{1}\rangle$ be the first such triple
discovered in some $w$-computable search and set
$\sigma_{e+1}=\sigma_{e}^{\smallfrown}\tau_{i}^{\smallfrown}\langle
y(e)\rangle$ where $\tau_{i}$ is equal to whichever of $\tau_{0},\tau_{1}$
causes $\Phi_{e}^{x_{0}\oplus w}(n)$ to disagree with $y(n)$.

  2. (2)

For every $n\in\omega$, there is at most one value of
$\Phi_{e}^{\sigma_{e}^{\smallfrown}\tau\oplus w}(n)$ obtainable over all
strings $\tau$. Then by standard arguments, if $x_{0}$ extends $\sigma_{e}$
then either $\Phi_{e}^{x_{0}\oplus w}$ is not total or it computes a real
which is computable from $w$ alone. In either case, $\Phi_{e}^{x_{0}\oplus w}$
cannot be equal to $y$ so we may simply set
$\sigma_{e+1}=\sigma_{e}^{\smallfrown}\langle y(e)\rangle$.

It is clear from the construction that $x_{0}\oplus w$ does not compute $y$.
To see that $(x_{0}\oplus w)^{\prime}$ computes $y$, simply note that
$(x_{0}\oplus w)^{\prime}$ can figure out what happened at each step of the
construction described above (i.e. it can check which of the two cases held at
each step and, in the first case, recover the triple $\langle
n,\tau_{0},\tau_{1}\rangle$) and can thus recover the digits of $y$ coded
during the construction. ∎

We can now prove Theorem 1.12. As we mentioned above, our proof uses
$\mathbf{\Pi}^{1}_{1}$-determinacy.

###### Proof of Theorem 1.12 from Theorem 1.8.

Suppose Theorem 1.12 fails. Then as we saw above, the set

$B=\\{x\in\omega^{\omega}\mid\text{the Posner-Robinson theorem fails relative
to $x$}\\}$

is cofinal in the Turing degrees and hence by Lemma 3.3, the following set is
also cofinal

$\displaystyle C=\\{x\in\omega^{\omega}\mid\exists y\leq_{T}x^{\prime}\,($
$\displaystyle y\text{ witnesses the failure of the}$
$\displaystyle\text{Posner-Robinson theorem relative to $x$})\\}.$

Now for each $e\in\omega$, define

$\displaystyle C_{e}=\\{x\in\omega^{\omega}\mid\Phi_{e}(x^{\prime})$ is total
and witnesses the failure of the $\displaystyle\text{ Posner-Robinson theorem
relative to $x$}\\}$

and note that $C=\bigcup_{e\in\omega}C_{e}$. Hence by Theorem 1.19, there is
some pointed perfect tree $T$ and $e\in\omega$ such that $[T]\subseteq C_{e}$.

Define $f\colon\omega^{\omega}\to\omega^{\omega}$ by

$f(x)=\begin{cases}\Phi_{e}(x^{\prime})&\text{if }x\in[T]\\\
0&\text{else.}\end{cases}$

Let’s now make some observations about $f$.

  1. (1)

$f$ is clearly Borel—in fact, it is actually Baire class $1$.

  2. (2)

For every $x\in[T]$, $f(x)$ is a witness to the failure of the Posner-Robinson
theorem relative to $x$.

  3. (3)

In particular, for any $x\in[T]$, $f(x)\nleq_{T}x$. Since $[T]$ is a cofinal
set in the Turing degrees, $f$ satisfies the hypothesis of Lemma 3.1.

  4. (4)

For any $x\in\omega^{\omega}$, there is no $y$ such that $f(x)\oplus y\oplus
x\geq_{T}(y\oplus x)^{\prime}$. If $x\in[T]$ then this is because $f(x)$ is a
witness to the failure of the Posner-Robinson theorem relative to $x$. If
$x\notin[T]$ then this is because $f(x)$ is computable. Hence $f$ satisfies
the hypothesis of Lemma 3.2.

Thus by Lemmas 3.1 and 3.2, $f$ is a counterexample to Theorem 1.8. ∎

##  4\. Generalizations

Recently, Marks and Montalbán have generalized the Solecki dichotomy
(specifically, Theorem 1.6) to higher levels of the Borel hierarchy [7]. To
state their result, we must introduce a few more definitions. First, we must
generalize $\sigma$-continuity. Recall that for any countable ordinal
$\alpha$, a function $f$ is _$\mathbf{\Sigma}^{0}_{\alpha}$ -measurable_ if
for every open set $U$, $f^{-1}(U)$ is in $\mathbf{\Sigma}^{0}_{\alpha}$.

######  Definition 4.1.

For any countable ordinal $\alpha$,

  * •

$\mathsf{Dec}_{\alpha}$ denotes the set of functions
$f\colon\omega^{\omega}\to\omega^{\omega}$ for which there is a partition
$\\{A_{n}\\}_{n\in\omega}$ of $\omega^{\omega}$ into countably many pieces
such that for each $n$, $f\operatorname{\upharpoonright}_{A_{n}}$ is
$\mathbf{\Sigma}^{0}_{\alpha}$-measurable with respect to the subspace
topology on $A_{n}$.

  * •

$\mathsf{Dec}_{<\alpha}$ denotes the set of functions
$f\colon\omega^{\omega}\to\omega^{\omega}$ for which there is a partition
$\\{A_{n}\\}_{n\in\omega}$ of $\omega^{\omega}$ into countably many pieces
such that for each $n$, $f\operatorname{\upharpoonright}_{A_{n}}$ is
$\mathbf{\Sigma}^{0}_{\beta}$-measurable for some $\beta<\alpha$ (note that
$\beta$ may depend on $n$).

Note that $\mathbf{\Sigma^{0}_{1}}$-measurable is the same as continuous, so a
function $f$ is $\sigma$-continuous if and only if it is
$\mathsf{Dec}_{1}=\mathsf{Dec}_{<2}$.

As a warning to readers, the notation in this area is not yet standardized and
our notation does not quite match previously used notation. In particular,
$\mathsf{Dec}_{\alpha}$ is sometimes denoted
$\mathsf{Dec}(\mathbf{\Sigma}^{0}_{\alpha})$ (see e.g. [3]). We have chosen
the notation $\mathsf{Dec}_{\alpha}$ to be consistent with our chosen notation
for $\mathsf{Dec}_{<\alpha}$, for which there does not seem to currently be
any standard notation but which is necessary to correctly express Marks and
Montalbán’s generalization of the Solecki dichotomy at limit levels of the
Borel hierarchy.

For each countable ordinal $\alpha\geq 1$, we will use
$J_{\alpha}\colon\omega^{\omega}\to\omega^{\omega}$ to denote the
$\alpha^{\text{th}}$ Turing jump—i.e. $J_{\alpha}(x)=x^{(\alpha)}$. Note that
technically $J_{\alpha}$ depends on a choice of presentation for $\alpha$.
However, the versions of $J_{\alpha}$ that are obtained by choosing different
presentations for $\alpha$ are all reducible to each other (in the sense of
Definition 1.5) and so this subtlety does not matter for us.

We can now state the appropriate generalization of Theorem 1.6 due to Marks
and Montalbán.

######  Theorem 4.2 (Generalized Solecki dichotomy).

For every countable ordinal $\alpha\geq 1$ and every Borel function
$f\colon\omega^{\omega}\to\omega^{\omega}$, either $f$ is in
$\mathsf{Dec}_{<(1+\alpha)}$ or $J_{\alpha}\leq f$.

There is also a generalization of the Posner-Robinson theorem to higher levels
of the hyperarithmetic hierarchy, due to Slaman and Shore [14].

######  Theorem 4.3 (Generalized Posner-Robinson theorem).

For all computable ordinals $\alpha$ and all reals $x$, either
$x\leq_{T}0^{(\beta)}$ for some $\beta<\alpha$ or there is some real $y$ such
that $x\oplus y\geq_{T}y^{(\alpha)}$.

As usual, there is also a relativized version.

######  Theorem 4.4.

For all reals $z$, all ordinals $\alpha$ which are computable relative to $z$
and all reals $x$, either $x\leq_{T}z^{(\beta)}$ for some $\beta<\alpha$ or
there is some real $y$ such that $x\oplus y\oplus z\geq_{T}(y\oplus
z)^{(\alpha)}$.

The main results of this paper also hold for these generalizations of the
Solecki dichotomy and the Posner-Robinson theorem. In particular, we can
introduce weakened versions of Theorems 4.2 and 4.4:

######  Theorem 4.5.

For every countable ordinal $\alpha\geq 1$ and every Borel function
$f\colon\omega^{\omega}\to\omega^{\omega}$, either $f$ is in
$\mathsf{Dec}_{<(1+\alpha)}$ or $J_{\alpha}\leq_{w}f$.

######  Theorem 4.6.

For every countable ordinal $\alpha$, there is some cone of Turing degrees,
$C$, such that for all $z\in C$ and all reals $x$, $\alpha$ is computable
relative to $z$ and either $x\leq_{T}z^{(\beta)}$ for some $\beta<\alpha$ or
there is some real $y$ such that $x\oplus y\oplus z\geq_{T}(y\oplus
z)^{(\alpha)}$.

The proofs in sections 2 and 3 work, with almost no modifications, to show
that the two theorems above are equivalent.

## Acknowledgments

Thanks to Andrew Marks and Ted Slaman for useful conversations and advice.

## References

  * [1] Vasco Brattka and Guido Gherardi.  Weihrauch degrees, omniscience principles and weak computability.  The Journal of Symbolic Logic, 76(1):143–176, 2011.
  * [2] Raphaël Carroy.  A quasi-order on continuous functions.  The Journal of Symbolic Logic, 78(2):633–648, 2013.
  * [3] Vassilios Gregoriades, Takayuki Kihara, and Keng Meng Ng.  Turing degrees in Polish spaces and decomposability of Borel functions.  J. Math. Log., 21(1):Paper No. 2050021, 41, 2021.
  * [4] Carl G. Jockusch, Jr. and Richard A. Shore.  REA operators, r.e. degrees and minimal covers.  In Recursion theory (Ithaca, N.Y., 1982), volume 42 of Proc. Sympos. Pure Math., pages 3–11. Amer. Math. Soc., Providence, RI, 1985.
  * [5] Peter Koellner and W Hugh Woodin.  Large cardinals from determinacy.  In Handbook of set theory, pages 1951–2119. Springer, 2010.
  * [6] Patrick Lutz.  Results on Martin’s conjecture [thesis abstract].  Bull. Symb. Log., 27(2):219–220, 2021.
  * [7] Andrew Marks and Antonio Montalbán.  A dichotomy for $\sigma$-Baire class $\alpha$ functions.  Presentation at the Caltech logic colloquium, 2021.
  * [8] Donald A. Martin.  The axiom of determinateness and reduction principles in the analytical hierarchy.  Bull. Amer. Math. Soc., 74(4):687–689, 07 1968.
  * [9] Donald A. Martin.  A purely inductive proof of Borel determinacy.  In Recursion theory (Ithaca, N.Y., 1982), volume 42 of Proc. Sympos. Pure Math., pages 303–308. Amer. Math. Soc., Providence, RI, 1985.
  * [10] Donald A Martin.  Measurable cardinals and analytic games.  In Mathematical Logic In The 20th Century, pages 264–268. World Scientific, 2003.
  * [11] Luca Motto Ros.  On the structure of finite level and $\omega$-decomposable Borel functions.  J. Symbolic Logic, 78(4):1257–1287, 2013.
  * [12] Janusz Pawlikowski and Marcin Sabok.  Decomposing Borel functions and structure at finite levels of the Baire hierarchy.  Ann. Pure Appl. Logic, 163(12):1748–1764, 2012.
  * [13] David B. Posner and Robert W. Robinson.  Degrees joining to ${\bf 0}^{\prime}$.  J. Symbolic Logic, 46(4):714–722, 1981.
  * [14] Richard A. Shore and Theodore A. Slaman.  Defining the Turing jump.  Math. Res. Lett., 6(5-6):711–722, 1999.
  * [15] Theodore A. Slaman and John R. Steel.  Definable functions on degrees.  In Alexander S. Kechris, Donald A. Martin, and John R. Steel, editors, Cabal Seminar 81–85, pages 37–55, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg.
  * [16] Sławomir Solecki.  Decomposing Borel sets and functions and the structure of Baire class $1$ functions.  J. Amer. Math. Soc., 11(3):521–550, 1998.
  * [17] Jindřich Zapletal.  Descriptive set theory and definable forcing.  Mem. Amer. Math. Soc., 167(793):viii+141, 2004.


# Physics-based Scene Layout Generation from Human Motion

Jianan Li  0009-0009-5684-9381<EMAIL_ADDRESS>The Chinese University
of Hong KongHong KongChina Tencent Robotics XShenzhenChina ,  Tao Huang
0009-0006-7403-2760<EMAIL_ADDRESS>The Chinese University of Hong
KongHong KongChina ,  Qingxu Zhu  0009-0001-6549-3438<EMAIL_ADDRESS>Tencent Robotics XShenzhenChina and  Tien-Tsin Wong  0000-0002-7792-9307
<EMAIL_ADDRESS>The Chinese University of Hong KongHong KongChina

(2024)

###### Abstract.

Creating scenes for captured motions that achieve realistic human-scene
interaction is crucial for 3D animation in movies or video games. As character
motion is often captured in a blue-screened studio without real furniture or
objects in place, there may be a discrepancy between the planned motion and
the captured one. This gives rise to the need for automatic scene layout
generation to relieve the burdens of selecting and positioning furniture and
objects. Previous approaches cannot avoid artifacts like penetration and
floating due to the lack of physical constraints. Furthermore, some heavily
rely on specific data to learn the contact affordances, restricting the
generalization ability to different motions. In this work, we present a
physics-based approach that simultaneously optimizes a scene layout generator
and simulates a moving human in a physics simulator. To attain plausible and
realistic interaction motions, our method explicitly introduces physical
constraints. To automatically recover and generate the scene layout, we
minimize the motion tracking errors to identify the objects that can afford
interaction. We use reinforcement learning to perform a dual-optimization of
both the character motion imitation controller and the scene layout generator.
To facilitate the optimization, we reshape the tracking rewards and devise
pose prior guidance obtained from our estimated pseudo-contact labels. We
evaluate our method using motions from SAMP and PROX, and demonstrate
physically plausible scene layout reconstruction compared with the previous
kinematics-based method.

Scene layout generation, physics-based character control, reinforcement
learning

The work was done while Jianan Li was an intern at Tencent.

††submissionid: 1127††journalyear: 2024††copyright:
rightsretained††conference: Special Interest Group on Computer Graphics and
Interactive Techniques Conference Conference Papers ’24; July 27-August 1,
2024; Denver, CO, USA††booktitle: Special Interest Group on Computer Graphics
and Interactive Techniques Conference Conference Papers ’24 (SIGGRAPH
Conference Papers ’24), July 27-August 1, 2024, Denver, CO, USA††doi:
10.1145/3641519.3657517††isbn: 979-8-4007-0525-0/24/07††ccs: Computing
methodologies Animation††ccs: Computing methodologies Reinforcement learning
Figure 1. (a) Given a captured 3D human motion as the reference, (b) our
proposed framework optimizes the scene configuration to reproduce the physical
interactions in simulation, and then generates suitable affording objects, (c)
allowing physically plausible interaction for the animated character in the
scene.

##  1\. Introduction

Even with the advanced motion capture facilities, creating realistic animated
avatars that seamlessly interact with surrounding objects poses a significant
challenge for animators involved in film production and game development.
Typically, character motion is blue-screen captured in a studio without the
actual physical furniture or objects in place. Even if the virtual
furniture/objects have been planned ahead, there could be deviations during
the actual capture. In other words, an animator may still have to meticulously
choose a suitable piece of furniture (e.g. a chair), position it correctly,
and adjust the human motion to fit it. Hence, it would be convenient to
automate this tedious procedure of generating a plausible scene for a given
captured human motion thereby achieving natural human-scene interaction.

Several studies have explored the synthesis of scene layouts from human
motions. Nie et al. (2022) proposed a data-driven approach that learns a
probabilistic distribution of room layout conditioned by human skeleton pose
trajectory. However, this method can only output semantic bounding boxes of
the room layout without modeling the contact relationship between the human
and objects. To generate a visually compelling scene with a moving human,
mesh-based human models and post-optimization for object placement have been
used in (Yi et al., 2022; Ye et al., 2022; Yi et al., 2023). Ye et al. (2022)
presented a two-stage pipeline that initially estimates contact vertices on
human bodies and subsequently recovers the affording object by minimizing
contact and collision losses based on the object and the human meshes.
However, such soft constraints cannot ensure a physically correct interaction.
Physics violations, such as interpenetration and floating, may still occur,
particularly when the character comes into contact with the object. Moreover,
the reliance on learned contact semantics predictor might restrict its
applicability to specific types of motions, and the diversity of object
categories within the synthesized scene is also limited.

To obtain physically plausible interactions within the generated scene, we
propose to impose stricter physics constraints by simulating a virtual
character in a physics-based environment. In addition, to generate a
reasonable scene for arbitrary motions with any possible affording objects, we
propose to infer the contacting object based on the physical relations between
the human and the scene. The underlying intuition is that the human needs the
object to support the interaction in the real physical world. In this paper,
we focus on generating the interacting objects, which is the most critical
part of the scene that a human is interacting with. We present Simultaneously
Inferring the Interacting Objects and Learning Human-Scene Interaction Motions
(INFERACT), a physics-based optimization framework, that holistically
synthesizes the scene layout and imitates the motion within a physics
simulator. As illustrated in Fig. 2, our framework consists of two modules, a
motion imitator which learns a character controller to imitate the input
motion, and a scene layout generator that predicts suitable contacting objects
with their placements. We perform dual-optimization using reinforcement
learning and adopt the motion tracking reward as the objective for both sides.
Finding the optimal object placement is challenging due to the inefficient
random exploration strategy of the reinforcement learning agent. To mitigate
this issue, we first incorporate the contact constraint into the tracking
reward to encourage frequent interactions between the human and the object.
Then, we leverage the contact human poses as pose priors to further provide
stronger guidance for the object placement, by estimating contact frames using
an implicit function of contact frame values.

We evaluated the efficacy and effectiveness of the proposed method on motions
captured in the PROX, SAMP datasets, and other outdoor motions. Our
experiments demonstrate that the proposed method excels in generating
physically plausible scene layouts that align with the given motion.
Additionally, we show that our approach is capable of generating diverse scene
configurations and selecting appropriate objects for various motions. We
demonstrate the direct applicability of our approach to other interaction
motions, such as vaulting, without the need for additional supporting data. In
the ablation study, we rigorously verified the effectiveness of the character-
object contact constraint and the pose prior guidance.

Figure 2. Given a human motion sequence and an interacting object set, our
framework performs joint optimization for the two composed parts: a motion
imitation controller that controls the simulated character and a scene layout
generator that configures the objects in the simulation environment.

##  2\. Related Works

#### Human-Scene Interaction Synthesis

Research on human-scene interactions (HSI) seeks to precisely model the
relationship between a human character and the interacting object. One strand
of this research focuses on synthesizing plausible static human poses within a
given scene (Grabner et al., 2011; Gupta et al., 2011; Savva et al., 2016;
Hassan et al., 2019; Li et al., 2019). To enhance the realism of the generated
human figures, considerations are given to salient interactions such as
contact and proximity between the human and the scene. Zhang et al. (2020b)
proposed an HSI synthesis framework that explicitly incorporates human-scene
contacts into the pose generation procedure, yielding realistic interactions.
POSA (Hassan et al., 2021b) introduces a body-centric HSI representation that
encodes semantic contacts onto the mesh vertices of a parametric human body
model, SMPL-X (Pavlakos et al., 2019).

Another line of work focuses on modeling the dynamic process of human-scene
interactions for realistic animated interactions. Starke et al. (2019)
proposed a goal-conditioned motion synthesis model that achieves precise scene
interactions and motion control. Hassan et al. (2021a) presented a stochastic
model enabling the generation of diverse styles of sitting and lying motions.
COUCH (Zhang et al., 2022) employs a contact-conditioned variational
autoencoder, facilitating fine-grained control over the interaction motion
between the human and the chair. Canonical motions are highlighted in (Mir et
al., 2023), which enables the generation of continuous human-scene interaction
motions using scene-agnostic MoCap data. In recent works, diffusion models
have been applied to capture HSI patterns, offering enhanced motion quality
and flexible editing possibilities (Huang et al., 2023; Kulkarni et al., 2023;
Ye et al., 2023; Taheri et al., 2024). Physics-based methods are also employed
for human-scene interaction synthesis, achieving realistic and physically
plausible interactions (Hassan et al., 2023; Pan et al., 2023). In contrast to
these endeavors, our work focuses on the generation of plausible scene layouts
aligned with a given motion, resulting in life-like human-scene interactions.

#### Physics-based Motion Tracking

Physics-based motion imitation is extensively employed for learning and
reproducing human movements in physics-based environments through
reinforcement learning (Coros et al., 2009; Peng et al., 2016, 2021, 2022;
Wang et al., 2020). One straightforward approach to imitating a reference
motion is motion tracking, wherein the primary objective is to minimize the
pose error between the simulated character and a given reference (Sok et al.,
2007; Muico et al., 2011; Liu et al., 2010, 2016; Fussell et al., 2021).
Motion tracking has demonstrated its efficacy in acquiring fundamental motor
skills, even those involving highly dynamic movements (Peng et al., 2018;
Bergamin et al., 2019; Won et al., 2020; Lee et al., 2021). It also serves as
an effective method for learning primitive skills in hierarchical models
(Merel et al., 2020; Yao et al., 2022; Won et al., 2022; Zhu et al., 2023).
During the pre-training of latent hierarchical models, motion tracking rewards
function akin to the reconstruction loss in variational autoencoders. Beyond
its application in learning motion synthesis models, physics-based motion
imitation is applied as a post-processing step to ensure physical plausibility
(Shimada et al., 2020, 2021; Xie et al., 2021; Yuan et al., 2023). In our
approach, the utilization of the tracking-based character controller extends
beyond refining motion artifacts and ensuring physically correct scene
interactions. It also encompasses the generation of plausible scenes wherein
the simulated characters engage in meaningful physical interactions.

#### Human-guided Scene Layout Generation

Humans play a crucial role in guiding and facilitating the generation and
reconstruction of indoor scene layouts. For scene layout reconstruction, Chen
et al. (2019) leveraged the inherent connection between the estimations of
human poses and the bounding boxes of objects in a scene. They proposed
merging these two individual tasks to enhance the scene understanding from
videos. iMAPPER provides a pipeline based on motion retrieval that can produce
realistic object layouts for videos even with severe occlusion (Monszpart et
al., 2019). Weng and Yeung (2021) introduced a model that predicts mesh-level
estimations for both humans and the scene, followed by joint optimization to
refine the results. To achieve improved 3D scene layout reconstruction, Yi et
al. (2022) explicitly incorporated Human-Scene Interaction (HSI) constraints
into the optimization of object placement.

Concerning scene layout generation, Nie et al. (2022) introduced an end-to-end
generative model that takes human motion as inputs and predicts the bounding
boxes of furniture in a room. A recent work (Ye et al., 2022) achieved scene
synthesis with object meshes by proposing a framework SUMMON that recovers the
interacting object based on the contact semantics of the humans. MIME (Yi et
al., 2023) also leverages human contacts as conditional inputs of a
transformer-based model to predict a room layout represented by a sequence of
objects. To mitigate artifacts like penetration and floating, such kinematics-
based methods often need an additional refinement stage mostly to minimize
contact or collision losses, which might be insufficient to obtain physically
correct results. In contrast, our proposed approach recovers and generates
scene configurations within a physics-based environment to ensure physical
plausibility. In addition, the physics constraints are unitized to steer the
scene layout generation procedure in our devised dual-optimization framework,
where reinforcement learning is used to explore the optimal object placement
for interacting objects.

Figure 3. The motion imitation controller is trained to track the reference
motion within a physics simulator. The frame value network, guided by the
motion imitation controller, predicts the frame value for a given query pose
and contact condition. Pseudo contact labels are derived by identifying frames
with higher estimated contact frame values compared to non-contact frame
values. Subsequently, pose priors and the number of contacting objects can be
obtained through clustering of the contact human poses. The scene layout
generator policy takes the motion index and the number of objects as inputs
and predicts a mixed distribution of selected object indices and their
corresponding placements, with the guidance of pose priors.

##  3\. Method

Given a set of interacting objects and a motion sequence, we aim to generate
scene layouts with physically plausible object placement that aligns with
human actions. At a high level, our proposed framework formulates scene layout
generation as an optimization problem for maximizing the motion tracking score
in physics-based simulation. The optimization process comprises two key
components: learning a motion imitation controller to animate the simulated
character within a physics simulator and updating the scene layout generator
to provide the physical affordances for the interaction. This section is
structured as follows. Firstly, we introduce the problem formulation of scene-
character joint optimization in Section 3.1. Then, we present the details of
the motion imitation controller in Section 3.2. Lastly, we introduce the scene
layout generator with the character-object contact constraint and pose prior
guidance for efficient scene layout optimization in Section 3.3.

###  3.1. Scene-Character Joint Optimization

To generate a scene that satisfies the interaction and contact relationship
with the given moving human, we formulate the scene layout generation from
human motions as a maximization of the motion tracking score with physics
constraints. Given a human kinematics motion sequence with a length of $T$
timesteps $m=p_{1:T}$, a set of $N$ objects
$\mathcal{O}=\\{o_{i}\\}_{i=1}^{N}$, we denote the actual motion of the
simulated human character in a physics environment as $\hat{p}_{1:T}$ and
represent the generated scene with $L$ interacting objects using a subset of
given objects $\\{o_{i_{j}}\\}_{j=1:L}$ and their placements
$\\{q_{j}\\}_{j=1:L}$. Our objective is to generate an appropriate scene for
the given motion, in other words, finding an optimal selection of objects
$\\{o^{*}_{i_{j}}\\}_{j=1:L}$ associated with the optimal locations
$q^{*}(o^{*}_{i_{j}})_{j=1:L}$ that can support the animated character
perfectly reproducing the reference motion $m$ under the physics constraints.
To animate the simulated character within the physics simulator, we employ a
motion imitation controller that minimizes the discrepancy between
$\hat{p}_{1:T}$ and $p_{1:T}$. We thus propose a dual optimization framework
to jointly optimize the motion imitation controller and the scene layout
generator.

###  3.2. Motion Imitation Controller

To effectively reproduce the input kinematics motion on a physical human
character, we train a motion imitation controller to perform physics-based
motion tracking. Motion tracking in a physics environment can be formulated as
a Markov Decision Process (MDP) (Kaelbling et al., 1996), which can be solved
using reinforcement learning. We represent the character controller as a
$\pi_{C}(s_{t})$, which outputs control commands $a_{t}$ as actions based on
the observation of the current state $s_{t}$. The physics simulator calculates
the subsequent state $s_{t+1}$ based on the applied action and the environment
dynamics $p(s_{t+1}|s_{t},a_{t})$. Additionally, it provides a reward $r_{t}$
to the character controller. By repeating these steps, a trajectory of
observed states $\tau=\\{s_{0},s_{1},…,s_{T-1}\\}$ is collected by the policy.
The policy is then updated to maximize the cumulative discounted rewards
$R=\sum_{t=0}^{T-1}\gamma^{t}r_{t}$.

#### State and Action Representation

In physics-based motion tracking, we represent the state observation of the
policy with three components $s_{t}=[s_{t}^{H},s_{t}^{E},s_{t}^{R}]$, where
$s_{t}^{H}\in\mathbb{R}^{125}$ is a local proprioceptive observation of the
human character’s pose, $s_{t}^{E}\in\mathbb{Z^{+}}\times\mathbb{R}^{3}$
represents the state of a scene layout and $s_{t}^{R}\in R^{127}$ denotes the
relative tracking feature of the reference motion. More specifically, the
scene layout state consisting of $L$ objects is a sequence of object indices
$i_{j}\in\mathbb{Z}^{+}$ and their placements $q_{i_{j}}\in\mathbb{R}^{3}$ for
each object $j$. The details of computation for each state component can be
referred to in the appendix. We use a commonly used humanoid character (Peng
et al., 2022) with 12 active joints and a total of 28 degrees of freedom
(DoFs). To control the character in the simulation, we calculate the driving
torques for each DoF using a PD controller, whose input target joint position
is defined as the action $a_{t}\in\mathbb{R}^{28}$.

#### Rewards

We adopt a similar reward function presented in (Peng et al., 2018) as the
motion tracking reward, which is given by

(1)
$r_{t}=w^{p}r^{p}_{t}+w^{o}r^{o}_{t}+w^{v}r^{v}_{t}+w^{jp}r^{jp}_{t}+w^{jv}r^{jv}_{t}+w^{k}r^{k}_{t},$

where $r^{p}_{t}$, $r^{o}_{t}$, $r^{v}_{t}$ are the character’s root position,
root orientation, and root velocity, and $r^{jp}_{t}$, $r^{jv}_{t}$,
$r^{k}_{t}$ denote the joint positions, joint velocities, and positions of key
bodies on the character respectively.

###  3.3. Scene Layout Generator

To populate plausible scenes for the simulated character to interact, we
optimize a scene layout generator simultaneously while learning the motion
imitation controller. We represent the scene layout generator with a
stochastic policy that outputs a joint distribution of discrete object indices
and continuous object placements. The input to the scene layout generator can
be either a complete motion sequence or other hand-crafted features that
represent the reference motion. For simplicity, we use a motion index
$I(m)\in\mathbb{Z^{+}}$ as a dummy input in our implementation. For a given
motion index $I(m)$, the scene layout generator predicts the selection and the
placement of the $j$-th object in contact with the human character as
$(i_{j},q_{i_{j}})\sim\pi_{S}(I(m),j)$, where index $i_{j}$ indicates the
object selection from the object set $\mathcal{O}$.

To train the scene layout generator, we use reinforcement learning to maximize
the accumulated motion tracking rewards, similar to the learning of the motion
imitation controller. However, tracking rewards cannot provide dense feedback
to the reinforcement learning agent, especially when the simulated character
does not have actual physical interaction with the object.

To facilitate learning, we incorporate guidance at different levels into
reward functions to provide effective feedback to the scene layout generator.
Firstly, we integrate a contact constraint into the motion tracking rewards,
ensuring a close spatial relationship between the character and the
interacting object. Secondly, we introduce direct guidance for object
placement by utilizing pose priors derived from the contact human poses,
estimated through an unsupervised contact frame value estimator.

#### Character-object Contacting Constraint

To promote increased interaction between the character and the scene, we
modify the reward structure for the scene layout generator by introducing a
binary multiplier to the original motion tracking reward. More specifically,
we provide rewards to the scene generator only when the simulated human makes
contact with the objects in the generated scene. The reshaped reward is
represented by the equation:

(2) $R_{\rm
track}=\mathds{1}(\sum_{t=1}^{T}c_{t}>0)\sum_{t=1}^{T}\gamma^{t}r_{t},$

where $c_{t}\in\\{0,1\\}$ denotes the contact state between the human and the
object at the time step $t$ and $\mathds{1}(\sum_{t=1}^{T}c_{t}>0)=1$ if the
internal statement is true, otherwise takes zero. With this reward shaping,
the original motion tracking task is reformulated to a constrained tracking
score maximization, where the primary requirement is to ensure the scene-
character contact.

#### Pseudo Contact Labels

The introduced character-object contacting constraint serves as a coarse prior
regarding the spatial distribution of the human’s location. To obtain a more
precise object location from the motion, we can leverage frame-wise contact
information that provides insights into the position of the interacting human.
In contrast to previous approaches that rely on a trained contact estimation
model (Ye et al., 2022; Yi et al., 2023), we propose an unsupervised method to
infer the contact pose based on the character’s tracking performance. We
specifically train an implicit contact frame value function, denoted as
$V(p_{t},c_{t})\in\mathbb{R}$, to predict the expected tracking performance
when provided with given human pose query $p_{t}$ and contact query $c_{t}$.
To train the implicit contact frame value function, we utilize the estimated
tracking performance value from the critic network (Schulman et al., 2017) to
provide supervision signals. The training objective for the frame value
network is presented as follows:

(3) $\mathcal{L}_{\rm
frameval}=\|V_{\phi}(p_{t},c_{t})-r_{t}-\gamma\hat{V}(s_{t+1})\|_{2}^{2},$

where $V_{\phi}(p_{t},c_{t})$ represents the frame value network, $r_{t}$
denotes the tracking reward, and $\hat{V}(s_{t+1})$ indicates the estimated
value for successive state $s_{t+1}$, obtained from the critic network of the
motion imitation controller.

We utilize the frame value network to infer pseudo contact labels for the
given motion sequence. As illustrated in Fig. 3, by providing the pose and
contact queries as inputs to the frame value network, we obtain two curves
representing estimated frame values with and without contact. Subsequently,
pseudo contact labels $\hat{c}_{t}$ can be computed by comparing the predicted
contact frame values using the following equation:

(4)
$\hat{c}_{t}=\mathds{1}\big{(}V_{\phi}(p_{t},1)-V_{\phi}(p_{t},0)>0\big{)}.$

#### Contact Pose Priors

With the estimated pseudo contact labels, we can incorporate stronger guidance
for object placement by leveraging contact pose priors, to enhance the
learning efficiency of the scene layout generator. The pose prior is
represented by the pelvis pose of the contact humans (Ye et al., 2022), which
can provide a rough indication of the object’s location during the
interaction. Besides, incorporating pose priors can enhance the quality of the
solution in cases where the motion tracking objective alone may not be
sufficient to achieve realistic outcomes.

To derive pose priors, we perform clustering on the pelvis poses of the
contact humans identified through the estimated pseudo contact labels. The
pose priors are represented as cluster centers, denoted as
$\bar{q_{r}}=(t_{x},t_{y},r_{\text{yaw}})$, which consists of planar
translations and a vertical rotation angle. Moreover, the number of clusters
can be used as an indication of the number of interacting objects present in
the scene. We combine the reshaped tracking reward in Eq. 2 with the pose
prior guidance to obtain the final reward function for the scene layout
generator, which is shown as below:

(5) $R=R_{\text{track}}+\alpha\|q-\bar{q_{r}}\|_{2}^{2},$

where the weight $\alpha$ controls the strength of the pose prior guidance.

Figure 4. Illustrations of our generated scenes for three different motions,
with the object placements obtained by SUMMON (Ye et al., 2022) for
comparison. Our method generates reasonable and plausible scenes compared with
SUMMON. Figure 5. Qualitative comparison with MIME (Yi et al., 2023). The
results exclusively focus on the contacting objects within the scene. Our
method demonstrates enhanced physical plausibility in object placements, while
MIME occasionally encounters difficulties in generating scenes with
satisfactory human-scene interaction, even after employing scene refinement.
Figure 6. Visualizations of diverse object selections generated by our method
for a sitting motion. The selection probability of each chosen object is
indicated above the figures. This example demonstrates the capability of
INFERACT to generate diverse results for chair choices (sub-figure 1 to 3) and
its ability to screen out inappropriate objects like tables (rightmost).
Figure 7. Illustrations of best selections for various motions. INFERACT can
select the suitable affording object for different motions. Motions from left
to right are sitting on a chair, sitting on a high stool, sitting on a
footstool, and lying on a bed.

##  4\. Experiments

###  4.1. Experiment Setup

We evaluate our approach using indoor motions from SAMP (Hassan et al., 2021a)
and PROX (Hassan et al., 2019), as well as outdoor vaulting motion capture
data. Meanwhile, we prepare an object set consisting of 32 different furniture
items from the 3D-Future dataset (Fu et al., 2021), categorized into chairs,
sofas, tables, and beds. Furthermore, we test other 3D shapes such as
fountains and rocks to evaluate the ability of our method to generate
reasonable placements, even when explicit affordances for interaction may not
be present.

###  4.2. Implementation Details

The motion imitation controller $\pi$ is represented by a neural network with
three fully connected layers of units [512, 256, 64]. The output of the policy
$\pi$ is a Gaussian distribution $\pi(s_{t})=\mathcal{N}(\mu(s_{t}),\Sigma)$,
where the mean $\mu(s_{t})$ is predicted by the neural network, and the
variance $\Sigma$ is a constant diagonal matrix defined manually. To handle
the scene layout state inputs $s_{t}^{E}$, which consists of an index input
$i_{j}$ and a placement input $q_{i_{j}}$ for each object in the scene, we
project $s_{t}^{E}$ into 128D vectors using an embedding layer and a linear
layer. Similarly, the scene layout generator is also represented by a neural
network. It consists of two fully connected neural networks with sizes [64,
16]. The first network takes inputs of the motion index $I(m_{i})$ and the
object order $j$, and then outputs a categorical distribution that represents
the selection probability for each object in the set $\mathcal{O}$. Once an
object is chosen, the second neural network predicts the corresponding
placement. The frame value network $V{\phi}(p_{t},c_{t})$ is modeled using
fully connected layers of [256, 128, 64]. The input pose query $p_{t}$ is a
feature of a canonical pose from the reference motion, where the pelvis
translation is set to zero to remove global information.

The optimization of the whole proposed framework is based on reinforcement
learning. We create a training environment in a GPU-based parallel simulator
IsaacGym (Makoviychuk et al., 2021). The contacts between the character and
objects are detected using the force sensor integrated into the simulator. To
accelerate the learning process of the motion imitation controller, we adopt a
reference-based initialization strategy recommended in (Peng et al., 2018).
This strategy initializes the character at the start of each episode with a
randomly chosen human pose from the reference motion. The location of the
objects is updated every 512 simulation steps based on predictions made by the
scene layout generator. The frame value network is updated every 32 updates
for the motion imitator networks. The gradients for the motion imitation
controller and the scene layout generator are calculated using the PPO
algorithm (Schulman et al., 2017).

Figure 8. Illustration of the generated scene for the vaulting motion. INFERACT can be applied to a wide range of motions. Table 1. Tracking scores and success rates on the SAMP dataset. Our method outperforms others. Method | tracking score | success rate
---|---|---
SUMMON | - |  0.53
SUMMON in physics | 0.61 |  0.68
Ours w/ POSA | 0.67 |  0.84
Ours | 0.67 |  0.84

###  4.3. Generated Scene Layouts

#### Comparison

We quantitatively compare the physical plausibility of our results with those
from the state-of-the-art human mesh-based scene synthesis approach SUMMON (Ye
et al., 2022) and its variant SUMMON in physics, which combines SUMMON
synthesized scenes with a physics-based motion imitation controller. We define
two metrics to assess the physical plausibility of the generated scenes for
physics-based approaches: the tracking score and the success rate. The
tracking score is computed using the tracking reward formulated in Eq. 1. To
determine a successful trial, we consider a maximum tracking error of the key
body parts (hands, feet, head, pelvis) that is less than 0.3m. We also extend
the definition of success rate to include the kinematics-based approach
SUMMON. For this approach, a trial is considered successful if there is no
significant penetration, which is determined by the non-collision score (Zhang
et al., 2020a) being less than 0.85.

The visualizations of the generated results for comparison are illustrated in
Fig. 4. According to the figure, our approach successfully generates
physically plausible scenes for three different settings: a human interacting
with multiple objects, a human performing complicated chair motions, and a
human interacting with an object without obvious interaction affordances. In
contrast, the compared method SUMMON exhibits artifacts such as severe
penetration or floating on the interacting object. Furthermore, we include
another strong baseline, MIME (Yi et al., 2023), in our qualitative comparison
for scene layout generation. Similar to SUMMON, MIME also exhibits limitations
in creating physically plausible scenes for human interaction, as shown in
Fig. 5. The comparison clearly demonstrates the strength of our method in
producing physically plausible scenes with animated humans.

#### Diversity

The diversity of the selected objects is demonstrated in Fig. 6. As shown in
the visualization results, the scene layout generator is capable of generating
a scene distribution. The chair in the left figure is the most suitable for
this motion and is therefore picked with the highest chance of 0.82. The
selection probability decreases if the heights of the chairs do not match, as
shown in the second and third examples. If the object does not have a proper
affordance to support the human, like the table illustrated in the rightmost
example, it has nearly zero probability of being selected. These results
demonstrate the ability of our method to generate diverse object selections
with plausible placements for the motion.

#### Object selection

We further investigate whether our method can select appropriate interacting
objects by varying the human motion. In this experiment, we utilize motions
from SAMP in different sitting heights. From the visualizations depicted in
Fig. 7, where each example showcases the most probable selection, our method
successfully chooses the suitable object for different motions.

#### Generalize to outdoor motions

In this experiment, we test our method on outdoor motions, which presents
extreme challenges for methods that rely on pre-trained contact estimators
using indoor activity motions. In Fig. 8, the scene layout generator is still
capable of generating a reasonable scene with a table serving as the obstacle
that supports the human in completing the vaulting motion. This demonstrates
the potential versatility of our method in handling various types of
interactions.

Figure 9. Results of ablation studies. The top figure depicts the learning
curves of our method and ablated ones. The bottom figures illustrate the
comparison between two generated scenes from ablated methods.

###  4.4. Ablation Study

#### Reward guidance

Firstly, we examine the significance of the reward guidance, which includes
the character-object contact constraint and the pose prior guidance, on the
learning efficiency of the scene layout generator. To assess the learning
efficiency, We use the learning curve as a proxy to reveal the motion tracking
score with respect to the update iteration. As shown in Fig. 9, we can observe
a significant improvement in the methods that incorporate scene-character
contact constraints compared to plain RL optimization without the scene-
character contact constraint and the pose prior guidance. Regarding the pose
prior guidance, the method with this feature experiences further improvement
in its learning procedure and achieves a higher tracking score after the
convergence point. During the experiments, we also observe additional benefits
of employing the pose prior guidance. In some cases, the agent “hacks” the
motion tracking task by learning a cheating object placement. As shown in Fig.
9, the character learns to lean against the armrest of the chair instead of
sitting on the chair. With the pose prior guidance, our method effectively
mitigates this issue and generates more reasonable results.

#### Pseudo contact labels

We further investigate the efficacy of our proposed pseudo contact label
estimation method by replacing it with ground truth contacts, in providing
pose prior guidance. This modified approach, referred to as ours with POSA,
utilizes the pre-trained POSA model to predict the contact frames. As the
results presented in Table. 1, our method maintains comparable performance
even without prior knowledge of motion contacts. Moreover, our method can be
directly applied to novel motions without the need for training the contact
estimator. We also visualize the estimated contact values for a sitting motion
in Fig. 10, where the estimated pseudo contact labels, indicated by the blue
shaded area, are approximately consistent with the motion semantics.

Figure 10. Visualizations of contact frame values and pseudo contact labels.
The top figure presents skeleton pose snapshots, while the bottom plot
displays the estimated contact frame values from the frame value networks
after 500 updates. The shadow areas represent the pseudo contact labels. The
visualization demonstrates the frame value network’s ability to predict
approximate correct contacts at an early stage of training.

##  5\. Conclusion

We presented a method INFERACT that generates plausible scene layouts
supporting realistic human-scene interaction in a physics-based environment.
Our method introduces physical constraints and motion dynamics as constraints
and optimizes both scene configurations and the simulated character controller
to maximize the motion tracking objective using reinforcement learning. The
generated scenes for the motions from SAMP and PROX show enhanced physical
plausibility compared with the state-of-the-art human mesh-based scene
synthesis method. The results of INFERACT also demonstrate the ability to
generate versatile scenes for a single motion and select the most matching
objects for different motions.

#### Limitations and future work.

INFERACT still has certain limitations. One notable limitation is that it
approximates all physical interactions using rigid body contact. However, this
approach may not accurately capture the complex dynamics of human-scene
interaction in the real world. Consequently, visual artifacts, such as motion
jitters during contact, may still exist. Another limitation arises from the
restricted range of supported interaction relationships. To expand the scope
of human-scene interactions, a potential future direction is to explore a more
comprehensive optimization objective that encompasses a wider range of
interaction categories.

###### Acknowledgements.

We thank Lei Han and He Zhang for their insightful and stimulating discussion
on the concept. This work was supported by Tencent and Hong Kong Innovation
and Technology Commission (ITS/307/20FP).

## References

  * (1)
  * Bergamin et al. (2019) Kevin Bergamin, Simon Clavet, Daniel Holden, and James Richard Forbes. 2019.  DReCon: data-driven responsive control of physics-based characters.  _ACM Transactions On Graphics (TOG)_ 38, 6 (2019), 1–11.
  * Chen et al. (2019) Yixin Chen, Siyuan Huang, Tao Yuan, Siyuan Qi, Yixin Zhu, and Song-Chun Zhu. 2019.  Holistic++ scene understanding: Single-view 3d holistic scene parsing and human pose estimation with human-object interaction and physical commonsense. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 8648–8657.
  * Coros et al. (2009) Stelian Coros, Philippe Beaudoin, and Michiel Van de Panne. 2009.  Robust task-based control policies for physics-based characters.  In _ACM SIGGRAPH Asia 2009 papers_. 1–9.
  * Fu et al. (2021) Huan Fu, Rongfei Jia, Lin Gao, Mingming Gong, Binqiang Zhao, Steve Maybank, and Dacheng Tao. 2021.  3d-future: 3d furniture shape with texture.  _International Journal of Computer Vision_ (2021), 1–25.
  * Fussell et al. (2021) Levi Fussell, Kevin Bergamin, and Daniel Holden. 2021.  Supertrack: Motion tracking for physically simulated characters using supervised learning.  _ACM Transactions on Graphics (TOG)_ 40, 6 (2021), 1–13.
  * Grabner et al. (2011) Helmut Grabner, Juergen Gall, and Luc Van Gool. 2011.  What makes a chair a chair?. In _CVPR 2011_. IEEE, 1529–1536.
  * Gupta et al. (2011) Abhinav Gupta, Scott Satkin, Alexei A Efros, and Martial Hebert. 2011.  From 3d scene geometry to human workspace. In _CVPR 2011_. IEEE, 1961–1968.
  * Hassan et al. (2021a) Mohamed Hassan, Duygu Ceylan, Ruben Villegas, Jun Saito, Jimei Yang, Yi Zhou, and Michael J Black. 2021a.  Stochastic scene-aware motion prediction. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 11374–11384.
  * Hassan et al. (2019) Mohamed Hassan, Vasileios Choutas, Dimitrios Tzionas, and Michael J Black. 2019.  Resolving 3D human pose ambiguities with 3D scene constraints. In _Proceedings of the IEEE/CVF international conference on computer vision_. 2282–2292.
  * Hassan et al. (2021b) Mohamed Hassan, Partha Ghosh, Joachim Tesch, Dimitrios Tzionas, and Michael J Black. 2021b.  Populating 3D scenes by learning human-scene interaction. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 14708–14718.
  * Hassan et al. (2023) Mohamed Hassan, Yunrong Guo, Tingwu Wang, Michael Black, Sanja Fidler, and Xue Bin Peng. 2023.  Synthesizing Physical Character-Scene Interactions. In _ACM SIGGRAPH 2023 Conference Proceedings_ (Los Angeles, CA, USA) _(SIGGRAPH ’23)_. Association for Computing Machinery, New York, NY, USA, Article 63, 9 pages.  https://doi.org/10.1145/3588432.3591525
  * Huang et al. (2023) Siyuan Huang, Zan Wang, Puhao Li, Baoxiong Jia, Tengyu Liu, Yixin Zhu, Wei Liang, and Song-Chun Zhu. 2023.  Diffusion-based generation, optimization, and planning in 3d scenes. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 16750–16761.
  * Kaelbling et al. (1996) Leslie Pack Kaelbling, Michael L Littman, and Andrew W Moore. 1996.  Reinforcement learning: A survey.  _Journal of artificial intelligence research_ 4 (1996), 237–285.
  * Kulkarni et al. (2023) Nilesh Kulkarni, Davis Rempe, Kyle Genova, Abhijit Kundu, Justin Johnson, David Fouhey, and Leonidas Guibas. 2023.  Nifty: Neural object interaction fields for guided human motion synthesis.  _arXiv preprint arXiv:2307.07511_ (2023).
  * Lee et al. (2021) Seyoung Lee, Sunmin Lee, Yongwoo Lee, and Jehee Lee. 2021.  Learning a family of motor skills from a single motion clip.  _ACM Transactions on Graphics (TOG)_ 40, 4 (2021), 1–13.
  * Li et al. (2019) Xueting Li, Sifei Liu, Kihwan Kim, Xiaolong Wang, Ming-Hsuan Yang, and Jan Kautz. 2019.  Putting humans in a scene: Learning affordance in 3d indoor environments. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 12368–12376.
  * Liu et al. (2016) Libin Liu, Michiel Van De Panne, and KangKang Yin. 2016.  Guided learning of control graphs for physics-based characters.  _ACM Transactions on Graphics (TOG)_ 35, 3 (2016), 1–14.
  * Liu et al. (2010) Libin Liu, KangKang Yin, Michiel Van de Panne, Tianjia Shao, and Weiwei Xu. 2010.  Sampling-based contact-rich motion control.  In _ACM SIGGRAPH 2010 papers_. 1–10.
  * Makoviychuk et al. (2021) Viktor Makoviychuk, Lukasz Wawrzyniak, Yunrong Guo, Michelle Lu, Kier Storey, Miles Macklin, David Hoeller, Nikita Rudin, Arthur Allshire, Ankur Handa, et al. 2021\.  Isaac gym: High performance gpu-based physics simulation for robot learning.  _arXiv preprint arXiv:2108.10470_ (2021).
  * Merel et al. (2020) Josh Merel, Saran Tunyasuvunakool, Arun Ahuja, Yuval Tassa, Leonard Hasenclever, Vu Pham, Tom Erez, Greg Wayne, and Nicolas Heess. 2020.  Catch & carry: reusable neural controllers for vision-guided whole-body tasks.  _ACM Transactions on Graphics (TOG)_ 39, 4 (2020), 39–1.
  * Mir et al. (2023) Aymen Mir, Xavier Puig, Angjoo Kanazawa, and Gerard Pons-Moll. 2023.  Generating continual human motion in diverse 3d scenes.  _arXiv preprint arXiv:2304.02061_ (2023).
  * Monszpart et al. (2019) Aron Monszpart, Paul Guerrero, Duygu Ceylan, Ersin Yumer, and Niloy J Mitra. 2019.  iMapper: interaction-guided scene mapping from monocular videos.  _ACM Transactions On Graphics (TOG)_ 38, 4 (2019), 1–15.
  * Muico et al. (2011) Uldarico Muico, Jovan Popović, and Zoran Popović. 2011.  Composite control of physically simulated characters.  _ACM Transactions on Graphics (TOG)_ 30, 3 (2011), 1–11.
  * Nie et al. (2022) Yinyu Nie, Angela Dai, Xiaoguang Han, and Matthias Nießner. 2022.  Pose2room: understanding 3d scenes from human activities. In _European Conference on Computer Vision_. Springer, 425–443.
  * Pan et al. (2023) Liang Pan, Jingbo Wang, Buzhen Huang, Junyu Zhang, Haofan Wang, Xu Tang, and Yangang Wang. 2023.  Synthesizing physically plausible human motions in 3d scenes.  _arXiv preprint arXiv:2308.09036_ (2023).
  * Pavlakos et al. (2019) Georgios Pavlakos, Vasileios Choutas, Nima Ghorbani, Timo Bolkart, Ahmed A. A. Osman, Dimitrios Tzionas, and Michael J. Black. 2019.  Expressive Body Capture: 3D Hands, Face, and Body from a Single Image. In _Proceedings IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_. 10975–10985.
  * Peng et al. (2018) Xue Bin Peng, Pieter Abbeel, Sergey Levine, and Michiel Van de Panne. 2018.  Deepmimic: Example-guided deep reinforcement learning of physics-based character skills.  _ACM Transactions On Graphics (TOG)_ 37, 4 (2018), 1–14.
  * Peng et al. (2016) Xue Bin Peng, Glen Berseth, and Michiel Van de Panne. 2016.  Terrain-adaptive locomotion skills using deep reinforcement learning.  _ACM Transactions on Graphics (TOG)_ 35, 4 (2016), 1–12.
  * Peng et al. (2022) Xue Bin Peng, Yunrong Guo, Lina Halper, Sergey Levine, and Sanja Fidler. 2022.  Ase: Large-scale reusable adversarial skill embeddings for physically simulated characters.  _ACM Transactions On Graphics (TOG)_ 41, 4 (2022), 1–17.
  * Peng et al. (2021) Xue Bin Peng, Ze Ma, Pieter Abbeel, Sergey Levine, and Angjoo Kanazawa. 2021.  Amp: Adversarial motion priors for stylized physics-based character control.  _ACM Transactions on Graphics (ToG)_ 40, 4 (2021), 1–20.
  * Savva et al. (2016) Manolis Savva, Angel X Chang, Pat Hanrahan, Matthew Fisher, and Matthias Nießner. 2016.  Pigraphs: learning interaction snapshots from observations.  _ACM Transactions on Graphics (TOG)_ 35, 4 (2016), 1–12.
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ (2017).
  * Shimada et al. (2021) Soshi Shimada, Vladislav Golyanik, Weipeng Xu, Patrick Pérez, and Christian Theobalt. 2021.  Neural monocular 3d human motion capture with physical awareness.  _ACM Transactions on Graphics (ToG)_ 40, 4 (2021), 1–15.
  * Shimada et al. (2020) Soshi Shimada, Vladislav Golyanik, Weipeng Xu, and Christian Theobalt. 2020.  Physcap: Physically plausible monocular 3d motion capture in real time.  _ACM Transactions on Graphics (ToG)_ 39, 6 (2020), 1–16.
  * Sok et al. (2007) Kwang Won Sok, Manmyung Kim, and Jehee Lee. 2007.  Simulating biped behaviors from human motion data.  In _ACM SIGGRAPH 2007 papers_. 107–es.
  * Starke et al. (2019) Sebastian Starke, He Zhang, Taku Komura, and Jun Saito. 2019.  Neural state machine for character-scene interactions.  _ACM Trans. Graph._ 38, 6 (2019), 209–1.
  * Taheri et al. (2024) Omid Taheri, Yi Zhou, Dimitrios Tzionas, Yang Zhou, Duygu Ceylan, Soren Pirk, and Michael J Black. 2024.  GRIP: Generating interaction poses using spatial cues and latent consistency. In _International conference on 3D vision (3DV)_.
  * Wang et al. (2020) Tingwu Wang, Yunrong Guo, Maria Shugrina, and Sanja Fidler. 2020.  Unicon: Universal neural controller for physics-based character motion.  _arXiv preprint arXiv:2011.15119_ (2020).
  * Weng and Yeung (2021) Zhenzhen Weng and Serena Yeung. 2021.  Holistic 3d human and scene mesh estimation from single view images. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 334–343.
  * Won et al. (2020) Jungdam Won, Deepak Gopinath, and Jessica Hodgins. 2020.  A scalable approach to control diverse behaviors for physically simulated characters.  _ACM Transactions on Graphics (TOG)_ 39, 4 (2020), 33–1.
  * Won et al. (2022) Jungdam Won, Deepak Gopinath, and Jessica Hodgins. 2022.  Physics-based character controllers using conditional vaes.  _ACM Transactions on Graphics (TOG)_ 41, 4 (2022), 1–12.
  * Xie et al. (2021) Kevin Xie, Tingwu Wang, Umar Iqbal, Yunrong Guo, Sanja Fidler, and Florian Shkurti. 2021.  Physics-based human motion estimation and synthesis from videos. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 11532–11541.
  * Yao et al. (2022) Heyuan Yao, Zhenhua Song, Baoquan Chen, and Libin Liu. 2022.  ControlVAE: Model-Based Learning of Generative Controllers for Physics-Based Characters.  _ACM Transactions on Graphics (TOG)_ 41, 6 (2022), 1–16.
  * Ye et al. (2022) Sifan Ye, Yixing Wang, Jiaman Li, Dennis Park, C Karen Liu, Huazhe Xu, and Jiajun Wu. 2022.  Scene synthesis from human motion. In _SIGGRAPH Asia 2022 Conference Papers_. 1–9.
  * Ye et al. (2023) Yufei Ye, Poorvi Hebbar, Abhinav Gupta, and Shubham Tulsiani. 2023.  Diffusion-Guided Reconstruction of Everyday Hand-Object Interaction Clips. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 19717–19728.
  * Yi et al. (2023) Hongwei Yi, Chun-Hao P Huang, Shashank Tripathi, Lea Hering, Justus Thies, and Michael J Black. 2023.  MIME: Human-Aware 3D Scene Generation. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 12965–12976.
  * Yi et al. (2022) Hongwei Yi, Chun-Hao P Huang, Dimitrios Tzionas, Muhammed Kocabas, Mohamed Hassan, Siyu Tang, Justus Thies, and Michael J Black. 2022.  Human-aware object placement for visual environment reconstruction. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 3959–3970.
  * Yuan et al. (2023) Ye Yuan, Jiaming Song, Umar Iqbal, Arash Vahdat, and Jan Kautz. 2023.  Physdiff: Physics-guided human motion diffusion model. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 16010–16021.
  * Zhang et al. (2020b) Siwei Zhang, Yan Zhang, Qianli Ma, Michael J Black, and Siyu Tang. 2020b.  PLACE: Proximity learning of articulation and contact in 3D environments. In _2020 International Conference on 3D Vision (3DV)_. IEEE, 642–651.
  * Zhang et al. (2022) Xiaohan Zhang, Bharat Lal Bhatnagar, Sebastian Starke, Vladimir Guzov, and Gerard Pons-Moll. 2022.  Couch: Towards controllable human-chair interactions. In _European Conference on Computer Vision_. Springer, 518–535.
  * Zhang et al. (2020a) Yan Zhang, Mohamed Hassan, Heiko Neumann, Michael J Black, and Siyu Tang. 2020a.  Generating 3d people in scenes without people. In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_. 6194–6204.
  * Zhu et al. (2023) Qingxu Zhu, He Zhang, Mengting Lan, and Lei Han. 2023.  Neural Categorical Priors for Physics-Based Character Control.  _ACM Transactions on Graphics (TOG)_ 42, 6 (2023), 1–16.

##  Appendix A Details of State Representation

The local proprioceptive observation $s^{H}_{t}$ includes various features
that describe the states of the animated humanoid character. These features
include the height and orientation of the root, the velocity of the root, the
angular velocity of the root, joint rotations represented using 6D normal-
tangent vectors, joint velocities, and the relative positions of key body
parts (such as hands and feet) with respect to the root, referred as to
keypos. All of these features are calculated in the local coordinate system of
the humanoid root. The scene layout state $s^{E}_{t}$ incorporates two
components. Firstly, it includes an index indicating the selected object from
the object set $O$. Secondly, it includes a 3D vector that indicates the
placement of the object. This vector consists of the global translations on
the $X-Y$ plane and the rotation angle in the $Z$ axis. The relative tracking
feature $s^{R}_{t}$ consists of the features of the reference human pose. It
includes the local root position, orientation, and linear and angular
velocities of the reference pose in the coordinate of the animated human root.
Additionally, it includes joint rotations and velocities, and keypos of the
reference human pose.

##  Appendix B Computation of Tracking Rewards

The tracking reward for the character’s root position, root orientation, and
root velocity are calculated as follows:

$r^{p}_{t}=\exp{(-10\cdot\|p_{t}-\hat{p_{t}}\|)},$
$r^{o}_{t}=\exp{(-5\cdot\|o_{t}-\hat{o_{t}}\|)},$
$r^{v}_{t}=\exp{(-1\cdot\|\dot{p}_{t}-\hat{\dot{p}}_{t}\|)},$

where $p,o,\dot{p}$ denotes the root position, root orientation, and root
velocity of the character, and $\hat{\cdot}$ denotes the desired value. The
reward terms for the joint positions and velocities are formulated to:

$r^{jp}_{t}=\exp{\Big{(}-2\cdot\sum_{j=1}^{N}(q^{j}_{t}-\hat{q^{j}_{t}})^{2}\Big{)}}$
$r^{jv}_{t}=\exp{\Big{(}-0.1\cdot\sum_{j=1}^{N}(\dot{q}^{j}_{t}-\hat{\dot{q}}^{j}_{t})^{2}\Big{)}},$

where $q^{j}$ and $\dot{q}^{j}$ represent the joint position and velocity for
each DoF, and $N$ is the number of DoFs in the humanoid character. The reward
for key body positions is

$r^{k}_{t}=\exp{\Big{(}-10\cdot\frac{1}{K}\sum_{k=1}^{K}\|p^{k}_{t}-\hat{p^{k}}_{t}\|\Big{)}},$

where $p^{k}$ denotes the position of the $k^{\rm th}$ body. The weights for
reward components are
$w^{p}=0.2,w^{o}=0.05,w^{v}=0.05,w^{jp}=0.45,w^{jv}=0.05,w^{k}=0.15$.