curds01
commented
4 years ago @douglasbandeiraivo This is the initial design document I promised. @saruvora I would also appreciate any additional thoughts you might have.
Open curds01 opened 4 years ago
curds01
commented
4 years ago @douglasbandeiraivo This is the initial design document I promised. @saruvora I would also appreciate any additional thoughts you might have.
douglasbandeiraivo
commented
4 years ago Very good, @curds01. It's not easy to implement a so general solution.
As I understood, the filtering/selection of the leader would be executed once the agent entered the state "following agent". To change the leader, the follower should change to another state of "following agent"?
curds01
commented
4 years ago @douglasbandeiraivo
You are correct. If you go for a behavior where the leader is selected by entering a state, the simplest way to select a new leader would be to enter a new (or even the same state). That would make it a matter of defining the transition that would cause him to change leaders.
Currently, I'm working on implementing an initial attempt at a following behavior (noting that there are many, many variations). I figure, if I get one implemented, I can evaluate how useful it is and then extend it for other behaviors.
douglasbandeiraivo
commented
4 years ago @curds01 ok.
saruvora
commented
4 years ago @curds01 Hi sorry for the late reply was caught up on another work, will explore it and give you some feedback. Thank you
A recent request has come up to enable the behavior in which agents follow agents. This is obviously a desirable behavior, but there are a host of decisions to be made. The purpose of this issue is to track the discussion/options so we can prioritize efforts toward enabling following behavior. As comments are added below, this main data will be edited to reflect the best/most current state of the discussion.
Behavior design
To design this in any meaningful way, we have to have a clear definition of the behavior we're going for. This can be determined by the answers to the following questions (and possibly others):
Below, I've offered some thoughts on each of the questions.
What causes an agent to start following another agent?
This topic is unique in that a) it is the simplest and b) most coupled with implementation details. It would be easy to say that an agent begins following another agent when it enters a "following state" (however that is encoded -- see implementation details below). This is fundamental to the design of Menge. Clearly, a change from not following an agent to following an agent is exactly what is encoded in the Behavior Finite State Machine (BFSM). So, the answer to this question can be answered as: The trigger that causes an agent to start following another agent is any transition that causes that agent to change states.
Under what circumstances is following possible?
For one agent to follow a "leader" agent, must that leader agent be visible? It is possible to give the follower "oracular" knowledge of the leading agent so that even if the agent is not visible, the following agent can still know its position and make progress towards it (think of Pacman pursuing ghosts).
Alternatively, some human behaviors may only make sense based on the follower being able to actually observe the follower.
What does it mean to follow?
Here are several potential answers:
Walk to the current position
This is conceptually the simplest. In principle, the leading agent defines an instantaneous goal for the following agent. A preferred velocity is computed to that position and the simulation step is taken. If the leading agent is moving significantly, the following agent will take a more delayed path to reaching the agent. (Incidentally, the PR #138 would be a prerequisite for this type of behavior.)
Walk to where the agent is going to be
This type of behavior has the potential of permitting the following agent to reach the leading agent more quickly. However, it depends significantly on the ability to anticipate the leading agent's trajectory. If the leading agent is taking an arbitrary path through a maze, this anticipation will be either a) exceptionally flawed, b) only computed over a small, conservative window of time, or c) have access to the leading agents path planning apparatus so that can be considered.
Furthermore, in the general case, finding an optimal path from the follower's current position to some future optial intersection point can't be solved trivially (and may not be solvable at all).
Maintain a fixed spatial relationship
This is akin to "walk to the current position", but instead of the agent's actual position, it would be some point relative to the agent's position. The relative position may be in the leading agent's frame (such that as it turns, the following agent has to traverse large circular arcs to maintain its position -- think "walk three feet behind as an example). The relative position may also be expressed in the world frame (or, more painfully, some arbitrary other frame). It is more difficult to think of a real-world example that would be recreated with this formation definition.
How does the leading agent get selected?
One way to think about the answer to this is to consider every agent in the simulation as a viable candidate and then provide filter criteria (to eliminate some agents from candidacy) and selection criteria (to select from remaining candidates). Note properties may be used in either filter or selection criteria.
Filter criteria
Possible examples of selection criteria:
Selecton criteria
Failed selection
Any combination of filter/selection criteria that cannot guarantee producing a leading agent must be able to define a fallback behavior. Relaxed filters? Alternate selection mechanism? Movement out of the state and into a new, non-following state?
What causes a following agent to stop following and what happens as a result?
If we associate the agent-following-another behavior with a particular state, than any transition logic available to Menge is one way to cause an agent to stop following. Simply transitioning to another, non-agent-following state is sufficient.
However, there are other circumstances in which we need to consider ending the leader-follower relationship:
In other words, the follower agent could lose its follower and that could be wholly unrelated to the follower's state (which is what BFSM transitions are predicated on) and be wholly related to the state of the leader.
Potentially, the follower might stay in its "follower" state but look for a new agent to follow. It might get pushed into an alternate state (and that state may or not have its own following behavior, unrelated to the previous state the agent just left).
Implementation Considerations
There is no straightforward implementation for a "following agent" behavior. As with all things in Menge, there are usually multiple ways to solve the same problem given the richness of the Element architecture. Picking one implementation over another really comes down to identifying the target behavior and implementing in a "natural" or "low friction" mechanism (the more we contort Menge to add a feature, the less likely that feature is being implemented "correctly"). However, it may well be that Menge will have to be extended in some fundamental ways to introduce meaningful following behaviors.
It is also reasonable to implement several different versions of following behavior with different properties such that they can be used as appropriate. No single, monolithic solution is required if it turns out that different behaviors are more naturally captured with different mechanisms.
For now, this isn't going to include any specific implementation details until it's clear what kind of behaviors we would want.