# ELLIPTIC NET - A PATH PLANNING ALGORITHM FOR DYNAMIC ENVIRONMENTS

### Martin Saska, Miroslav Kulich, Libor Přeučil

#### 2006

#### Abstract

Robot path planning and obstacle avoidance problems play an important role in mobile robotics. The standard algorithms assume that a working environment is static or changing slowly. Moreover, computation time and time needed for realization of the planned path is usually not crucial. The paper describes a novel algorithm that is focused especially to deal with these two issues: the presented algorithm - Elliptic Net is fast and robust and therefore usable in highly dynamic environments. The main idea of the algorithm is to cover an interesting part of the working environment by a set of nodes and to construct a graph where the nodes are connected by edges. Weights of the edges are then determined according to their lengths and distance to obstacles. This allows to choose whether a generated path will be safe (far from obstacles), short, or weigh these two criterions. The Elliptic Net approach was implemented, experimentally verified, and compared with standard path planning algorithms.

#### References

- Aurenhammer, F. and Klein, R. (2000). Voronoi diagrams.. pages 201-290.
- Borenstein, J. and Koren, Y. (1991). The vector field histogram: Fast obstacle avoidance for mobile robots. IEEE Journal of Robotics and Automation.
- Braunl, T. and Tay, N. (2001). Combining configuration space and occupancy grid for robot navigation. 28(3):233-41.
- Jorgen, B. and Gutin, G. (1979). Digraphs: Theory, Algorithms and Applications. Elsevier North Holland.
- Khatib, O. (1986). Real-time obstacle avoidance for manipulators and mobile robots. The International Journal of Robotics Research, 5:90-98.
- Krajník, T., Faigl, J., and Pr?euc?il, L. (2006). Decision support by simulation in a robotic soccer domain. In MATHMOD 2006, ARGESIM-Reports.
- Kunigahalli, R. and Russell, J. (1994). Visibility graph approach to detailed path planning in cnc concrete placement.
- Latombe, J. (1991). Robot Motion Planning. MA: Kluwer, Norwell.
- Saska, M., Kulich, M., Klancar, G., and Faigl, J. (2006). Transformed net - collision avoidance algorithm for robotic soccer. In MATHMOD 2006.

#### Paper Citation

#### in Harvard Style

Saska M., Kulich M. and Přeučil L. (2006). **ELLIPTIC NET - A PATH PLANNING ALGORITHM FOR DYNAMIC ENVIRONMENTS** . In *Proceedings of the Third International Conference on Informatics in Control, Automation and Robotics - Volume 2: ICINCO,* ISBN 978-972-8865-60-3, pages 372-377. DOI: 10.5220/0001208403720377

#### in Bibtex Style

@conference{icinco06,

author={Martin Saska and Miroslav Kulich and Libor Přeučil},

title={ELLIPTIC NET - A PATH PLANNING ALGORITHM FOR DYNAMIC ENVIRONMENTS},

booktitle={Proceedings of the Third International Conference on Informatics in Control, Automation and Robotics - Volume 2: ICINCO,},

year={2006},

pages={372-377},

publisher={SciTePress},

organization={INSTICC},

doi={10.5220/0001208403720377},

isbn={978-972-8865-60-3},

}

#### in EndNote Style

TY - CONF

JO - Proceedings of the Third International Conference on Informatics in Control, Automation and Robotics - Volume 2: ICINCO,

TI - ELLIPTIC NET - A PATH PLANNING ALGORITHM FOR DYNAMIC ENVIRONMENTS

SN - 978-972-8865-60-3

AU - Saska M.

AU - Kulich M.

AU - Přeučil L.

PY - 2006

SP - 372

EP - 377

DO - 10.5220/0001208403720377