Planning
You have a world that has some state, and the agents can do actions that affect that state. Now, you can think of the world state as a node, and the actions are the links.
You would not have a graph with all the possible game states. Instead you should express your actions as pre-conditions (needed to be able to do the action) effects (that you should be able to apply to the world state to be able to compute the new state) and some cost (in time or resources).
Then the goals are predicates you should be able to check about the world state (for a given world state, the goal has been met or not). As you can see, the actions have pre-conditions that are basically the same thing. This means that you can model the goal as an action (having the effect of "the AI wins").
What follows is planning. There are two approaches:
Forward Searching
The idea is that you need to find a path (a series of actions) that will take the current world state to a world state that satisfies the goals. You do this by pathfinding.
As you know, when pathfinding you can have a heuristic to provide priorities over the different branches you search... that heuristic could be a measurement of the progress towards a goal (you may expand this idea to include the risk of moving away from the goal, perhaps as an estimate of enemy treats).
Now, you can search the action space for a path that will lead you to the goal state. Or, perhaps you could just plan a few steps by finding the path that would take you closer to the goals in those steps, this way keeping the time dedicated to AI short.
Note: As I said above, you don't have a graph will all the possible states of the game. Instead you would generate the game states that the AI explores as it does it. If you give a look to the pseudo code for A* Search Algorithm or for Dijkstra's algorithm you'll see that you only need to persist the actions, not the states. This also allows you to search an infinite state machine.
Backtracking
Here you start with the goal, you attempt to do it as an action and you find you need to meet some condition first. Then you look at the other actions and see what actions may lead to that, etc... until you reach an action that can be performed right away (that is an action to which the current world state satisfies its pre-condition).
As you can see, this is also searching, except you start by the end. Backtracking works better with simple abstract scenarios, but it may not work for open ended games because reaching the goals may be too far away that it takes too long for the AI to start doing any actions.
Abstractions
The world representation that the AI sees doesn't need details. The idea is to move code away from the predicates. For example one possible action is to shoot an enemy; its pre-conditions would be to have a ranged weapon, with enough ammo, and for there to be a nearby visible enemy. You don't want to have to write in the predicate the logic to find nearby objects, line of sight checks, etc... This would be abstracted by the code that creates the world representation with which the AI works. A subsystem will then deal with the details of changing weapon, aiming and shooting.
Another thing you can do is to find interchangeable objects. If something can be done with object A or with object B to similar results, the AI doesn't need to be concerned with it. Instead a subsystem can deal with the details. For example in some combat video games the AI doesn't have the responsibility of choosing kick vs punch. Instead another subsystem can check the collision boxes, the damage of each option, and whatever or not they can be chained in a combo to decide what attack to do. The AI will then worry about being offensive or defensive, going for ranged attacks or close combat and predicting player moves to dodge, block or counter.
Another technique you can apply is to bookmark zones and choke points that are important to control. This will allow you to provide the AI with a discrete list of locations instead of having to deal with coordinates. Then a subsystem dealing with formation and pathfinding will decide exactly where to go.
Note on large maps
You will want to keep a structure that allows you to query nearby objects (this is useful for other things), using that structure you will be able to limit the representation of the world state used by the AI to the immediate surroundings of the objects it controls. This will keep the AI performance regardless of the size of the map.
Predicting other agents
Of course there are multiple agents in the game, and there is no way an agent will know what another agent will do (unless they share information). You can approach this by implementing game theory: the agent considers the possible moves the other agents may do and picks what’s best across all the possibilities.
In order to keep things simple you may consider making each agent predict what is best for each other agent according to your AI (similar to MinMax) but with only the information available to the agent doing the prediction.
To predict players, you can represent them as probabilities. To give value to those probabilities you can use the frequency with which the user does an action, is seen in a given location, or uses some item. For the locations you may want to annotate the frequency in the map. Since you are keeping your AI isolated, you would make a separate representation of each player for each AI agent.
Randomness
So far the AI is deterministic, therefore predictable…
A simple way to do is, is having using random to have the AI pick unnecessary actions or actions that nonetheless have some reward for the AI agents, or by taking a suboptimal approach to reach the goal. This may provide a more interesting gameplay, more replay value, and the benefits of the unnecessary action may help the AI to find alternative solutions when their plans fail.
