Actor Framework Discussions
RFC: Dynamic Resource Allocation Among Actors
AristosQueue wrote:
although the external system probably needs to handle the possibility of both robots sending the "order more parts" message at the same time to avoid double ordering parts.
This is not at all relevant to your core question, but imo the robot has no business whatsoever instructing another component to "order more parts." Inventory management isn't what the robot is supposed to be doing. The robot *can* and *should* send a "parts bin low" or "parts bin empty" message if there's no other system in place to keep track of what's on the shelves.
---------------------------------
I read through the collision avoidance strategies and it seems they can be categorized as one of two paradigms: Those with an active resource manager (1, 2, 3, and 7) and those that serve resources family style (4, 5, and 6.) (I haven't figured out where 8 fits.) The former request resources from someone else; the latter pass around resources and take what they need. I typically favor an active resource manager (in the form of 1 or 7) simply because I find it easier to understand the system as a whole and predict what the system's behavior will be for any arbitrary situation.
AristosQueue wrote:
I added this as a new pattern in my original post (#7). I like the idea for some things, like use of DAQ channels. How do you establish an "actor" for driving across a floor where empty space is the resource? Is there an actor for every tile square?
Defining empty space as a resource is a little different than defining a DAQ channel as a resource. Space is continuous; DAQ channels are discrete. In my (limited) experience with mobile industrial robot systems the robots are not allowed to take an arbitrary path to their destination. They must follow a network of predefined paths. The helps simplify things a little bit--a continuous 2d resource (floor space) is reduced to a continuous 1d resource (floor space in the direction of travel.)
Maybe the space each actor is responsible for is equal to robot's footprint. Maybe it's a floor tile. Maybe it's arbitrarily sized according to the situation. For example, if there's a 10' path between two storage shelves that is only wide enough to accomodate one robot, that might be considered a single unit of space and be managed by a single actor.
A side question is how are you going to model the system? Do you want to model the connections (intersection-based) or the space between the connections (path-based)? On paper the intersection-based model is more intuitive, but since we're concerned with the space between the intersections and not the intersections themselves I think the path-based model is the better choice.
Thinking about this a bit I'm not sure there's a significant difference in functionality between having each path managed by its own actor and having a central actor managing the paths. If anything the central actor is probably better componentized, easier to understand, and scales better.
The more I consider it the more I don't like the idea of individual actors managing an arbitrary section of floor space in this kind of situation. If your units of space are too small you'll run into inefficiencies. A robot might get most of the way to its destination only to find the path blocked, then have to turn around and go a different route. If the units of space are too large (and that resource cannot be subdivided; it's either "available" or "not available.") you'll have inefficiencies from unused space. The paths are subdivisions of the same shared resource, not individual resources in themselves.
--------------------------------------
Is there a most efficient strategy for resource allocation?
In the general case? Probably not. TCP ports are a resource but allocating them is very different than allocating paths in the example above. TCP ports are independent--any one is as good as another. A single path is generally not useful in isolation. It only has value as a resource if a correct set of paths can be allocated to achieve the goal of getting to the destination. I doubt there's a general solution that works equally well for both situations.
If there is not a general efficient strategy, what are the strategy options and what use cases would lend themselves best to which strategies?
<Thinking out loud>
Let's start by defining the strategic axes. You said collision avoidance vs. collision detection are functionally identical, and I agree, so that's not an axis. As I mentioned above, I think active resource manager vs. family style resource management is one axis. Active resource management has a central controller fielding requests for resources and granting them according to a decision tree. Family style resource management is simply, "if you grab it it's yours until you give it up."
Another strategic axis that comes to mind is what you identified in 1 and 2; resource allocation vs resource scheduling. Resource scheduling allows resources to be reserved for a future point in time to complete the task. Allocation is more along the lines of an "ask for it when you need it and you'll get it when you get it" system.
I also think bulk reservation vs progressive reservation fits in there somewhere, though I'm not sure it's orthogonal to the other axes. A bulk reservation system is one where multiple resources must be sucessfully obtained, otherwise none of them are needed. Think of a group of friends reserving 10 rooms in a single hotel. Reserving a single hotel room is a degenerate case of bulk reservation. Progressive reservation is where multiple resources are required to complete a task, but they are acquired sequentially.
No other strategic axes come to mind at the moment, so here's a first cut at characterizing each combination. Critique invited:
1. Active Management / Resource Allocation / Bulk Reservation
I believe this is probably the simplest strategy to understand and implement. It can work (I think) for any kind of resource. For these reasons I think it's a good starting point. In certain situations where the resource usage rate is high or otherwise constrained it may be very inefficient. For example, if robot 1 is on path 3 and reserves paths 2 and 1 to return to its workstation, robot 2 is stuck waiting for a path to open up, even though they are not blocked at the moment. Still, I think it would be relatively straightforward to refactor this strategy into a more capable strategy if the need arises.
2. Active Management / Resource Allocation / Progressive Reservation
Using the robot situation from the previous combination, robot 1 moves towards the intersection of paths 2 and 3. Once there, it requests the path 2 resource. If granted, it will progress down path 2 and release path 3 when it is no longer occupying that space. The process is repeated at the intersection of paths 1 and 2, and again at paths 1 and 9. This strategy allows robot 2 to exit at any time other than the brief period when robot 1 is crossing the intersection of paths 1 and 2. Less time is spent waiting and efficiency improves.
On the other hand, this strategy ignores the overall goal of each progressive reservation. It's easy to imagine deadlocks and various other blocking situations that don't have obvious general solutions. Who should yield when n robots converge on an n-way intersection if you want to maximize efficiency? There's no easy answer. Rolling random numbers for priority can help resolve deadlocks, but it won't maximize efficiency.
3. Active Management / Resource Scheduling / Bulk Reservation
There are two situations where this could be useful. The first is scheduling multiple resources at a single future point in time. Suppose your system has many individual actors 'A' each using a small amount of the resource and a single actor 'B' that occasionally requires a large allotment of resources. The A actors have no trouble acquiring their resources, because they only need small amounts. But there are never enough available resources for B's request to get fulfilled. The resource manager could respond with, "I can't give that to you now, but I will start reserving them for you and let you know when I have them."
The second is scheduling a series of resources across a sequence of time slots. This is along the lines of the flight plan model. However, with this implementation if there are any conflicts *expected* along the way the entire plan is rejected. I suppose this could be useful when resource allocation is very predictable. (i.e. Once a roller coaster trains starts down the initial hill you can pretty accurately predict where it will be on the track at any given time in the next minute. It would be silly to start another train on a crossing track thinking one of them might stop to disembark a passenger, thus avoiding a collision.)
4. Active Management / Resource Scheduling / Progressive Reservation
This is also along the lines of the flight plan model. In the robot example, each path is scheduled based on the expected route, travel speed, etc. But the path isn't allocated until the robot is ready to enter that path. This is different than #2. Here the resource manager has the information required to predict and resolve potential conflict in the most efficient way. It's also different than #3 in that conflict resolution is postponed until the conflict is immenent. I could see this being useful in a system where an actor's resource requirements in the near future are not well defined.
For example, suppose the robot system also has a shelf-stocking robot. When this robot receives a "parts bin low" message from an assembly robot, it retrieves parts from the warehouse and refills the parts bin on the shelf. This robot could get one message an hour, or it could get a bunch of refill requests before it's had a chance to fill the first one. The path can't be predicted accurately because it is subject to being changed at any time. You don't want to deny access to a resource based on future expectations unless you're reasonable certain that future expectation will really occur.
I think this would be the most complex of the four active management solutions.
5-8. Family-Style Management solutions
It's too late for me to think through these combinations. Others are more than welcome to comment if so inclined.
My gut feeling is all of these solutions are more complex and more involved than the active manager solutions. The problem with putting too much smarts in systems with many concurrent actors is you're running the risk of creating undiscovered emergent behaviors. Emergent behaviors are very cool in reseach and hobbyist environments. Those investing in industrial manufacturing systems are decidedly less excited about them. I haven't yet had a customer ask me to build them a system with emergent behaviors. (Keeping my fingers crossed...)
I think I would only implement this kind of solution if there were technical reasons an active manager solution was not viable.
