Search

Among sub-optimal Multi-Agent Path Finding (MAPF) solvers, rule-based algorithms are particularly appealing since they are complete. Even in crowded scenarios, they allow finding a feasible solution that brings each agent to its target, preventing deadlock situations. However, generally, rule-based algorithms provide much longer solutions than the shortest one. The main contribution of this paper is introducing a new local search procedure for improving a known feasible solution. We start from a feasible sub-optimal solution, and perform a local search in a neighborhood of this solution. If we are able to find a shorter solution, we repeat this procedure until the solution cannot be shortened anymore. At the end, we obtain a solution that is still sub-optimal, but generally of much better quality than the initial one. We propose two different local search policies. In the first, we explore all paths in which the agents positions remain in a neighborhood of the corresponding positions of the reference solution. In the second, we set an upper limit to the number of agents that can change their path with respect to the reference solution. These two different policies can also be alternated. We explore the neighborhoods by dynamic programming. The fact that our search is local is fundamental in terms of time complexity. Indeed, if the dynamic programming approach is applied to the full MAPF problem, the number of explored states grows exponentially with the number of agents. Instead, the introduction of a locality constraint allows exploring the neghborhoods in a time that grows polynomially with respect to the number of agents., Comment: arXiv admin note: text overlap with arXiv:2304.01765

We consider a road network represented by a directed graph. We assume to collect many measurements of traffic flows on all the network arcs, or on a subset of them. We assume that the users are divided into different groups. Each group follows a different path. The flows of all user groups are modeled as a set of independent Poisson processes. Our focus is estimating the paths followed by each user group, and the means of the associated Poisson processes. We present a possible solution based on a Dynamic Programming algorithm. The method relies on the knowledge of high order cumulants. We discuss the theoretical properties of the introduced method. Finally, we present some numerical tests on well-known benchmark networks, using synthetic data.

Fast electronic readout for high-channel density scintillator-based systems is needed for radiation tracking and imaging in a wide range of applications, including nuclear physics, nuclear security and nonproliferation. Programmable electronics, like FPGAs and ASICs, provide a fast way of conditioning and processing the signal in real time. In this paper, we present a pulse shape discrimination (PSD) method based on the shaping circuit of a commercially available ASIC, the Citiroc1A by CAEN Technologies. We used two different shaping times per detector channel to calculate a shaping parameter that enables PSD. Using our new method, neutron and gamma-ray pulses detected by a d$_{12}$-stilbene scintillator can be effectively discriminated at light output values greater than 0.15 MeVee. While not achieving the PSD performance of traditional offline charge integration, our method does not require the transfer of data to a separate system for further processing and enables the direct deployment of high-channel density multi-particle detection systems. Moreover, the availability of a wider range of shaping times than those on the Citiroc1A can potentially further improve the PSD performance., Comment: 20 pages, 17 figures

We address the problem of parameter identification for the standard pharmacokinetic/pharmacodynamic (PK/PD) model for anesthetic drugs. Our main contribution is the development of a global optimization method that guarantees finding the parameters that minimize the one-step ahead prediction error. The method is based on a branch-and-bound algorithm, that can be applied to solve a more general class of nonlinear regression problems. We present some simulation results, based on a dataset of twelve patients. In these simulations, we are always able to identify the exact parameters, despite the non-convexity of the overall identification problem.

The behavior of cyclists when choosing the path to follow along a road network is not uniform. Some of them are mostly interested in minimizing the travelled distance, but some others may also take into account other features such as safety of the roads or pollution. Individuating the different groups of users, estimating the numerical consistency of each of these groups, and reporting the weights assigned by each group to different characteristics of the road network, is quite relevant. Indeed, when decision makers need to assign some budget for infrastructural interventions, they need to know the impact of their decisions, and this is strictly related to the way users perceive different features of the road network. In this paper, we propose an optimization approach to detect the weights assigned to different road features by various user groups, leveraging knowledge of the true paths followed by them, accessible, for example, through data collected by bike-sharing services.

We consider the speed planning problem for a vehicle moving along an assigned trajectory, under maximum speed, tangential and lateral acceleration, and jerk constraints. The problem is a nonconvex one, where nonconvexity is due to jerk constraints. We propose a convex relaxation, and we present various theoretical properties. In particular, we show that the relaxation is exact under some assumptions. Also, we rewrite the relaxation as a Second Order Cone Programming (SOCP) problem. This has a relevant practical impact, since solvers for SOCP problems are quite efficient and allows solving large instances within tenths of a second. We performed many numerical tests, and in all of them the relaxation turned out to be exact. For this reason, we conjecture that the convex relaxation is always exact, although we could not give a formal proof of this fact.

The pebble motion on trees (PMT) problem consists in finding a feasible sequence of moves that repositions a set of pebbles to assigned target vertices. This problem has been widely studied because, in many cases, the more general Multi-Agent path finding (MAPF) problem on graphs can be reduced to PMT. We propose a simple and easy to implement procedure, which finds solutions of length O(knc + n^2), where n is the number of nodes, $k$ is the number of pebbles, and c the maximum length of corridors in the tree. This complexity result is more detailed than the current best known result O(n^3), which is equal to our result in the worst case, but does not capture the dependency on c and k.

In this paper, we propose a branch-and-bound algorithm for solving nonconvex quadratic programming problems with box constraints (BoxQP). Our approach combines existing tools, such as semidefinite programming (SDP) bounds strengthened through valid inequalities, with a new class of optimality-based linear cuts which leads to variable fixing. The most important effect of fixing the value of some variables is the size reduction along the branch-and-bound tree, allowing to compute bounds by solving SDPs of smaller dimension. Extensive computational experiments over large dimensional (up to $n=200$) test instances show that our method is the state-of-the-art solver on large-scale BoxQPs. Furthermore, we test the proposed approach on the class of binary QP problems, where it exhibits competitive performance with state-of-the-art solvers.

We discuss C-MP and C-MAPF, generalizations of the classical Motion Planning (MP) and Multi-Agent Path Finding (MAPF) problems on a directed graph G. Namely, we enforce an upper bound on the number of agents that occupy each member of a family of vertex subsets. For instance, this constraint allows maintaining a safety distance between agents. We prove that finding a feasible solution of C-MP and C-MAPF is NP-hard, and we propose a reduction method to convert them to standard MP and MAPF. This reduction method consists in finding a subset of nodes W and a reduced graph G/W, such that a solution of MAPF on G/W provides a solution of C-MAPF on G. Moreover, we study the problem of finding W of maximum cardinality, which is strongly NP-hard.

On an assigned graph, the problem of Multi-Agent Pathfinding (MAPF) consists in finding paths for multiple agents, avoiding collisions. Finding the minimum-length solution is known to be NP-hard, and computation times grows exponentially with the number of agents. However, in industrial applications, it is important to find feasible, suboptimal solutions, in a time that grows polynomially with the number of agents. Such algorithms exist for undirected and biconnected directed graphs. Our main contribution is to generalize these algorithms to the more general case of strongly connected directed graphs. In particular, given a MAPF problem with at least two holes, we present an algorithm that checks the problem feasibility in linear time with respect to the number of nodes, and provides a feasible solution in polynomial time.

The purpose of this work is to introduce and characterize the Bounded Acceleration Shortest Path (BASP) problem, a generalization of the Shortest Path (SP) problem. This problem is associated to a graph: the nodes represent positions of a mobile vehicle and the arcs are associated to pre-assigned geometric paths that connect these positions. BASP consists in finding the minimum-time path between two nodes. Differently from SP, we require that the vehicle satisfy bounds on maximum and minimum acceleration and speed, that depend on the vehicle position on the currently traveled arc. We prove that BASP is NP-hard and define solution algorithm that achieves polynomial time-complexity under some additional hypotheses on problem data., Comment: 39 pages

In the Celis-Dennis-Tapia (CDT) problem a quadratic function is minimized over a region defined by two strictly convex quadratic constraints. In this paper we re-derive a necessary and optimality condition for the exactness of the dual Lagrangian bound (equivalent to the Shor relaxation bound in this case). Starting from such condition we propose to strengthen the dual Lagrangian bound by adding one or two linear cuts to the Lagrangian relaxation. Such cuts are obtained from supporting hyperplanes of one of the two constraints. Thus, they are redundant for the original problem but they are not for the Lagrangian relaxation. The computational experiments show that the new bounds are effective and require limited computing times. In particular, one of the proposed bounds is able to solve all but one of the 212 hard instances of the CDT problem presented in [Burer, Anstreicher, 2013].

In this paper we propose a variant of the linear least squares model allowing practitioners to partition the input features into groups of variables that they require to contribute similarly to the final result. The output allows practitioners to assess the importance of each group and of each variable in the group. We formally show that the new formulation is not convex and provide two alternative methods to deal with the problem: one non-exact method based on an alternating least squares approach; and one exact method based on a reformulation of the problem using an exponential number of sub-problems whose minimum is guaranteed to be the optimal solution. We formally show the correctness of the exact method and also compare the two solutions showing that the exact solution provides better results in a fraction of the time required by the alternating least squares solution (assuming that the number of partitions is small). For the sake of completeness, we also provide an alternative branch and bound algorithm that can be used in place of the exact method when the number of partitions is too large, and a proof of NP-completeness of the optimization problem introduced in this paper., Comment: To appear in Springer Machine Learning Journal (https://link.springer.com/journal/10994)

In this paper we address game theory problems arising in the context of network security. In traditional game theory problems, given a defender and an attacker, one searches for mixed strategies which minimize a linear payoff functional. In the problems addressed in this paper an additional quadratic term is added to the minimization problem. Such term represents switching costs, i.e., the costs for the defender of switching from a given strategy to another one at successive rounds of a Nash game. The resulting problems are nonconvex QP ones with linear constraints and turn out to be very challenging. We will show that the most recent approaches for the minimization of nonconvex QP functions over polytopes, including commercial solvers such as CPLEX and GUROBI, are unable to solve to optimality even test instances with n = 50 variables. For this reason, we propose to extend with them the current benchmark set of test instances for QP problems. We also present a spatial branch-and-bound approach for the solution of these problems, where a predominant role is played by an optimality-based domain reduction, with multiple solutions of LP problems at each node of the branch-and-bound tree. Of course, domain reductions are standard tools in spatial branch-and-bound approaches. However, our contribution lies in the observation that, from the computational point of view, a rather aggressive application of these tools appears to be the best way to tackle the proposed instances. Indeed, according to our experiments, while they make the computational cost per node high, this is largely compensated by the rather slow growth of the number of nodes in the branch-and-bound tree, so that the proposed approach strongly outperforms the existing solvers for QP problems.

The problem of planar registration consists in finding the transformation that better aligns two point sets. In our setting, the search domain is the set of planar rigid transformations and the objective function is the sum of the distances between each point of the transformed source set and the destination set. We consider a Branch and Bound (BnB) method for finding the globally optimal solution. The algorithm recursively splits the search domain into boxes and computes an upper and a lower bound for the minimum value of the restricted problem. The main contribution of this work is the introduction of a novel lower bound, the relaxation bound, which corresponds to the solution of a concave relaxation of the objective function based on the linearization of the distance. In the BnB we also employ the so called cheap bound, equal to to the sum of the minimum distances between each point of source point set, transformed according to current box, and all the candidate points in the destination point set. We prove, both theoretically and practically, that the novel relaxation bound dominates the cheap bound over small boxes. More precisely, from the theoretical point of view, we prove that the relaxation bound is a second-order approximation of the minimum value, i.e., its distance from the minimum value decreases quadratically with respect to the diameter of the box (see Theorem 1), while the cheap bound is a first-order one (see Proposition 3). From the practical point of view, we show through different computational experiments that the addition of the relaxation bound considerably enhances the performance of the BnB algorithm, compensating the higher cost of its computation with respect to the cheap bound with a strong reduction of the number of BnB nodes to be explored., Comment: 40 pages, 13 figures, 2 tables

In this paper, we address a class of specially structured problems that include speed planning, for mobile robots and robotic manipulators, and dynamic programming. We develop two new numerical procedures, that apply to the general case and to the linear subcase. With numerical experiments, we show that the proposed algorithms outperform generic commercial solvers., Comment: 27 pages, 9 figures, 1 table

For a vehicle on an assigned path, we find the minimum-time speed law that satisfies kinematic and dynamic constraints, related to maximum speed and maximum tangential and transversal acceleration. We present a necessary and sufficient condition for the feasibility of the problem and a simple operator, based on the solution of two ordinary differential equations, which computes the optimal solution. Theoretically, we show that the problem feasible set, if not empty, is a lattice, whose supremum element corresponds to the optimal solution., Comment: 14 pages, 7 figures

We consider the speed planning problem for a robotic manipulator. In particular, we present an algorithm for finding the time-optimal speed law along an assigned path that satisfies velocity and acceleration constraints and respects the maximum forces and torques allowed by the actuators. The addressed optimization problem is a finite dimensional reformulation of the continuous-time speed optimization problem, obtained by discretizing the speed profile with N points. The proposed algorithm has linear complexity with respect to N and to the number of degrees of freedom. Such complexity is the best possible for this problem. Numerical tests show that the proposed algorithm is significantly faster than algorithms already existing in literature.

In this paper we define a discrete dynamical system that governs the evolution of a population of agents. From the dynamical system, a variant of Differential Evolution is derived. It is then demonstrated that, under some assumptions on the differential mutation strategy and on the local structure of the objective function, the proposed dynamical system has fixed points towards which it converges with probability one for an infinite number of generations. This property is used to derive an algorithm that performs better than standard Differential Evolution on some space trajectory optimization problems. The novel algorithm is then extended with a guided restart procedure that further increases the performance, reducing the probability of stagnation in deceptive local minima., Comment: IEEE Transactions on Evolutionary Computation 2011. ISSN 1089-778X