Revamp Role Assignment

[JNeiger]

I wanted to get some feedback on this that won't get deleted in slack.

I want to implement the priority/required attributes for roles that accurately are inherited in the composite behaviors. This is part of #1334

Priority

Priority is going to be swapped to an enum (High, Medium, Low, Idle). Priority will be used to decide which subbehavior to fill first within the current composite behavior.

High priority will be used for the bare minimum subbehaviors to complete the current composite behavior. For adaptive, the Capture/Pass/Shot will be High priority. For basic, Capture/Shot will be High. For the restart where we move multiple receivers, only the pass will be high.

Medium priority will be for extra passing options mostly. For two side attack, the moves before deciding to pass/shot will be medium. For the restart with multiple receivers, the others will be Medium.

Low priority will be for non essential robots and ones who are just getting setup in good positions for missed/lost balls. For adaptive, the midfielders will be low as well as the defence. For basic, the markers/defence. We don't have any plays that have this yet, but there may be a play in which the receiver misses the ball a lot, we can place a low priority robot in the location to optimally get the ball when the play fails.

Idle priority will only be used for formation stuff. I want to make sure it's a much lower priority then everything.

For large trees of these behaviors, it's difficult to "chain" a nonequal amount of these priorities together when comparing the priorities at the leafs of the tree. I'm thinking about doing an exponential weight to the system. The filter will do an weighted average from base of the tree down to the leafs. alpha will be some config which allows us to configure how much to weight the lowest level skills/tactics priorities versus high level play priorities.

For a play with two subbehaviors, A and B with sub-subbehaviors AA and BB respectively, the following chart states the combination of priorities. HH in the A/AA row means that A is High priority, AA has High priority. HL means that A is High while AA is Low. The value in the table at the intersection states which leaf should be filled first if only one robot is available. Basically given the two options, which one has a higher combined priority. Note that *L is always lower than *H. This is what I think the relationship should look like.

	A/AA
	HH	HM	HL	MH	MM	ML	LH	LM	LL
B/BB	HH	Equal	B/BB	B/BB	B/BB	B/BB	B/BB	B/BB	B/BB	B/BB	B/BB
HM	A/AA	Equal	B/BB	B/BB	B/BB	B/BB	B/BB	B/BB	B/BB	B/BB	B/BB
HL	A/AA	A/AA	Equal	A/AA	A/AA	B/BB	A/AA	B/BB	B/BB	B/BB	B/BB	B/BB
MH	A/AA	A/AA	B/BB	Equal	B/BB	B/BB	B/BB	B/BB	B/BB	B/BB	B/BB	B/BB
MM	A/AA	A/AA	B/BB	A/AA	Equal	B/BB	B/BB	B/BB	B/BB	B/BB	B/BB	B/BB
ML	A/AA	A/AA	A/AA	A/AA	A/AA	Equal	A/AA	B/BB	B/BB	B/BB	B/BB	B/BB
LH	A/AA	A/AA	B/BB	A/AA	A/AA	B/BB	Equal	B/BB	B/BB	B/BB	B/BB	B/BB
LM	A/AA	A/AA	A/AA	A/AA	A/AA	A/AA	A/AA	Equal	B/BB	B/BB	B/BB	B/BB
LL	A/AA	A/AA	A/AA	A/AA	A/AA	A/AA	A/AA	A/AA	Equal	B/BB	B/BB	B/BB

Required

The required parameter will pre-select which leafs to try and fill first. If you walk from each leaf back up the tree, the level at which required is no longer set, is the "requirement level". Aka if a play had a subbehavior which was required, and that subbehavior had a required skill, the "requirement level" will be at the play level. But if the subbehavior was not required, but the skill still was, the "requirement level" will be at the subbehavior level. Any leafs with a "requirement level" of play will be filled. If they cannot be filled the play will be blacklisted and exit. If they are filled, the rest of the leafs will be filled based on "requirement level" working down the tree, from highest priority to lowest. If two leafs had the same requirement level, but are from different subbheaviors, the one with the higher priority will be filled first. Any non-filled leafs that have any nonzero requirement level at the end, will cause the subbehavior at the requirement level to be black listed and any robots partially assigned will be moved to other roles. This may result in a situation where there are not assigned robots (which default to formations roles) event though the play would support up to some amount more.

For example, a play has a required special passing subbehavior, a non required move subbehavior. The special passing subbehavior uses 3 robots, 1 required kicker, 1 required receiver, and a nonrequired receiver. Move is just a single robot. If there is 1 robot, it will blacklist the entire play. If there are 2 robots, they will be assigned to the required kicker and required receiver. If there are 3 robots, the 2 required roles will be filled and the third could be the more or the nonrequired receiver depending on priority. If there are 4 robots, all roles are filled.

For another example, a play has a nonrequired subbehavior and a non required move subbehavior. This nonrequired subbheavior is just a wrapper for that required special passing subbehavior from above. If there is 1 robot, the move will be filled since the nonrequired wrapper subbehavior will not be run since it won't have enough robots. For robot amounts 2-4, the same behavior is present.

[JNeiger]

I'm still in the thought process on the actual cost functions themselves. I'm thinking about doing either doing a weighted average again or just a simple sum. It should be fine either way since we are just comparing the robots against each other for a specific role so they all run the same cost function. It's just more so what matters more, the highest level cost function or the lowest. There is very few places this affects stuff at the current moment, but I want to plan for it since I'm already doing some stuff.

[oswinso]

Interesting... I've got a few questions (sorry if this is because I'm unfamiliar with the robocup codebase / terminology)

1. What does subbehavior refer to? Is this a "Is A" relationship? (two possible offensive strategies that are both possible), or a "Has A" relationship? (one touch has a pass and then a shoot)? I think the priority calculations are different depending on which case you are in. Also, I think for the "has a" relationship the cost function changes depending on whether it's a "parallel" relationship (with a distraction play I move two robots while I pass to a third) vs a "sequential" relationship (with a one - two play a robot passes, and then moves, then gets passed to)

2. What are some examples of situations where you perform a play but you don't have enough robots? Is this counting "having a robot" as having a robot that is close enough to the region of the play, or is this in terms of having robots that don't have other things to do right now? It seems like most plays would deal with robots that do have the ball, so what could cause the other robots to not be available?

3. This "requiring 1 robot for a passing subbehavior" thing means that the passing target becomes "selected" here when you do "dependency checking" right? Doesn't this mean that you will only have one robot to pass to, when theoretically all robots could become valid passing targets? I guess this also relates back to the previous question.

4. What do you mean by "comparing the robots against each other for a specific role"?

5. For the question on whether higher or lower priority is more important, what is the priority of the behavior relative to? I guess this question depends on the first question wrt the definition of subbehavior, but like are the priorities meant as a comparison wrt other alternatives? (oh i think I misread, the priority is for determining which "aspects" of a play are more important). In that case, doesn't it kind of overlap with the role of optional?

[JNeiger]

1. Our autonomy is basically a hierarchical statemachine. At the root we have what we call the play. A play can have as many subbehaviors as it wants. Each subbehavior can have as many subbehaviors as they want. This continues down to the leaves of the trees which are what we call skills (They are still subbehaviors, we just gave them a special name). A play, for example, may have a pass subbehavior and a move skill. The pass subbehavior will then have a kick and move skill. Not all subbehaviors exist in every state. After the kick happens for a pass, the kicker subbehavior dissapears. The subbehaviors exist only for the states they are used. To be explicit, the cost functions will never be run and the subbehavior will not be filled unless the behavior is actively being used. With that being said, is your concern about the cost function changing still applicable? I'm not sure I fully understand your concern.

2. This is specifically that when we run robots and something breaks, we have to take the robot off the field. Sometimes we will play an entire game with 5, or even 4 robots instead of 6 due to mechanical or electrical issues. The play being run will have access to all the robots on the field so the only constraints are structural in the code. Specially, you don't want to be trying to pass if you don't have enough robots to do the recieving, you'll just get stuck in the statemachines. So we have this notion of being required to describe these situations. We will blacklist a play so it is not run again and then choose a different one. In this specific example we would choose one that always shoots if there aren't enough robots to do a pass.

3. Code wise we choose to pass to points, not robots. This is a specific distinction because we don't really care where robots are from a strategic point of view, we really just want to pass into open areas in the field. Additionally, this piece of role assignment is assuming that the play or autonomy has already decided that a specific location is the best pass. The strategy is already done, its now time to do the execution and select which robot should move to that point for the pass. Given a setup of robots on the field, which ones should be chosen to do this action.

4. Right now we use a hungarian algorithm to do task assignment. Each skill has a cost function which, given a robot, spits out how "expensive" it is for that robot to complete a specific skill. To select the best robot for a role, you find the lowest cost for that skill. Since each robot is running the same function, the relative scores are what matters, not the absolute scores. Given the relative costs for each robot to fill each role and the relative priorities between the roles, we can figure out which roles should be filled by which robots to produce the assignments we want. I'm thinking of swapping from the hungarian to something more greedy since the plays will be only using a few robots, but it's very easy to play with and I want to see the behavior irl before settling on one.

5. It does overlap a little bit. The priorities are there moreso for the non-critical roles of a play. It's very important to be able to influence which supporting members are more important and which are less as if you do not have all 6 robots available, you want to be able to say fill this role first. I may shift the definitions of High/Medium/Low around a little to make sure there is better distribution between them. I just want to make sure they are very well defined such that they are used consistently across subbehaviors

[oswinso]

Ok, so I've looked at a few examples of subbehaviours and I think I have a better understanding now. I still have a few questions about the whole concept of priorities though.

My current understanding of priorities is that this is only used in the case where you don't have access to all robots because of electrical / mechanical issues, and thus need to weigh between which subbehaviours are the "most essential" if not all robots work. Is this understanding correct?

[JNeiger]

Yep, that's the idea

[oswinso]

Ah, okay. So I guess I've misunderstood this then. I initially thought priorities were meant for use as like a general purpose "cost function"-ish thing. nvm then. I guess this is more of a situation analysis thing then?

[JNeiger]

I gotcha, it's not crazy clear. This is more so for formations. I needed to add in an extremely low priority subbehavior for everything and make it so things with the same priority/subbehavior are filled based on cost function not order in the list. If a play steals a robot and it's the first one added, the old version will fill it and move another formation robot into that subbehavior instead of leaving it empty

[kylestach]

@liquidmetal9015 @tjones320 @HussainGynai - it would be great to get opinions from y'all on this considering you will be the ones with the most experience in plays (@oswinso, the door is always open for you to join robocup, though :wink:)

[tjones320]

Alright, so I think I agree with the logic. I don't see an obvious flaw with this in regards to doing composite behaviors and behavior relations (I take that what you mean by skill and subbehavior). I would like to say that high priority should only be a task that directly interacts with the ball. Following that, I think the medium priority should be things that could possibly interact with the ball following a quick turn of events (side passes and goalie would be examples). Low priority should probably be things essential to the overarching strategy, but probably aren't going to interact with the ball (eg. winger wall when we are on offense). I agree formations should be the idle behaviors.

Hmm, this is very interesting, while we are going to have to refactor a few things to make this transition smooth I think this will help with formalizing how we prioritize things.

I think we also talked about at some point adding subbehaviors that can call only one instance of during any play (not completely related but wanted your thoughts). This way we can mandate that only one robot will be attempting to move on capture the ball if we have an idle behavior in the formation also wanting to capture.

[tjones320]

Also sorry for the late response

[JNeiger]

I like that better in terms of priority descriptions. It flows much better.

@instanced subbehaviors: I'm optimistically cautious, there's a lot of low level decisions that have to be made behavior wise, but I can see it helping if you want a standard defense or something. We should definitely try to design it with situations in mind to make sure it's still even a major problem

[Jason27chan]

I like the clarity of this priority structure more than whatever we have currently