The Multi-Agent Path Finding (MAPF) problem is a computationally challenging task that involves coordinating collision-free trajectories for multiple cooperative agents. Although existing methods address corridor symmetry, where agents encounter repeated bidirectional conflicts in constrained environments, they typically focus exclusively on pairwise agent interactions. Our observations reveal that such pairwise symmetry frequently arises when multiple agents traverse shared corridors, necessitating repeated applications of the corridor reasoning technology over extended durations. To overcome this limitation, we propose a multi-agent corridor reasoning (MAC) technology capable of resolving group-level corridor symmetry in a single optimization step. Our theoretical analysis demonstrates that this technology preserves the completeness and optimality guarantees of Conflict-Based Search (CBS). By integrating MAC technology with CBSH-RTC, we developed CBSH-MACRT, which significantly outperforms state-of-the-art algorithms (CBSH-RTC and CBSH with mutex propagation) on standardized MAPF benchmarks, improving success rates by 8–40% and cutting runtimes by 14–67%.

The Multi-Agent Combinatorial Path Finding (MCPF) problem is a generalized version of the Multi-Agent Path Finding (MAPF) problem, in which each agent must collectively visit multiple intermediate target locations on the way to its final destination. The state-of-the-art approach for addressing MCPF, known as Conflict-Based Steiner Search (CBSS) [1], leverages K-best joint sequences to create multiple search trees, and employs a CBS-like search to resolve collisions for each tree. Despite its optimality guarantee, CBSS is computationally burdensome due to the duplicated collision resolutions across multiple trees and the computation of the K best joint sequences. To address these challenges, we propose a novel algorithm called Improved Conflict-Based Steiner Search (ICBSS), aiming at expediting CBSS by replacing the multi trees with a single constraint tree (CT), which can be implemented by interleaving the time-dependent traveling salesman algorithm to compute the optimal joint path for agents under the newly generated constraints in each CT vertex. Additionally, we introduce a sub-optimal variant of ICBSS, which improves computational efficiency at the expense of solution optimality. Empirical results show that ICBSS outperforms state-of-the-art MCPF algorithms on a variety of MAPF instances.

We investigate the Combined Target-Assignment and Path-Finding (TAPF) problem that computes both task assignments and collision-free paths for multiple agents, that is, each agent is required to select a target from an underlying set, reaching which leads to a payoff. There is a cost closely related to the time required for each agent to reach the goal. The objective is to maximize the minimum gain generated by the agents. We proposed a Compilation-Based Approach with Heuristics (TA-CBWH) to approximate the optimal solution, behind which are two critical ideas: (i) for a specific task assignment, we formulate an integer linear programming (ILP) and create the iteration combined with large neighborhood search (LNS) to quickly improve the solution quality to near-optimal; (ii) regarding distinct task assignments, a switching mechanism is developed to determine the most promising iteration while progressively eliminating unnecessary task assignments. Comparative experiments demonstrate that TA-CBWH outperforms a wide range of existing approaches across various maps and different numbers of agents.

Global app marketplaces make families in foreign countries easily accessible to developers, but most scholarship on joint media engagement (JME) between parents and children reports on data from participants in Western contexts. We conducted an observational lab study to examine how preschoolers (age 3-5) and parents (N=74) from three different regions of the world (communities in China, Taiwan, and the United States) engage with two types of tablet games: an instructional game with goals and an exploratory, open-ended game. We found systematic differences among groups and between games. For example, parents from China and Taiwan frequently picked up their child's hand and used it as a tool to engage with the screen, a practice parents in our U.S. sample did not employ. Dyads from all three samples exhibited more warmth when playing an instructional game than an exploratory one. Our results suggest that characteristics of the populations we sampled interact with design features, that is, the same design prompted opposing behaviors in different groups. We conclude that it may be useful to examine goal-free and goal-oriented JME as separate constructs, that design choices influence the roles parents adopt during JME, and that the range of behaviors we observed complicate the prevailing research narrative of what positive and productive JME looks like.