Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Two types of GOAP AI and Problems I'm facing

Discussion in 'Scripting' started by John_Leorid, Jan 16, 2019.

  1. John_Leorid

    John_Leorid

    Joined:
    Nov 5, 2012
    Posts:
    646
    For anyone who has written a Goal oriented Action Planning AI, or atleast know what it is and how it works, I just can't get around the GOTO Action.

    There are 2 ways of planning, forward and backward:
    To explain those, lets start with a simple example:
    We want our agent to take cover behind a coverObject - so the graph should be
    FindCover --> GoTo(cover Position) --> TakeCover
    FindCover searches for a suitable cover and it's position
    GoTo moves the agent to a position
    TakeCover is equal to Couching down

    Reverse:
    From Goal to start, only accepting actions which effects fulfill preconditions:
    As we know, we have a CurrentState and GoalPreconditions, the start state contains all information, which are present, such as
    "hasWeapon - true" "hasCover - false" "isCouching - false" "isAtPosition - (0,0,0)"

    GoalPreconditions are: "isCouching - true" "hasCover - true"

    "isCouching - true" is fulfilled by TakeCover - so first one is TakeCover, but it has a precondition "hasCover - true"
    FindCover Effects fulfill "hasCover" but there is a precondition "isAtPosition(1,0,1)" where (1,0,1) is the position of the cover
    GoTo has already fulfilled preconditions "isCouching-false" and it's effect reads the position value out of the preconditions and sets "isAtPosition" to (1,0,1) - planning finished plan is:
    GoTo --> FindCover --> TakeCover

    This works great, until the cover is exposed and I need the agent to swich cover, now the world state is:
    "hasWeapon - true" "hasCover - false" "isCouching - true" "isAtPosition - (1,0,1)"
    Now the first Action the Planner finds is FindCover, which fulfills "hasCover - true" and a precondition "isAtPosition - (2,0,2)" where (2,0,2) is the position of a valid cover
    then GoTo "isAtPosition - (2,0,2)" with it's unfulfilled precondition "isCouching - false"
    So the planner adds LeaveCover which sets "isCouching - false" --> planning failed because the plan is:
    LeaveCover --> GoTo(2,0,2) --> FindCover

    and at the last state, we are not couching, because we were not expecting that any further action would lead the agent to stand up. Now we cannot find a plan with the given actions and the goal, even it would be possible by just adding TakeCover at the end, but the planner does not know that, and fails.
    Any idea how to solve this?

    Forward:
    Start with the world state and try to reach the goal. Only add Actions, which preconditions are fulfulled and try to find a branch where the goal preconditions are fulfilled.

    As we find new Actions, which preconditions are met, a copy of the current state gets updated. When the current state contains the GoalPreconditions, the plan is finished.
    GoTo has a cost, based on the path distance, so I need it to be an Action. Because when I add the GoTo Action, I do not know at what position I want to be, because the "isAtPosition" parameter is a precondition of the following action, and I don't know what will be the next action to add.
    Now how do I get the position from FindCover to the GoTo Action?

    I searched the internet for a week and didn't find a solution to the problems, hopfully the community can point me in the right direction.
     
  2. TonyLi

    TonyLi

    Joined:
    Apr 10, 2012
    Posts:
    12,670
    Games that use GOAP typically do a reverse search, and they'll frequently offload trivial behavior to an FSM or simpler logic. This could include crouching. Your implementation for Goto could make sure the player is standing before starting to move. This way the planner doesn't need to worry about it. Otherwise you'll need to add a StandUp action that the planner can use, which adds more work to the planner.

    Jeff Orkin's paper Three States and a Plan: The A.I. of F.E.A.R. remains a good model to follow if you're intent on using GOAP.
     
  3. John_Leorid

    John_Leorid

    Joined:
    Nov 5, 2012
    Posts:
    646
    Yep, I read this paper 5 or 6 times I think ^^

    Well, the agent does stand up, but in reverse search he does not know that he will be standing, when he reaches the cover. Have a look at the graph, in the order the algorithm chooses the Actions:

    FindCover <-- GoToCover <-- StandUp

    this is wrong, because he doesn't "TakeCover" at the beginning of the search / at the end of the plan, because he is already couching when he starts the planning. When he does have a rifle, he won't get a new rifle in order to shoot at the player. But if he drops the rifle to climb up a ladder and then tries to shoot the player, he does not have a rifle anymore.
    The correct Plan should look like this:

    TakeCover <-- FindCover <-- GoToCover <-- StandUp

    TakeCover at the beginning does only exist because he stands up at the end, if he wouldn't have to stand up, he wouldn't need to TakeCover at the beginning. So how do I get the planner to add the TakeCover at the beginning of the plan, because he stands up at the end? In practical use this gets way more complex, because "takeCover" could be everything and could have new preconditions and effects which could then affect the whole plan.
    For example if he would need a shovel to TakeCover the plan would look like this:

    TakeCover <-- FindCover <-- GoToCover <-- PickShovel <-- GoToShovel <-- StandUp

    Two Actions added somewhere within the path, also the effects could make some actions unnecessary...
     
  4. TonyLi

    TonyLi

    Joined:
    Apr 10, 2012
    Posts:
    12,670
    I'm suggesting that you make the planning less granular.

    Planning is more expensive than hard-coded behavior. A plan's actions are abstract, but each action is tied to some concrete behavior in the game world. For example, the Goto action is tied to some behavior that moves the agent's GameObject, typically with animation, and often defined in an FSM. Why do you need a StandUp action? Just make StandUp part of the behavior FSM. Something like:

    Goto:
    Code (text):
    1. [START] --(crouching?)--> [Stand] --> [Animate & Move] --(arrived?)--> [Stop]
    2.    |                                        ^
    3.    `----------------------------------------'
    This way, your planner can assume that Goto knows how to handle standing up without having to plan it in such detail.

    You could even go so far as to add:

    --> [Stop] --(hasCover?)--> [Crouch]

    This way your planner doesn't need to know about crouching at all, which means it doesn't need to burn CPU cycles figuring out how to crouch and uncrouch. Of course, it also means that agents will always automatically crouch when they stop in cover, which may or may not be the behavior you want.

    I realize my reply skirts around the answer you're asking for. But it's worth considering.

    Otherwise you may need to add more actions and preconditions, and your planner will need to crank through a much larger search space. However, in this case, I think you can adjust the definitions of your current actions.

    Shouldn't the plan be this?

    TakeCover <-- GoToCover <-- StandUp <-- FindCover

    I'll recap my understanding of your actions:
    • The goal is to be in the state (hasCover, isCrouching, ?atDestination). (?atDestination means we don't care.)
    • TakeCover: (hasCover, !isCrouching, ?atDestination) --> (hasCover, isCrouching, ?atDestination)
    • GoToCover: (!hasCover, !isCrouching, !atDestination) --> (hasCover, !isCrouching, atDestination)
    • StandUp: (?hasCover, isCrouching, ?atDestination) --> (?hasCover, !isCrouching, ?atDestination)
    • FindCover: (!hasCover, ?isCrouching, ?atDestination) --> (!hasCover, ?isCrouching, !atDestination)
    • The start state is (!hasCover, isCrouching, atDestination)
    If that's correct, then just search back from the goal state: (hasCover, isCrouching, ?atDestination). One path (the optimal one) could be:
    • Check TakeCover: (hasCover, isCrouching, ?atDestination) <-- (hasCover, !isCrouching, ?atDestination)
      This doesn't yet match the start state, so...
    • Check GoToCover: (hasCover, !isCrouching, atDestination) <-- (!hasCover, !isCrouching, !atDestination)
      This doesn't yet match the start state so...
    • Check StandUp: (!hasCover, !isCrouching, !atDestination) <-- (!hasCover, isCrouching, !atDestination)
      This doesn't yet match the start state so...
    • Check FindCover: (!hasCover, isCrouching, !atDestination) <-- (!hasCover, isCrouching, atDestination)
      This matches the start state, so we're done.
     
    Last edited: Jan 17, 2019
    eterlan likes this.
  5. John_Leorid

    John_Leorid

    Joined:
    Nov 5, 2012
    Posts:
    646
    More or less, just that the preconditions and effects (some call them postconditions) don't contain the full state.

    Goal: Pre: HasCover, IsCouching
    GoTo: Pre: !HasCover, !IsCouching Eff: IsAtPosition(any wanted position listed in the current precondition set)
    TakeCover: Pre: HasCover Eff: IsCouching
    FindCover: Pre: IsAtPosition Eff: HasCover
    StandUp: Pre: IsCouching Eff: !IsCouching

    Initial State1 (when the agent has no cover): !HasCover, !IsCouching, IsAtPosition(0,0,0)
    Initial State2 (when the agent has cover, but the cover is no longer valid): !HasCover, IsCouching, IsAtPosition(1,0,1)

    As you can see, stand up is not the problem here.


    Also I don't mind if the planning takes up to 0.5f seconds because thinking in real life takes time too - the whole planner is threaded, so it won't cause lag anyways.
    And I prefer GOAP over Statemachines and Behaviour Trees, because I want somehow complex behaviours and well, except for this particular problem, everything already works fine. Agents run around, taking cover, shooting at the player - just when they have to switch from cover to cover, they don't find a plan to do so. And the problem is way more complex than I thought, because in any plan, an action could affect what is already planned and this should be possible, because the Agent COULD switch from cover to cover with all the actions he has, but the planner is not good enough to find the plan.
     
    Last edited: Jan 17, 2019
  6. TonyLi

    TonyLi

    Joined:
    Apr 10, 2012
    Posts:
    12,670
    BTW, I included the whole state vector in my previous reply to remove ambiguity about what the preconditions and effects need to be. Try doing the same; maybe it will give you an idea.

    I don't understand your issue. The goal state requires isCrouching. One of the search paths should always end up being:

    [goal] <-- [TakeCover]

    because that's an action that satisfies the goal's preconditions. As you search back from [goal] to [TakeCover] to etc., TakeCover's preconditions (!isCrouching) will be true from the effects of GoTo.

    I'm not saying to replace GOAP, but to offload "autonomic" behaviors. In real life, when we touch a hot stove, we don't generate a plan to pull our hand away. A reflexive "state machine" does it automatically. Similarly, when we walk, we don't make a plan for how to raise and move each foot, even though we make a plan at a higher level about where to walk to. You may not mind if the planning takes up to 0.5f seconds, but keep in mind that in an action game agents may need to constantly replan. For example, while the agent is running to cover, an enemy might blow up the cover, or another agent may occupy the cover. In this case, the agent will need to generate a new plan. Just a suggestion. It's just a way to give you more CPU cycles to replan, to support more simultaneous agents, and to do other things such as line of sight checks, etc.
     
  7. John_Leorid

    John_Leorid

    Joined:
    Nov 5, 2012
    Posts:
    646
    The issue is simple:
    Preconditions that are fulfilled by the world state don't need actions to fulfill them. If I have full HP and I want to have full HP, I don't need to heal myself to get to the state. And if I have to heal myself because I do not have full HP, but I am standing right at the healing machine, I do not have to go to that machine to use it, because I am already there.
    Now if I want to heal myself I just have to run the action "UseHealMachine" instead of "GoTo(healMachine)" "UseHealMachine". Now to the couching problem:
    At the start, the Agent is couching already, so he don't have to run "TakeCover" - but later in the planning, we have to "GoTo" the cover and so we have to "StandUp".
    So the planner does not add the "TakeCover" because he assumes that we can fulfill the goal without standing up at all - but later in the planning process this value gets overridden, so we can walk - and theres the problem. The value "couching" gets overridden and will never be set back to TRUE because that would only happen at the beginning of the search --> somewhere after the "goto" action.
     
  8. TonyLi

    TonyLi

    Joined:
    Apr 10, 2012
    Posts:
    12,670
    When you search back from the goal state (hasCover & isCrouching), the intermediate states are going to change isCrouching. So it doesn't matter what the start state is.
     
  9. John_Leorid

    John_Leorid

    Joined:
    Nov 5, 2012
    Posts:
    646
    Could you elaborate? I don't quite understand this. Why wouldn't the start state matter?

    If he "hasCover" and "!IsCouching" the plan is just
    "TakeCover" - - > done

    Because of the start state, he don't have to go anywhere, not search for a cover, just get back to couching to fulfill the goal.

    If the agent "hasAmmo" and "hasWeapon" there is no need to reload before shooting, because of the start state or am I getting this wrong?
    I thought thats exactly how GOAP works - we want a change in the world(state) so we create a plan that changes the world(state) as desired.
     
  10. TonyLi

    TonyLi

    Joined:
    Apr 10, 2012
    Posts:
    12,670
    Right. Your goal is a state, not an action. Maybe we're talking cross-purposes and saying the same thing to each other, but we'll get to a mutual understanding. :)

    ---

    Let's say the goal state is (hasCover, isCrouching).
    The start state is (hasCover, !isCrouching).

    • If you're doing a reverse search, you identify the set of actions that result in (hasCover, isCrouching). This set includes TakeCover, whose preconditions are (hasCover, !isCrouching).
    • This matches the start state, so you're done. Plan: TakeCover.

    ---

    Let's say the goal state is (hasCover, isCrouching).
    The start state is (!hasCover, isCrouching).

    • You identify the set of actions that result in (hasCover, isCrouching). This set includes TakeCover, whose preconditions are (hasCover, !isCrouching).
    • Now you need to plan back from (hasCover, !isCrouching). The set of actions includes GoTo, whose preconditions are (!hasCover, !isCrouching).
    • Now you need to plan back from (!hasCover, !isCrouching). The set of actions includes StandUp, whose preconditions are (?hasCover, isCrouching).
    • This matches the start state, so you're done. Plan: StandUp -> GoTo -> TakeCover.
      (To keep it short, I omitted FindCover, which is more of the same.)
    At each step, the set of actions may include other actions, too. That's why you need a good heuristic to choose the most promising action when searching.

    What's not working about that?
     
  11. John_Leorid

    John_Leorid

    Joined:
    Nov 5, 2012
    Posts:
    646
    Well thats how I solved the couching Problem - by adding isCouching to the FindCover Action, but the theoretical problem does still exist.

    The plan
    StandUp, GotoCover, FindCover, TakeCover is a valid plan but the planner just creates nodes, which effects fulfill a precondition
    And TakeCover only fulfills "isCouching=true"
    At the initial state, isCouching is not a precondition, so the node will never be created
    The only precondition is "hasCover" because the agent is already couching but has no (valid) cover anymore.
    On a theoretical basis, could I improve the planning algorithm, so that the plan
    StandUp, GotoCover, FindCover, TakeCover
    Gets created even if TakeCover fulfills a precondition that is caused by the effect of StandUp?
    I just see that this could cause errors in future development, where plans are possible, but the planner does not find them.
    Fun fact - the forward planning would find the example plan, so I think they way my reverse planner works is wrong.
    I started to track all the worldFulfilled preconditions and check if any effect breakes them, but I got stuck there. I don't know what I should do with this information, restarting the whole planning causes a stack overflow because it happens over and over again with all possible actions at any node during planning..
    Any ideas? I've found nothing on google to this topic, maybe forward planning is the only correct way of finding every possible plan? Idk, I'm a bit lost with this problem, even my AI does what I want for now.
     
  12. TonyLi

    TonyLi

    Joined:
    Apr 10, 2012
    Posts:
    12,670
    That's why I suggested earlier that your world state may need more expressions. The goal state isn't isCrouching, it's (hasCover, isCrouching). When you search back from this, one possible action whose effects are isCrouching is TakeCover. Then you need to find a path that, when you unwind it, leads to (hasCover, !isCrouching) by the time it gets to TakeCover.
     
  13. John_Leorid

    John_Leorid

    Joined:
    Nov 5, 2012
    Posts:
    646
    If I use all goal-preconditions for the planning, including the already fulfilled ones, some goals can't be archived. Example: Shoot
    In order to shoot, I have a precondition "hasWeapon" but no action that would fulfill this, it just gets set by a sensor, if the agent has no weapon, execute melee attack.
    But I think this could be a solution maybe.
    Adding optional nodes IF a world fulfilled precondition becomes unfulfilled because of an effect..
    I can't be the only one struggling with this? Strange that I found nothing related to this problem with reverse-goap..
    Thanks for your time TonyLi - now I'll have to test some of these ideas to see what works :)
     
  14. Sanginius

    Sanginius

    Joined:
    Apr 21, 2013
    Posts:
    14
    Maybe you need to have some additional decision making for your agent to set the goals. For example, if the sensor would write something to the blackboard like "isSeenByEnemy = true", you could set the goal to "GoAndFindWeaponToShootWith", because attacking in melee could cause to much damage when he has to run to the enemy first.

    You most likely have to tackle all eventualities as goals and actions to avoid problems like "shoot" can never be achieved.
     
  15. John_Leorid

    John_Leorid

    Joined:
    Nov 5, 2012
    Posts:
    646
    The goal superclass has an abstract function
    float GetPriority()

    Where I can track the player position, distance to the enemy, ammunition, rotations, other enemies and so on and return a priority value. Then from highest to lowest priority, it tries to create a plan.

    I think I just need more goals and a more aggressive AI, they are hiding to much and don't do anything else beside finding some cover and shooting from that cover.. pretty boring opponents atm. Maybe realistic, maybe hard to kill but still extremly boring in gameplay.
     
    eelstork likes this.