| 1. |
- Krishnamurthy, Vikram, et al.
(författare)
-
A Value Iteration Algorithm for Partially Observed Markov Decision Process Multi-armed Bandits
- 2004
-
Ingår i:
-
Konferensbidrag (refereegranskat)abstract
- A value iteration based algorithm is given for computing the Gittins index of a Partially Observed Markov Decision Process (POMDP) Multi-armed Bandit problem. This problem concerns dynamical allocation of efforts between a number of competing projects of which only one can be worked on at any time period. The active project evolves according to a finite state Markov chain and generates then a reward, while the states of the idle projects remain fixed. In this contribution, it is assumed that the state of the active project only can be indirectly observed from noisy observations. The objective is to find the optimal policy based on partial information to determine which project to work on at a certain time in order to maximize the total expected reward. The solution is obtained by transforming the problem into a standard POMDP problem, for which there exist efficient near-optimal algorithms. A numerical example from the field of task planning for an autonomous robot is presented to illustrate the algorithms.
|
|
| 2. |
- Lingelbach, Frank
(författare)
-
Path planning for mobile manipulation using probabilistic cell decomposition
- 2004
-
Konferensbidrag (refereegranskat)abstract
- In the field of autonomous robotics, manipulation planning is a problem of major significance. A very important component within a manipulation planner is a path planner that is able to connect two configurations by a feasible continuous path, provided that such a path exists. Recently, a new probabilistic path planning method, Probabilistic Cell Decomposition (PCD), has been shown to perform well for - amongst other problems - motion planning for a robotic manipulator. In this paper we investigate how the performance of the general method can be further unproved when used within the context of manipulation planning by incorporating knowledge of a specific manipulator. We propose pre-computation of a cell decomposition covering self-collision, adjustment of the cell splitting procedure to the articulated structure of the robot and tuning of distance metrics with respect to the robot. To evaluate the algorithms, we present simulations of a Puma 560 robot arm mounted on a Nomadic XR4000 mobile platform.
|
|
| 3. |
- Lingelbach, Frank
(författare)
-
Path planning using probabilistic cell decomposition
- 2004
-
Ingår i: 2004 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION, VOLS 1- 5, PROCEEDINGS. - 0780382323 ; , s. 467-472
-
Konferensbidrag (refereegranskat)abstract
- In this paper we present a new approach to path planning in high-dimensional static configuration spaces. The concept of cell decomposition is combined with probabilistic sampling to obtain a method called Probabilistic Cell Decomposition (PCD). The use of lazy evaluation techniques and supervised sampling in important areas leads to a very competitive path planning method. It is shown that PCD is probabilistic complete. PCD is easily scalable and applicable to many different kinds of problems. Experimental results show that PCD performs well under various conditions. Rigid body movements, maze like problems as well as path planning problems for chain-like robotic platforms have been solved successfully using the proposed algorithm.
|
|
| 4. |
- Lingelbach, Frank
(författare)
-
Path planning using probabilistic cell decomposition
- 2005
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The problem of path planning occurs in many areas, such as computational biology, computer animations and computer-aided design. It is of particular importance in the field of robotics. Here, the task is to find a feasible path/trajectory that the robot can follow from a start to a goal configuration. For the basic path planning problem it is often assumed that a perfect model of the world surrounding the robot is known. In industrial robotics, such models are often based on, for example, CAD models. However, in applications of autonomous service robotics less knowledge about the environment is available. Efficient and robust path planning algorithms are here of major importance. To be truly autonomous, a robot should be able to plan all motions on its own. Furthermore, it has to be able to plan and re-plan in real time, which puts hard constraints on the acceptable computation time. This thesis presents a novel path planning method called Probabilistic Cell Decomposition (PCD). This approach combines the underlying method of cell decomposition with the concept of probabilistic sampling. The cell decomposition is iteratively refined until a collision-free path is found. In each immediate step the current cell decomposition is used to guide probabilistic sampling to important areas. The basic PCD algorithm can be decomposed into a number of components such as graph search, local planning, cell splitting and probabilistic sampling. For each component different approaches are discussed. The performance of PCD is then tested on a set of benchmark problems. The results are compared to those obtained by one of the most commonly used probabilistic path planning methods, namely Rapidly-exploring Random Trees. It is shown that PCD efficiently solves various kinds of path planning problems. Planning for autonomous manipulation often involves additional path constraints beyond collision avoidance. This thesis presents an application of PCD to path planning for a mobile manipulator. The robot has to fetch a carton of milk from the refrigerator and place it on the kitchen table. Here, opening the refrigerator involves motion with a pre-specified end-effector path. The results show that planning the different motions for the high-level task takes less time than actually executing them. The whole series of subtasks takes about 1.5 seconds to compute.
|
|
