I'm taking an introductory AI class this semester at
RPI. In today's class (class number three of the semester), we have just gotten to the point of talking about some of the different approaches to problem solving in AI. Now, this class is structured around the idea of learning to build a
rational agent. Therefore, we focused today on developing a goal-based problem solver.
A goal-based agent is designed around the concept of "states". The current position of the agent in its environment, all observable attributes of the environment, etc. comprise the agent's "current state". Every time the agent performsa an action (or any other agents or environmental bodies perform an action in a non-static environment), a new state is essentially created. We work under the assumption (for now, anyway) that all possible states are known. In fact, we work under several assumptions when creating a simple problem solver. We assume that our environment is:
- Static - unchanging except when the agent affects it
- Observable - there are no unknown or unaccounted for variables
- Deterministic - again, we either know all possible states or can at least calculate/predict with complete accuracy the state after a given set of actions
Now, with these assumptions in place, a goal-based agent needs four thing to solve a problem:
- An initial state
- A set of possible states (or a way to calculate them)
- A set of possible actions
- A goal state
- A metric by which to measure solution desirability, so as to be able to find the "best" solution
This is a fascinating concept to me, mainly because the more I think about it, the more I realize that this is essentially what human brains do a lot of the time. Consider a board game such as chess, checkers, or Stratego. A state consists of the current arrangement of the pieces on the game board. The set of states is quite large, though not infinite, and consists of every possible arrangement of every piece. The sets of possible actions are different for each game and are defined by the various sets of rules, but in general consist of moving the various pieces in different directions, capturing pieces, etc. And of course the goal state consists of either eliminating the opponent from the board (checkers), leaving the opponent with no possible moves while the King piece is in imminent danger (chess), or capturing the opponent's flag. The desirability metric is generally considered to be how few moves the solution takes, though this may be replaced by how enjoyable the game was, etc. This item is far more subjective than the others.
Another example is road travel. You want to get from your house to someone else's. The various states may be roadways, cities, buildings, etc., depending on how you frame it. Your actions may involve going straight, turning, slowing down, increasing speed, etc., depending on what you designate as states and how detailed you want to get here. Your initial state is your house and your goal state is your destination. Your desirability metric can be time, distance, road quality, number of tolls, etc.
This type of model can be applied to a huge number of scenarios and applications. It is only one part of a much larger set of skills that a brain has, but it is certainly a good place to start.
I think I am going to begin withby writing this goal-based agent. This will probably extend to a utility-based agent, which I will probably write another post about down the line (study ahead
here), but that change shouldn't be too hard to make later. For now I need to devise a solid general purpose algorithm and a couple of extendable classes to go with it.
