Search for: All records

We solve the TSP for moving targets. 

Conventional Multi-Agent Path Finding (MAPF) problems aim to compute an ensemble of collision-free paths for multiple agents from their respective starting locations to pre-allocated destinations. This work considers a generalized version of MAPF called Multi-Agent Combinatorial Path Finding (MCPF) where agents must collectively visit a large number of intermediate target locations along their paths before arriving at destinations. This problem involves not only planning collision-free paths for multiple agents but also assigning targets and specifying the visiting order for each agent (i.e., target sequencing). To solve the problem, we leverage Conflict-Based Search (CBS) for MAPF and propose a novel approach called Conflict-Based Steiner Search (CBSS). CBSS interleaves (1) the collision resolution strategy in CBS to bypass the curse of dimensionality in MAPF and (2) multiple traveling salesman algorithms to handle the combinatorics in target sequencing, to compute optimal or bounded sub-optimal paths for agents while visiting all the targets. We also develop two variants of CBSS that trade off runtime against solution optimality. Our test results verify the advantage of CBSS over the baselines in terms of computing cheaper paths and improving success rates within a runtime limit for up to 20 agents and 50 targets. Finally, we run both Gazebo simulation and physical robot tests to validate that the planned paths are executable 

Self-propelling organisms locomote via generation of patterns of self-deformation. Despite the diversity of body plans, internal actuation schemes and environments in limbless vertebrates and invertebrates, such organisms often use similar traveling waves of axial body bending for movement. Delineating how self-deformation parameters lead to locomotor performance (e.g. speed, energy, turning capabilities) remains challenging. We show that a geometric framework, replacing laborious calculation with a diagrammatic scheme, is well-suited to discovery and comparison of effective patterns of wave dynamics in diverse living systems. We focus on a regime of undulatory locomotion, that of highly damped environments, which is applicable not only to small organisms in viscous fluids, but also larger animals in frictional fluids (sand) and on frictional ground. We find that the traveling wave dynamics used by mm-scale nematode worms and cm-scale desert dwelling snakes and lizards can be described by time series of weights associated with two principal modes. The approximately circular closed path trajectories of mode weights in a self-deformation space enclose near-maximal surface integral (geometric phase) for organisms spanning two decades in body length. We hypothesize that such trajectories are targets of control (which we refer to as “serpenoid templates”). Further, the geometric approach reveals how seemingly complex behaviors such as turning in worms and sidewinding snakes can be described as modulations of templates. Thus, the use of differential geometry in the locomotion of living systems generates a common description of locomotion across taxa and provides hypotheses for neuromechanical control schemes at lower levels of organization. 

Multi-Agent Path Finding (MA-PF) computes a set of collision-free paths for multiple agents from their respective starting locations to destinations. This paper considers a generalization of MA-PF called Multi-Agent Teamwise Cooperative Path Finding (MA-TC-PF), where agents are grouped as multiple teams and each team has its own objective to be minimized. For example, an objective can be the sum or max of individual arrival times of the agents. In general, there is more than one team, and MA-TC-PF is thus a multi-objective planning problem with the goal of finding the entire Paretooptimal front that represents all possible trade-offs among the objectives of the teams. To solve MA-TC-PF, we propose two algorithms TC-CBS and TC-M*, which leverage the existing CBS and M* for conventional MA-PF. We discuss the conditions under which the proposed algorithms are complete and are guaranteed to find the Pareto-optimal front. We present numerical results for several types of MA-TC-PF problems. 

Conventional Multi-Agent Path Finding (MAPF) problems aim to compute an ensemble of collision-free paths for multiple agents from their respective starting locations to pre-allocated destinations. This work considers a generalized version of MAPF called Multi-Agent Combinatorial Path Finding (MCPF) where agents must collectively visit a large number of intermediate target locations along their paths before arriving at destinations. This problem involves not only planning collision-free paths for multiple agents but also assigning targets and specifying the visiting order for each agent (i.e., target sequencing). To solve the problem, we leverage Conflict-Based Search (CBS) for MAPF and propose a novel approach called Conflict-Based Steiner Search (CBSS). CBSS interleaves (1) the collision resolution strategy in CBS to bypass the curse of dimensionality in MAPF and (2) multiple traveling salesman algorithms to handle the combinatorics in target sequencing, to compute optimal or bounded sub-optimal paths for agents while visiting all the targets. We also develop two variants of CBSS that trade off runtime against solution optimality. Our test results verify the advantage of CBSS over the baselines in terms of computing cheaper paths and improving success rates within a runtime limit for up to 20 agents and 50 targets. Finally, we run both Gazebo simulation and physical robot tests to validate that the planned paths are executable.