Author name cluster

Nan Rong

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

UAI Conference 2016 Conference Paper

MDPs with Unawareness in Robotics

Nan Rong
Joseph Y. Halpern
Ashutosh Saxena

while most actions result in the robot losing control and falling down. We formalize decision-making problems in robotics and automated control using continuous MDPs and actions that take place over continuous time intervals. We then approximate the continuous MDP using finer and finer discretizations. Doing this results in a family of systems, each of which has an extremely large action space, although only a few actions are “interesting”. We can view the decision maker as being unaware of which actions are “interesting”. We an model this using MDPUs, MDPs with unawareness, where the action space is much smaller. As we show, MDPUs can be used as a general framework for learning tasks in robotic problems. We prove results on the difficulty of learning a near-optimal policy in an an MDPU for a continuous task. We apply these ideas to the problem of having a humanoid robot learn on its own how to walk. Halpern, Rong, and Saxena [2010] (HRS from now on) defined MDPs with unawareness (MDPUs), where a decision-maker (DM) can be unaware of the actions in an MDP. In the robotics applications in which we are interested, we can think of the DM (e. g. , a humanoid robot) as being unaware of which actions are the useful actions, and thus can model what is going on using an MDPU.

Details

AAMAS Conference 2010 Conference Paper

Cooperative Equilibrium

Joseph Halpern
Nan Rong

We propose a new equilibrium concept, perfect cooperativeequilibrium (PCE), which may help explain players' behaviorin games where cooperation is observed in practice. We alsoconsider a few related equilibrium concepts that take intoaccount the degree of cooperation.

PDF

UAI Conference 2010 Conference Paper

MDPs with Unawareness

Joseph Y. Halpern
Nan Rong
Ashutosh Saxena

Markov decision processes (MDPs) are widely used for modeling decision-making problems in robotics, automated control, and economics. Traditional MDPs assume that the decision maker (DM) knows all states and actions. However, this may not be true in many situations of interest. We define a new framework, MDPs with unawareness (MDPUs) to deal with the possibilities that a DM may not be aware of all possible actions. We provide a complete characterization of when a DM can learn to play near-optimally in an MDPU, and give an algorithm that learns to play near-optimally when it is possible to do so, as efficiently as possible. In particular, we characterize when a near-optimal solution can be found in polynomial time.

Details

ICRA Conference 2008 Conference Paper

A point-based POMDP planner for target tracking

David Hsu
Wee Sun Lee
Nan Rong

Target tracking has two variants that are often studied independently with different approaches: target searching requires a robot to find a target initially not visible, and target following requires a robot to maintain visibility on a target initially visible. In this work, we use a partially observable Markov decision process (POMDP) to build a single model that unifies target searching and target following. The POMDP solution exhibits interesting tracking behaviors, such as anticipatory moves that exploit target dynamics, informationgathering moves that reduce target position uncertainty, and energy-conserving actions that allow the target to get out of sight, but do not compromise long-term tracking performance. To overcome the high computational complexity of solving POMDPs, we have developed SARSOP, a new point-based POMDP algorithm based on successively approximating the space reachable under optimal policies. Experimental results show that SARSOP is competitive with the fastest existing pointbased algorithm on many standard test problems and faster by many times on some.

Details

NeurIPS Conference 2007 Conference Paper

What makes some POMDP problems easy to approximate?

Wee Lee
Nan Rong
David Hsu

Point-based algorithms have been surprisingly successful in computing approx- imately optimal solutions for partially observable Markov decision processes (POMDPs) in high dimensional belief spaces. In this work, we seek to understand the belief-space properties that allow some POMDP problems to be approximated efﬁciently and thus help to explain the point-based algorithms’ success often ob- served in the experiments. We show that an approximately optimal POMDP so- lution can be computed in time polynomial in the covering number of a reachable belief space, which is the subset of the belief space reachable from a given belief point. We also show that under the weaker condition of having a small covering number for an optimal reachable space, which is the subset of the belief space reachable under an optimal policy, computing an approximately optimal solution is NP-hard. However, given a suitable set of points that “cover” an optimal reach- able space well, an approximate solution can be computed in polynomial time. The covering number highlights several interesting properties that reduce the com- plexity of POMDP planning in practice, e. g. , fully observed state variables, beliefs with sparse support, smooth beliefs, and circulant state-transition matrices.

PDF Details