For each term \(t\), let’s store all the documents containing \(t\). We identify each doc by DocID.

postings list

a “postings list” datastructure is a variable-length list which is appended to with “postings”. In this way, we can store a “posting” for every DocID with the index we encounter.

For instance, this could be a linked list.

Although: we generally want to sort our postings list by documentID for ease of indexing.

irrational numbers are real numbers that are not rational numbers.

Formally:

\begin{equation} \mathbb{C} = \mathbb{R} \backslash \mathbb{Q} \end{equation}

where, \(\backslash\) is subtracting two sets.

Motivation

Large crowd navigation with sudden changes: unlikely events are out of likely sample. So, we want to bring in another distribution based on importance and not likelyness.

Goals

• retains DESPOT garantees
• outperforms DESPOT and POMCP

DESPOT with Importance Sampling

1. take our initial belief
2. sample trajectories according to Importance Sampling distribution
3. calculate values of those states
4. obtain value estimate based on weighted average of the values

Importance Sampling of trajectories

We define an importance distribution of some trajectory \(\xi\):