2
$\begingroup$

I have two questions regarding a paragraph about table-driven agent programs from Modern Approach to Artificial Intelligence 3rd Edition.

  1. "Let $\mathbb{P}$ be the set of possible percepts and let T be the lifetime of the agent (the total number of percepts it will receive). The lookup table will contain $\sum\limits_{t=1}^T |\mathbb{P}|^t$ entries. Consider the automated taxi: the visual input from a single camera comes in at a rate of roughly 27 megabytes per second (30 frames per second, 640 x 480 pixels with 24 bits of color information). This gives a lookup table with over $10^{250,000,000,000}$ entries for an hour's driving."

Can someone please show me the step-by-step derivation of the total number of entries based on the given information to arrive at a value over $10^{250,000,000,000}$? I did my math in the following way, but clearly there is something wrong:


$\mathbb{P} = 2^{640x480x24}$, since per frame there are 24x640x480 bits, and each frame is a percept. (I'm not entirely sure that my claim that a frame is a percept is accurate.)

Then, the total number of entries (S) for an hour is as follows:

S = $\sum\limits_{t=1}^{T=3600x30} (2^{640x480x24})^{t}$.

That series can be converted into the following closed form:

S = $\frac{\mathbb{P}^{T+1} - \mathbb{P}}{\mathbb{P} - 1}$.

If I plug in $2^{640x480x24}$ for $\mathbb{P}$, I end up with essentially $10^{240,000,000,000}$ and NOT over $10^{250,000,000,000}$. What am I doing wrong?


  1. "The daunting size of these tables (the number of atoms in the observable universe is less than $10^{80}$) means that (a)...(d) even if the environment is simple enough to yield a feasible table size, the designer still has no guidance about how to fill in the table entries." I'm not exactly sure what guidance the designer needs. I'm assuming that the agent function already exists. In that case, all the designer needs to do in constructing their table entries is look up the corresponding action with each percept sequence.

I thank everyone in advance for taking the time to read this and help me out =)!

$\endgroup$
1
$\begingroup$

You are asking two questions. The answer to your first question is very simple – the authors used a figure of speech when they wrote over $10^{250,000,000,000}$. What they meant was roughly $10^{250,000,000,000}$. In any case, the exact number isn't important – it is just supposed to be an impressively large number rather than an exact estimate. For this reason I didn't bother to check your calculation. It is possible that your calculation is right, and the authors either got it wrong or preferred writing a round number rather than a more pedantic one; but it doesn't really matter.

As to your second question, probably the authors meant what they wrote – even when the table is small, it's not clear what its contents should be! For example, consider a speech recognition program. It is possible to convert the high dimensional raw input into a low dimensional representation using a vocoder. However, it is still difficult to parse what the person is saying, for many reasons. (This is just a guess as to what they meant; you aren't supplying enough context.)

If you want to understand the authors' comments mentioned in your second question better, I suggest you keep reading the book. The authors probably offer solutions to these problems, and these solutions will highlight the problems themselves.

$\endgroup$
  • $\begingroup$ I understand the solution to my first question. As for the second question, I think I do, but I want to make sure what I have in mind is aligned with what you meant: In your example, the agent function maps already parsed speech to meaning. However, trying to create a table entry from the low dimensional representation to the meaning is not all that straightforward since a particular low dimensional representation can possible be parsed in more than one way: "We ate a cake with forks" can be interpreted as a cake that was eaten by forks or a cake of forks. Then, the designer would need help. $\endgroup$ – Coder47 Sep 11 '15 at 18:01
  • $\begingroup$ In fact, I don't really know what the authors meant due to lack of context. It's also not very important: after all, this is not the bible. The goal of the authors' remarks was to explain the problems whose solutions occupy the rest of the book. If you do read the rest of the book, these motivating remarks would become less important. $\endgroup$ – Yuval Filmus Sep 11 '15 at 20:08
  • $\begingroup$ Understood. It just bugs me when I don't completely understand something. It's sort of similar to the question you helped answer: math.stackexchange.com/questions/44704/…. I'm going to practice the technique of ignoring specifications for the purpose/goal of the author if I'm getting stuck (saving the specifications for later), since the authors' purpose seems to be the most important thing and would avoid me a lot of headache. $\endgroup$ – Coder47 Sep 11 '15 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.