Fleet Management

manirajan · 2021-06-08T04:19:17.170Z

Hello,

I am developing Fleet management system for multi robots and looking for optimized and standard method for traffic control and path planning. Do the centralized system get the input from device and make plan or devices communicate each other and make a diversion while moving.

Please share your thoughts

Thanks

grey · 2021-06-08T07:44:12.203Z

Both centralized and distributed methods for fleet management are feasible. There are considerable advantages and disadvantages to each, so the choice between the two will ultimately depend on your overall requirements, and which method is a better fit for those requirements.

Open Robotics is currently working on an open source platform-agnostic mobile robot fleet management+integration framework called the “Robotics Middleware Framework” (RMF). You can find some high-level documentation on the project here. The landing page for the source code is here. This work is still in the R&D phase, but it’s actively moving towards production.

The traffic management in RMF is designed to use a distributed approach, although it supports centralized planning (as a rule of thumb, it’s easier to centralize a distributed system than to distribute a centralized system). As explained here there are two major dimensions to the traffic management:

Prevention. There is a centralized schedule that all robots report their intended trajectories to, and which all the robots can read (asynchronously). Using this information, the robots can plan optimal routes for themselves that shouldn’t interfere with any of the other robots.
Negotiation. When a traffic conflict is identified despite the preventative measures, a negotiation will be started between the conflicting robots, and they’ll talk peer-to-peer to negotiate an optimal resolution to their conflict.

A design goal of RMF is to allow multiple unrelated proprietary fleet managers to be able to cooperate with each other without changing the way those fleet managers are implemented. We anticipate many of those fleet managers will take a centralized approach to their traffic management, so RMF supports the ability to have one fleet manager that schedules and negotiates on behalf of many robots simultaneously.

The traffic management design in RMF is probably more complex than what’s strictly needed for applications where all robots will always be the same type of platform with the same API on the same network. But it does work for those scenarios, and it carries the benefit that your system won’t be locked into those requirements, making it easier to add new platforms in the future or migrate to more complex setups.

manirajan · 2021-06-09T06:22:36.808Z

Thanks Grey for your explanations and from my understanding each robot read the intended trajectories of remaining robots and make path plan for current task. Can you plz suggest any algorithms or methods which has leverage for this scenario (compare other robot paths and plan) and looking for centralized system configuration required to manage (for example fleet of 5 robots ) from your experience.

victor_sillerico · 2021-06-13T13:47:32.364Z

That’s a really interesting project @manirajan.

Do the centralized system get the input from device and make plan or devices communicate each other and make a diversion while moving.

You can use either a decoupled method or a coupled method.
Motion Planning in Multi-Robot Systems

manirajan · 2021-06-24T10:12:30.683Z

Hi Grey, in a distributed system, what is standard or optimized algorithms for local planner in multi robot environment.

grey · 2021-06-29T07:40:22.809Z

I’d say this is an open area of research, so I don’t think there’s going to be a specific standard to follow. The link that @victor_sillerico provided has a lot of great suggestions in it, but I can mention what we’ve been using for RMF.

If you can define a discrete navigation graph for the robot to follow, then you could use kinodynamic A*. In this context “kinodynamic” means that time and velocity/acceleration constraints are factors for the A* branching. When expanding the search, you should compute each expansion trajectory and verify that it has no collisions with any of the trajectories of other robots that have been given higher priority. If any such collisions exist, then the expansion should be discarded. Note that sitting in place or returning to a previous graph node should be considered valid expansions, which makes pruning the search very tricky.

Using A* will guarantee that your single-robot planner is optimal, relative to the discrete navigation graph. We have a C++ implementation of that planner which can be found here. It’s made for the RMF traffic management stack, but it can be used on its own.

Otherwise if you need to work in free space, then you’ll need a time-configuration space free space motion planner that can account for obstacles with known motion. Here’s a paper that describes the concept of a time-configuration space motion planner, although I can’t say the specific technique being used is relevant.

We’re looking into developing a suitable free space motion planner, but we don’t have any firm timeline for that currently.