Abstract In this paper we consider nonconvex diagonal Quadratically Constrained Quadratic Programming (QCQP) problems, where at least one constraint is strictly convex. A lower bound for such problems can be computed through a Lagrangian relaxation, where all constraints, except the strictly convex constraint, are moved into the objective function, suitably weighted by a vector of Lagrange multipliers. The search for the best (largest) Lagrangian bound leads to the definition of the dual Lagrangian problem. The aim of this paper is to provide sufficient as well as necessary and sufficient conditions under which exactness of the dual Lagrangian bound (i.e., the equivalence of its optimal value with the optimal value of the original nonconvex problem) is guaranteed. Some of these conditions are based on the solution of linear feasibility problems defined over the space of the Lagrange multipliers, some others on the solution of convex problems over the same space. We specialize the results proved for general diagonal QCQPs to the special case where the constraints are linear, ball and reverse ball constraints, i.e., the Hessian matrices of the constraint quadratic functions are null matrices (linear constraints), identity matrices (ball constraints), and the opposite of identity matrices (reverse ball constraints). We show that in this special case the conditions can be evaluated much more efficiently. Finally, we perform experiments over random instances to identify relevant factors which affect both exactness of the dual Lagrangian bound and the ability of detecting such exactness through the proposed sufficient conditions.

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, we describe a procedure that checks the problem feasibility in linear time with respect to the number of vertices n , and we find a necessary and sufficient condition for feasibility of any MAPF instance. Moreover, we present an algorithm (diSC) that provides a feasible solution of length O ( k n 2 c ) , where k is the number of agents and c the maximum length of the corridors of the graph.

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(|P|nc + n2), where n is the number of nodes, P is the set 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(n3), which is equal to our result in the worst case, but does not capture the dependency on c and |P|.

In a high-speed palletizing machine, packages of various sizes are inserted on a conveyor belt. Then, cooperating multiple robotic manipulators move them to obtain a desired final layout. The throughput of this palletizing process critically hinges upon the strategic selection of the insertion sequence and the careful choice of robot manipulations. Pursuing a higher throughput in this context holds great importance due to its potential to enhance productivity, however, reaching such goal constitutes a challenging task. Indeed, the problem of maximizing the throughput of the palletizing machine is a nontrivial one and, despite its relevant importance in industrial settings, it has not received much attention in existing literature. In this work, we present a Dynamic Programming-based algorithm, together with some reduction techniques, that allows finding the shortest packages sequence and the corresponding robot manipulations that maximize production. We include some numerical experiments on randomly generated problems and on actual industrial scenarios, which show the good performance of the proposed method.Note to Practitioners—This work is motivated by the need of high-speed palletizing machine manufacturers to automate the generation of packages sequences, and the corresponding robot manipulations tasks assignment. We solve this problem with a Dynamic Programming-based algorithm. The benefit of the proposed method is twofold. On one hand, it allows palletizing machines manufacturers not to waste their employees’ time on the often lengthy task of manually planning packages sequences and manipulations. On the other hand, the proposed approach allows minimizing the time required to assemble an assigned layout, increasing the overall throughput of the production chain. The proposed algorithm can be implemented in any programming language of choice (e.g., C$++$) and integrated by manufacturers in their production software. The main limitation of this approach is the computational time which grows exponentially with the number of packages. However, given that the application is an off-line one, this approach allows handling most of the industrial layouts, which usually consist of a few tens of packages, in a reasonable amount of time. As future developments, the approach could be generalized to handle more complicated manipulator movements and/or allow robots to manipulate each package more than once. This would add a layer of complexity that would require nontrivial tailored solution strategies in order to handle these new degrees of freedom.

In this article, we discuss a sequential algorithm for the computation of a minimum-time speed profile over a given path, under velocity, acceleration, and jerk constraints. Such a problem arises in industrial contexts, such as automated warehouses, where LGVs need to perform assigned tasks as fast as possible in order to increase productivity. It can be reformulated as an optimization problem with a convex objective function, linear velocity and acceleration constraints, and nonconvex jerk constraints, which, thus, represent the main source of the difficulty. While existing nonlinear programming (NLP) solvers can be employed for the solution of this problem, it turns out that the performance and robustness of such solvers can be enhanced by the sequential line-search algorithm proposed in this article. At each iteration, a feasible direction, with respect to the current feasible solution, is computed, and a step along such direction is taken in order to compute the next iterate. The computation of the feasible direction is based on the solution of a linearized version of the problem, and the solution of the linearized problem, through an approach that strongly exploits its special structure, represents the main contribution of this work. The efficiency of the proposed approach with respect to existing NLP solvers is proven through different computational experiments. Note to Practitioners—This article was motivated by the needs of LGV manufacturers. In particular, it presents an algorithm for computing the minimum-time speed law for an LGV along a preassigned path, respecting assigned velocity, acceleration, and jerk constraints. The solution algorithm should be: 1) fast, since speed planning is made continuously throughout the workday, not only when an LGV receives a new task but also during the execution of the task itself, since conditions may change, e.g., if the LGV has to be halted for security reasons and 2) reliable, i.e., it should return solutions of high quality, because a better speed profile allows to save time and even small percentage improvements, say a 5% improvement, has a considerable impact on the productivity of the warehouse, and, thus, determines a significant economic gain. The algorithm that we propose meets these two requirements, and we believe that it can be a useful tool for LGV manufacturers and users. It is obvious that the proposed method also applies to the speed planning problem for vehicles other than LGVs, e.g., road vehicles.

In this paper an optimized robust feedforward/feedback control strategy for anesthesia induction is proposed. Propofol is used to induce hypnosis and the bispectral index scale (BIS) is employed as an indicator of depth of hypnosis. The control action is divided in two parts, a feedforward action, which acts alone in the first phase of anesthesia induction, and a feedback PID action that concludes the induction by smoothly driving the BIS to the target value. The feedforward action is given by an optimized bolus of propofol that is determined by taking into account the uncertainty of the nonlinear pharmacodynamic model for the effect of propofol on BIS. In particular, the bolus is obtained as the solution of a constrained minimum-time control problem in order to minimize the induction time of anesthesia while preventing the undershoot of the BIS level. Thus the patient’s safety is ensured by avoiding side-effects due to drug overdosing. The PID controller is then used in order to compensate for the deviation of the BIS from the theoretical behaviour caused by the effect of inter-patient and intra-patient variability.

In this paper, 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 industrial weight-filling machines, containers are filled with the liquid stored in a tank by an electronically controlled valve. The weight is sensed through a load cell. We develop a learning algorithm that predicts the right closure time as a function of liquid pressure and temperature. The algorithm solves a non-convex robust regression problem and is based on a branch and bound approach in regressors space.

Mobile Cloud Computing (MCC) is an emerging paradigm aiming to elastically extend the range of resource-intensive tasks supported by mobile devices, leveraging upon broadband connectivity and cloud-based resources. In literature, almost all MCC models focus on mobile devices, considering the Cloud as a system endowed with unlimited resources. In this paper, we illustrate a novel MCC model characterized by the presence of adaptive loops, i.e., feedback interactions between the mobile device and the Cloud, with the purpose to enforce adaptive behavior on both sides. Indeed, the Cloud adapts its resource allocation (number of activated virtual machines) to the workload provided by mobile devices. On the other hand, feedback from the Cloud allows mobile devices to improve offloading decisions. The performance of the whole system is heavily affected by the auto-scaling strategy adopted by the Cloud. By means of simulations, we have evaluated the impact of two very different auto-scaling strategies. Quantitative results are reported and discussed.

It is assumed that a central pattern generator possesses an exponentially stable limit cycle, which originates a periodic output signal. We propose a method based on a Gauss-Newton iteration to determine the values of the neural coupling parameters that allows to approximate a given reference output signal. We present two applications. The first is a ring network of Morris-Lecar neurons, where the output of the system is the sum of the membrane potential of all neurons. The second is a network of six neural cells for the generation of the leg movements of a hexapod.

The paper considers a minimum-time feedforward motion control problem for an open container carrying a liquid. The proposed solution is a time-continuous acceleration planning that avoids liquid spilling and satisfies amplitude constraints on jerk, acceleration, and velocity of the container moving on a linear guide of an automation line. This solution is based on linear programming and can provide rest-to-rest liquid motion planning or, alternatively, a rest-to-disequilibrium planning with bounded post-motion liquid oscillations. Experimental results on a test bench prototype show the effectiveness of the presented approach.

The article consider the Cartesian trajectory tracking of wheeled mobile robots to be performed by a hybrid control scheme with feedforward inverse control and a state feedback that is only updated periodically and relies on a recursive convex replanning of the reference trajectory. This approach applied to the standard unicycle model is shown to maintain its efficacy also in presence of noise or unmodeled robot dynamics. Explicit, sufficient conditions are provided to ensure global boundedness of the tracking error. Experimental results are presented using Lego Mindstorm mobile robots.

The paper deals with a general class of leader-follower formations of unicycle robots induced by a constraint function that depends on the position and the orientation of the vehicles. We study the flexibility of such formations by introducing the notion of formation internal dynamics, characterize its equilibria and give sufficient geometric conditions for their existence. In particular, we show that the displacement and the relative orientation of each follower with respect to the leader's reference frame are fixed if and only if the robots either move along circular paths or parallel straight lines. These equilibrium configurations always exist if the trajectory of the leader is a circle of sufficiently small curvature or a straight line.

The paper proposes a new geometric approach to the stabilization of a hierarchical formation of unicycle robots. Hierarchical formations consist of elementary leader-follower units disposed on a rooted tree: each follower sees its relative leader as a fixed point in its own reference frame. Robots' linear velocity and trajectory curvature are forced to satisfy some given bounds. The major contribution of the paper is to study the effect of these bounds on the admissible trajectories of the main leader. In particular, we provide recursive formulas for the maximum velocity and curvature allowed for the main leader, so that the robots can achieve the desired formation while respecting their input constraints. An original formation control law is proposed and the asymptotic stabilization is proved. Simulation experiments illustrate the theory and show the effectiveness of the proposed designs.

The paper proposes a linear programming approach to the feedforward minimum-time control of flexible joints. Taking into account both input and output constraints, the optimal bang-bang control is computed by discretizing a continuous-time joint model and by solving a sequence of linear programming feasibility problems. The resulting joint motion is a smooth rest-to-rest motion without oscillations. Experimental results illustrate the proposed open-loop technique.

The paper focuses on leader-follower formations of nonholonomic mobile robots. A formation control alternative to those existing in the literature is introduced. We show that the geometry of the formation imposes a bound on the maximum admissible curvature of leader trajectory. A peculiar feature of the proposed strategy is that the followers position is not rigidly fixed with respect to the leader reference frame but varies in suitable cones centered in the leader reference frame. Our approach also applies to hierarchical multirobot formations described by rooted tree graphs. Simulation experiments confirm the effectiveness of the proposed control schemes.