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.

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.

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 a previous paper we introduced the concept of semiseparable functor. Here we continue our study of these functors in connection with idempotent (Cauchy) completion. To this aim, we introduce and investigate the notions of (co)reflection and bireflection up to retracts. We show that the (co)comparison functor attached to an adjunction whose associated (co)monad is separable is a coreflection (reflection) up to retracts. This fact allows us to prove that a right (left) adjoint functor is semiseparable if and only if the associated (co)monad is separable and the (co)comparison functor is a bireflection up to retracts, extending a characterization pursued by X.-W. Chen in the separable case. Finally, we provide a semi-analogue of a result obtained by P. Balmer in the framework of pre-triangulated categories.

We propose an infinitesimal counterpart to the notion of braided category. The corresponding infinitesimal braidings are natural transformations which are compatible with an underlying braided monoidal structure in the sense that they constitute a first-order deformation of the braiding. This extends previously considered infinitesimal symmetric or Cartier categories, where involutivity of the braiding and an additional commutativity of the infinitesimal braiding with the symmetry are required. The generalized pre-Cartier framework is then elaborated in detail for the categories of (co)quasitriangular bialgebra (co)modules and we characterize the resulting infinitesimal $\mathcal{R}$-matrices (resp. $\mathcal{R}$-forms) on the bialgebra. It is proven that the latter are Hochschild $2$-cocycles and that they satisfy an infinitesimal quantum Yang-Baxter equation, while they are Hochschild $2$-coboundaries under the Cartier (co)triangular assumption in the presence of an antipode. We provide explicit examples of infinitesimal braidings, particularly on quantum $2\times 2$-matrices, $\mathrm{GL}_q(2)$, Sweedler's Hopf algebra and via Drinfel'd twist deformation. As conceptual tools to produce examples of infinitesimal braidings we prove an infinitesimal version of the FRT construction and we provide a Tannaka-Krein reconstruction theorem for pre-Cartier coquasitriangular bialgebras. We comment on the deformation of infinitesimal braidings and construct a quasitriangular structure on formal power series of Sweedler's Hopf algebra., Comment: 38 pages; conceptualized proof of Prop. 2.7; improved formulations in Def. 2.1, Def. 3.1 and in Thm. 2.6, Thm. 3.2; connection to matched pairs discussed before Lem. 3.16; adjusted relations for $\mathrm{M}_q(2)$ and computations on pages 21-23; minor typo corrections

Among sub-optimal 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 solutions that are much longer than the optimal one. The main contribution of this paper is the introduction of an iterative local search procedure in MAPF. We start from a feasible suboptimal solution and we perform a local search in a neighborhood of this solution, to find a shorter one. Iteratively, we repeat this procedure until the solution cannot be shortened any longer. At the end, we obtain a solution, that is still sub-optimal, but, in general, of much better quality than the initial one. We use dynamic programming for the local search procedure. Under this respect, the fact that our search is local is fundamental to reduce the time complexity of the algorithm. Indeed, if we apply a standard dynamic programming the number of explored states grows exponentially with the number of agents. As we will see, the introduction of a locality constraint allows solving the (local) dynamic programming problem in a time that grows only polynomially with respect to the number of agents.

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.

In this paper we introduce and investigate the notion of semiseparable functor. One of its first features is that it allows a novel description of separable and naturally full functors in terms of faithful and full functors, respectively. To any semiseparable functor we attach an invariant, given by an idempotent natural transformation, which controls when the functor is separable and yields a characterization of separable functors in terms of (dual) Maschke and conservative functors. We prove that any semiseparable functor admits a canonical factorization as a naturally full functor followed by a separable functor. Here the main tool is the construction of the coidentifier category attached to the associated idempotent natural transformation. Then we move our attention to the semiseparability of functors that have an adjoint. First we obtain a Rafael-type Theorem. Next we characterize the semiseparability of adjoint functors in terms of the (co)separability of the associated (co)monads and the natural fullness of the corresponding (co)comparison functor. We also focus on functors that are part of an adjoint triple. In particular, we describe bireflections as semiseparable (co)reflections, or equivalently, as either Frobenius or naturally full (co)reflections. As an application of our results, we study the semiseparability of functors traditionally attached to ring homomorphisms, coalgebra maps, corings and bimodules, introducing the notions of semicosplit coring and semiseparability relative to a bimodule which extend those of cosplit coring and Sugano's separability relative to a bimodule, respectively.

Liftable pairs of adjoint functors between braided monoidal categories in the sense of \cite{GV-OnTheDuality} provide auto-adjunctions between the associated categories of bialgebras. Motivated by finding interesting examples of such pairs, we study general pre-rigid monoidal categories. Roughly speaking, these are monoidal categories in which for every object $X$, an object $X^{\ast}$ and a nicely behaving evaluation map from $X^{\ast}\otimes X$ to the unit object exist. A prototypical example is the category of vector spaces over a field, where $X^{\ast}$ is not a categorical dual if $X$ is not finite-dimensional. We explore the connection with related notions such as right closedness, and present meaningful examples. We also study the categorical frameworks for Turaev's Hopf group-(co)algebras in the light of pre-rigidity and closedness, filling some gaps in literature along the way. Finally, we show that braided pre-rigid monoidal categories indeed provide an appropriate setting for liftability in the sense of loc. cit. and we present an application, varying on the theme of vector spaces, showing how -- in favorable cases -- the notion of pre-rigidity allows to construct liftable pairs of adjoint functors when right closedness of the category is not available.

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

It is known that the so-called monadic decomposition, applied to the adjunction connecting the category of bialgebras to the category of vector spaces via the tensor and the primitive functors, returns the usual adjunction between bialgebras and (restricted) Lie algebras. Moreover, in this framework, the notions of augmented monad and combinatorial rank play a central role. In order to set these results into a wider context, we are led to substitute the monadic decomposition by what we call the adjoint decomposition. This construction has the advantage of reducing the computational complexity when compared to the first one. We connect the two decompositions by means of an embedding and we investigate its properties by using a relative version of Grothendieck fibration. As an application, in this wider setting, by using the notion of augmented monad, we introduce a notion of combinatorial rank that, among other things, is expected to give some hints on the length of the monadic decomposition.

In this paper we set up the foundations around the notions of formal differentiation and formal integration in the context of commutative Hopf algebroids and Lie-Rinehart algebras. Specifically, we construct a contravariant functor from the category of commutative Hopf algebroids with a fixed base algebra to that of Lie-Rinehart algebras over the same algebra, the differentiation functor, which can be seen as an algebraic counterpart to the differentiation process from Lie groupoids to Lie algebroids. The other way around, we provide two interrelated contravariant functors form the category of Lie-Rinehart algebras to that of commutative Hopf algebroids, the integration functors. One of them yields a contravariant adjunction together with the differentiation functor. Under mild conditions, essentially on the base algebra, the other integration functor only induces an adjunction at the level of Galois Hopf algebroids. By employing the differentiation functor, we also analyse the geometric separability of a given morphism of Hopf algebroids. Several examples and applications are presented along the exposition., Comment: Minor changes. Comments are very welcome!

Prompted by an example related to the tensor algebra, we introduce and investigate a stronger version of the notion of separable functor that we call heavily separable. We test this notion on several functors traditionally connected to the study of separability.

In this paper we investigate a family of algebras endowed with a suitable non-degenerate bilinear form that can be used to define two different notions of dual for a given right ideal. We apply our results to the classification of the right ideals and their duals in the cyclic group algebra, in the Taft algebra and in another example of Hopf algebra arising as bosonization.

Let $\mathcal{A}$ and $\mathcal{B}$ be monoidal categories and let $R:\mathcal{A} \rightarrow \mathcal{B}$ be a lax monoidal functor. If $R$ has a left adjoint $L$, it is well-known that the two adjoints induce functors $\overline{R}={\sf Alg}(R):{\sf Alg}(\mathcal{A})\rightarrow {\sf Alg }(\mathcal{B})$ and $\underline{L}={\sf Coalg(L)}:{\sf Coalg}(\mathcal{B})\rightarrow {\sf Coalg}(\mathcal{A})$ respectively. The pair $(L,R)$ is called "liftable" if the functor $\overline{R}$ has a left adjoint and if the functor $\underline{L}$ has a right adjoint. A pleasing fact is that, when $\mathcal{A}$, $\mathcal{B}$ and $R$ are moreover braided, a liftable pair of functors as above gives rise to an adjunction at the level of bialgebras. In this note, sufficient conditions on the category $\mathcal{A}$ for $\overline{R}$ to possess a left adjoint, are given. Natively these conditions involve the existence of suitable colimits that we interpret as objects which are simultaneously initial in four distinguished categories (among which the category of epi-induced objects), allowing for an explicit construction of $\overline{L}$, under the appropriate hypotheses. This is achieved by introducing a relative version of the notion of weakly coreflective subcategory, which turns out to be a useful tool to compare the initial objects in the involved categories. We apply our results to obtain an analogue of Sweedler's finite dual for the category of vector spaces graded by an abelian group $G$ endowed with a bicharacter. When the bicharacter on $G$ is skew-symmetric, a lifted adjunction as mentioned above is explicitly described, inducing an auto-adjunction on the category of bialgebras "colored" by $G$., Comment: The previous verision has been revised by means of weak coreflections and initial objects. The study of pre-rigid categories has been extrapolated and expanded to become an independent research line (arXiv:2201.03952)

We give a description of the category of restricted Lie algebras over a field $\Bbbk $ of prime characteristic by means of monadic decomposition of the functor that computes the $\Bbbk $-vector space of primitive elements of a $\Bbbk $-bialgebra.

We prove that a finite-dimensional Hopf algebra with the dual Chevalley Property over a field of characteristic zero is quasi-isomorphic to a Radford-Majid bosonization whenever the third Hochschild cohomology group in the category of Yetter-Drinfeld modules of its diagram with coefficients in the base field vanishes. Moreover we show that this vanishing occurs in meaningful examples where the diagram is a Nichols algebra.

The aim of this paper is to establish a contravariant adjunction between the category of quasi-bialgebras and a suitable full subcategory of dual quasi-bialgebras, adapting the notion of finite dual to this framework. Various functorial constructions involving non-associative algebras and non-coassociative coalgebras are then carried out. Several examples illustrating our methods are expounded as well.

In this paper Hom-Lie algebras, Lie color algebras, Lie superalgebras and other type of generalized Lie algebras are recovered by means of an iterated construction, known as monadic decomposition of functors, which is based on Eilenberg-Moore categories. To this aim we introduce the notion of Milnor-Moore category as a monoidal category for which a Milnor-Moore type Theorem holds. We also show how to lift the property of being a Milnor-Moore category whenever a suitable monoidal functor is given and we apply this technique to provide examples.

In this paper, the theory to construct quantum lines for general dual quasi-bialgebras is developed followed by some specific examples where the dual quasi-bialgebras are pointed with cyclic group of points.

In this paper we introduce and study Miyashita action in the context of monoidal categories aiming by this to provide a common framework of previous studies in the literature. We make a special emphasis of this action on Azumaya monoids. To this end, we develop the theory of invertible bimodules over different monoids (a sort of Morita contexts) in general monoidal categories as well as their corresponding Miyashita action. Roughly speaking, a Miyashita action is a homomorphism of groups from the group of all isomorphic classes of invertible subobjects of a given monoid to its group of automorphisms. In the symmetric case, we show that for certain Azumaya monoids, which are abundant in practice, the corresponding Miyashita action is always an isomorphism of groups. This generalizes Miyashita's classical result and sheds light on other applications of geometric nature which can not be treated using the classical theory. In order to illustrate our methods, we give a concrete application to the category of comodules over commutative (flat) Hopf algebroids. This obviously includes the special cases of split Hopf algebroids (action groupoids), which for instance cover the situation of the action of an affine algebraic group on an affine algebraic variety.

We give a necessary and sufficient smoothness condition for the scheme parameterizing the n-dimensional representations of a finitely generated associative algebra over an algebraically closed field of characteristic zero. In particular, our result implies that the points M of the above scheme, satisfying $Ext_A ^2(M,M)=0$, are regular. This generalizes well-known results on finite-dimensional algebras to finitely generated algebras., Comment: 15 pages. Accepted for publication in Annales De L'Institut Fourier

In this paper we investigate the categories of braided objects, algebras and bialgebras in a given monoidal category, some pairs of adjoint functors between them and their relations. In particular we construct a braided primitive functor and its left adjoint, the braided tensor bialgebra functor, from the category of braided objects to the one of braided bialgebras. The latter is obtained by a specific elaborated construction introducing a braided tensor algebra functor as a left adjoint of the forgetful functor from the category of braided algebras to the one of braided objects. The behaviour of these functors in the case when the base category is braided is also considered.

We describe all the quasi-bialgebra structures of a group algebra over a torsion-free abelian group. They all come out to be triangular in a unique way. Moreover, up to an isomorphism, these quasi-bialgebra structures produce only one (braided) monoidal structure on the category of their representations. Applying these results to the algebra of Laurent polynomials, we recover two braided monoidal categories introduced in \cite{CG} by S. Caenepeel and I. Goyvaerts in connection with Hom-structures (Lie algebras, algebras, coalgebras, Hopf algebras).