We study the reinforcement learning (RL) problem in a constrained Markov decision process (CMDP), where an agent explores the environment to maximize the expected cumulative reward while satisfying a single constraint on the expected total utility value in every episode. While this problem is well understood in the tabular setting, theoretical results for function approximation remain scarce. This paper closes the gap by proposing an RL algorithm for linear CMDPs that achieves $\tilde{\mathcal{O}}(\sqrt{K})$ regret with an episode-wise zero-violation guarantee. Furthermore, our method is computationally efficient, scaling polynomially with problem-dependent parameters while remaining independent of the state space size. Our results significantly improve upon recent linear CMDP algorithms, which either violate the constraint or incur exponential computational costs.

On manifolds with metrics, minimizing geodesics, or shortest paths, are minimum-length curves connecting points. Various real-world tasks can be reduced to the generation of geodesics on manifolds. Examples include time-optimal path planning on sloping ground [Matsumoto, 1989], robot motion planning under various constraints [LaValle, 2006, Ratliff et al., 2015], physical systems [Pfeifer, 2019], the Wasserstein distance [Agueh, 2012], and image morphing [Michelis and Becker, 2021, Effland et al., 2021]. Typically, metrics are only known infinitesimally (a form of a Riemannian or Finsler metric), and their distance functions are not known beforehand. Computation of geodesics by solving optimization problems or differential equations is generally computationally costly and requires an explicit form of the metric, or at least, values of its differentials.

The human brain's plasticity allows for the integration of artificial body parts into the human body. Leveraging this, embodied systems realize intuitive interactions with the environment. We introduce a novel concept: embodied swarm robots. Swarm robots constitute a collective of robots working in harmony to achieve a common objective, in our case, serving as functional body parts. Embodied swarm robots can dynamically alter their shape, density, and the correspondences between body parts and individual robots. We contribute an investigation of the influence on embodiment of swarm robot-specific factors derived from these characteristics, focusing on a hand. Our paper is the first to examine these factors through virtual reality (VR) and real-world robot studies to provide essential design considerations and applications of embodied swarm robots. Through quantitative and qualitative analysis, we identified a system configuration to achieve the embodiment of swarm robots.

We propose an efficient framework using the Dehornoy order for homotopy-aware multi-agent path planning in the plane. We developed a method to generate homotopically distinct solutions of multi-agent path planning problem in the plane by combining our framework with revised prioritized planning and proved its completeness under specific assumptions. Experimentally, we demonstrated that the runtime of our method grows approximately quintically with the number of agents. We also confirmed the usefulness of homotopy-awareness by showing experimentally that generation of homotopically distinct solutions by our method contributes to planning low-cost trajectories for a swarm of agents.

Multi-agent path planning (MAPP) is the problem of planning collision-free trajectories from start to goal locations for a team of agents. This work explores a relatively unexplored setting of MAPP where streams of agents have to go through the starts and goals with high throughput. We tackle this problem by formulating a new variant of MAPP called periodic MAPP in which the timing of agent appearances is periodic. The objective with periodic MAPP is to find a periodic plan, a set of collision-free trajectories that the agent streams can use repeatedly over periods, with periods that are as small as possible. To meet this objective, we propose a solution method that is based on constraint relaxation and optimization. We show that the periodic plans once found can be used for a more practical case in which agents in a stream can appear at random times. We confirm the effectiveness of our method compared with baseline methods in terms of throughput in several scenarios that abstract autonomous intersection management tasks.

This study presents a benchmark for evaluating action-constrained reinforcement learning (RL) algorithms. In action-constrained RL, each action taken by the learning system must comply with certain constraints. These constraints are crucial for ensuring the feasibility and safety of actions in real-world systems. We evaluate existing algorithms and their novel variants across multiple robotics control environments, encompassing multiple action constraint types. Our evaluation provides the first in-depth perspective of the field, revealing surprising insights, including the effectiveness of a straightforward baseline approach. The benchmark problems and associated code utilized in our experiments are made available online at github.com/omron-sinicx/action-constrained-RL-benchmark for further research and development.