extended-abstract

Improving a Genetic Algorithm for Route Planning Using Parallelism with Speculative Execution

Authors:

H. David Mathias,

Samantha S. FoleyAuthors Info & Claims

PEARC '19: Practice and Experience in Advanced Research Computing 2019: Rise of the Machines (learning)

Article No.: 108, Pages 1 - 5

https://doi.org/10.1145/3332186.3333251

Published: 28 July 2019 Publication History

Abstract

A typical United Parcel Service (UPS) route consists of approximately 100 stops. The distance traveled to visit those 100 stops is determined by the order in which they are visited and the paths traveled between consecutive stops. This is an example of a problem we call route planning. The reward for finding short routes is substantial. UPS estimates that reducing each of their 55,000 North American routes by only 1 mile per day results in annual savings of up to $50,000,000, in fuel costs alone [18]. We approach the route planning problem with a novel, parallel genetic algorithm. We demonstrate the utility of parallelism for route planning by showing decreasing run times and solving much more complex problem instances that a non-parallel implementation of the same algorithm. By introducing speculative execution to the algorithm, we further, significantly improve the results.

References

[1]

Faez Ahmed and Kalyanmoy Deb. 2011. Multi-Objective Path Planning using Spline Representation. In Proc. IEEE Int'l Conf. Robotics & Biomimetics. 1047--1052.

[2]

K. S. Al-Sultan and M. D. S. Aliyu. 1996. A new potential field-based algorithm for path planning. Journal of Intelligent & Robotic Systems 17, 3 (1996), 265--282.

[3]

Gerardo Berbeglia, Jean-François Cordeau, Irina Gribkovskaia, and Gilbert Laporte. 2007. Static Pickup and Delivery Problems: A Classification Scheme and Survey. In TOP 15. 1--31.

[4]

Kris Braekers, Katrien Ramaekers, and Inneke Van Nieuwenhuyse. 2016. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering 99 (2016), 300--313.

Digital Library

[5]

N. Buniyamin, W. Wan Ngah, N. Shariff, and Z. Mohammad. 2011. A simple local path planning algorithm for autonomous mobile robots. Journal of Systems Applications, Engineering & Development 5, 2 (2011), 151--159.

[6]

Q. Chen, C. Liu, and Z. Xiao. 2014. Improving MapReduce Performance Using Smart Speculative Execution Strategy. IEEE Trans. Comput. 63, 4 (April 2014), 954--967.

Digital Library

[7]

H. Choset and P. Pignon. 1997. Coverage path planning: the boustrophedon decomposition. In International Conference on Field and Service Robotics.

[8]

Valeria de Carvalho Santos, Claudio Fabiano Motta Toledo, and Fernando Santos Osorio. 2015. An Exploratory Path Planning Method based on Genetic Algorithm for Autonomous Mobile Robots. In IEEE Congress on Evolutionary Computation.

[9]

Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (April 2002), 182--197.

Digital Library

[10]

D. Ferguson, M. Likachev, and A. Stentz. 2005. A guide to heuristic-based path planning. In Proc. Int'l Conf. on Automated Planning and Scheduling.

[11]

R. Glasius, A. Komoda, and S. Gielen. 1995. Neural Network dynamics for path planning and obstacle avoidance. Neural Networks 8, 1 (1995), 125--133.

Digital Library

[12]

I. Hasircioglu, H. Topcuoglu, and M. Ermis. 2008. 3-D path planning for the navigation of unmanned aerial vehicles by using evolutionary algorithms. In Genetic Algorithms and Evolutionary Computation Conference. ACM, 1499--1506.

Digital Library

[13]

Yong K. Hwang and Narendra Ahuja. 1992. Gross motion planning -- A survey. Comput. Surveys 24, 3 (1992), 219--291.

Digital Library

[14]

Shadi Ibrahim, Hai Jin, Lu Lu, Bingsheng He, Gabriel Antoniu, and Song Wu. 2012. Maestro: Replica-Aware Map Scheduling for MapReduce. In Proceedings of the 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (Ccgrid 2012) (CCGRID '12). IEEE Computer Society, Washington, DC, USA, 435--442.

Digital Library

[15]

H. Jun and Z. Qingbao. 2010. Multi-objective mobile robot path planning based on improved genetic algorithm. In IEEE International Conference on Intelligent Computation Technology and Automation. 752--756.

Digital Library

[16]

Shidong Li, Mingyue Ding, and Chao Cai. 2009. A novel path planning method based on path network. In 6th Int'l Symp Multispectral Image Processing and Pattern Recognition.

[17]

Edmund B. Nightingale, Peter M. Chen, and Jason Flinn. 2005. Speculative Execution in a Distributed File System. SIGOPS Oper. Syst. Rev. 39, 5 (Oct. 2005), 191--205.

Digital Library

[18]

UPS Press Office. 2018. Orion Backgrounder. (January 2018).

[19]

Vincent R. Ragusa, H. David Mathias, Vera A. Kazakova, and Annie S. Wu. 2017. Enhanced Genetic Path Planning for Autonomous Flight. In Proceedings of the ACM Genetic and Evolutionary Computation Conference. 1208--1215.

Digital Library

[20]

Ravi Rajwar and James R. Goodman. 2001. Speculative Lock Elision: Enabling Highly Concurrent Multithreaded Execution. In Proceedings of the 34th Annual ACM/IEEE International Symposium on Microarchitecture (MICRO 34). IEEE Computer Society, Washington, DC, USA, 294--305. http://dl.acm.org/citation.cfm?id=563998.564036

Digital Library

[21]

James E. Smith. 1981. A Study of Branch Prediction Strategies. In Proceedings of the 8th Annual Symposium on Computer Architecture (ISCA '81). IEEE Computer Society Press, Los Alamitos, CA, USA, 135--148. http://dl.acm.org/citation.cfm?id=800052.801871

Digital Library

[22]

John Towns, Timothy Cockerill, Maytal Dahan, Ian Foster, Kelly Gaither, Andrew Grimshaw, Victor Hazelwood, Scott Lathrop, Dave Lifka, Gregory D. Peterson, Ralph Roskies, J. Ray Scott, and Nancy Wilkins-Diehr. 2014. XSEDE: Accelerating Scientific Discovery. Computing in Science and Engineering 16, 5 (2014), 62--74.

[23]

J. Xiao, Z. Michalewicz, L. Zhang, and K. Trojanowski. 1997. Adaptive evolutionary planner/navigator for mobile robots. IEEE Trans Evol Comp 1, 1 (1997).

Digital Library

[24]

C. Zheng, M. Ding, C. Zhou, and L. Li. 2004. Coevolving and cooperating path planner for multiple unmanned air vehicles. Engineering Applications of Artificial Intelligence 17 (2004), 887--896.

Digital Library

Cited By

Singh JCheng J(2020)Automating the Generation of 3D Multiple Pipe Layout Design Using BIM and Heuristic Search MethodsProceedings of the 18th International Conference on Computing in Civil and Building Engineering10.1007/978-3-030-51295-8_6(54-72)Online publication date: 14-Jul-2020
https://doi.org/10.1007/978-3-030-51295-8_6

Recommendations

A parallel two-stage genetic algorithm for route planning
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion

Robotic path planning is an area of increasing importance given the interest in developing autonomous vehicles of all types and sizes. Consider, for example, a warehouse robot for a large internet commerce company. The robot's task is to retrieve a ...
Research of Route Planning Based on Genetic Algorithm
ICCSEE '12: Proceedings of the 2012 International Conference on Computer Science and Electronics Engineering - Volume 02

In this paper, a novel evolutionary algorithm is proposed for solving route planning problems. Firstly, the route planning attributes were analyzed in detail. Secondly, the constraint expressions, evaluation function, and genetic algorithm were ...
GP-genetic planning algorithm based on planning graph
AIAP'07: Proceedings of the 25th conference on Proceedings of the 25th IASTED International Multi-Conference: artificial intelligence and applications

In recent years, a new planning algorithm, graph plan, is presented and has a great impact on the development of intelligent planning. In graph planning, the algorithm has two main phases: Firstly, a directed, leveled graph with two kinds of nodes and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

PEARC '19: Practice and Experience in Advanced Research Computing 2019: Rise of the Machines (learning)

July 2019

775 pages

ISBN:9781450372275

DOI:10.1145/3332186

General Chair:
Tom Furlani
Roswell Park Comprehensive Cancer Center

Copyright © 2019 Owner/Author.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 July 2019

Check for updates

Qualifiers

Extended-abstract
Research
Refereed limited

Conference

PEARC '19

PEARC '19: Practice and Experience in Advanced Research Computing

July 28 - August 1, 2019

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 133 of 202 submissions, 66%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
55
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Singh JCheng J(2020)Automating the Generation of 3D Multiple Pipe Layout Design Using BIM and Heuristic Search MethodsProceedings of the 18th International Conference on Computing in Civil and Building Engineering10.1007/978-3-030-51295-8_6(54-72)Online publication date: 14-Jul-2020
https://doi.org/10.1007/978-3-030-51295-8_6

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents