decision_control/slotplanner.cc

   1 /*
   2 This file is part of I am car.
   3
   4 I am car is free software: you can redistribute it and/or modify
   5 it under the terms of the GNU General Public License as published by
   6 the Free Software Foundation, either version 3 of the License, or
   7 (at your option) any later version.
   8
   9 I am car is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with I am car. If not, see <http://www.gnu.org/licenses/>.
  16 */
  17
  18 #include <algorithm>
  19 #include <cmath>
  20 #include <list>
  21 #include <queue>
  22 #include "slotplanner.h"
  23
  24 ParallelSlot::ParallelSlot()
  25 {}
  26
  27 // getter
  28 std::vector<std::vector<RRTNode *>> &ParallelSlot::cusp()
  29 {
  30         return this->cusp_;
  31 }
  32
  33 float ParallelSlot::DH() const
  34 {
  35         return this->DH_;
  36 }
  37
  38 PolygonObstacle &ParallelSlot::slot()
  39 {
  40         return this->slot_;
  41 }
  42
  43 float ParallelSlot::slotHeading()
  44 {
  45         float y0 = this->slot().bnodes()[0]->y();
  46         float x0 = this->slot().bnodes()[0]->x();
  47         float y3 = this->slot().bnodes()[3]->y();
  48         float x3 = this->slot().bnodes()[3]->x();
  49         float dy = y0 - y3;
  50         float dx = x0 - x3;
  51         return atan2(dy, dx);
  52 }
  53
  54 SlotSide ParallelSlot::slotSide()
  55 {
  56         return this->slotSide_;
  57 }
  58
  59 SlotType ParallelSlot::slotType()
  60 {
  61         return this->slotType_;
  62 }
  63
  64 // setter
  65 void ParallelSlot::DH(float dh)
  66 {
  67         this->DH_ = dh;
  68 }
  69
  70 void ParallelSlot::setAll()
  71 {
  72         // slot side
  73         float y0 = this->slot().bnodes()[0]->y();
  74         float x0 = this->slot().bnodes()[0]->x();
  75         float y1 = this->slot().bnodes()[1]->y();
  76         float x1 = this->slot().bnodes()[1]->x();
  77         float y3 = this->slot().bnodes()[3]->y();
  78         float x3 = this->slot().bnodes()[3]->x();
  79         if (sgn((x1 - x3) * (y0 - y3) - (y1 - y3) * (x0 - x3)) < 0)
  80                 this->slotSide_ = LEFT;
  81         else
  82                 this->slotSide_ = RIGHT;
  83         // slot type
  84         float d1 = EDIST(
  85                 this->slot().bnodes()[0],
  86                 this->slot().bnodes()[1]
  87         );
  88         float d2 = EDIST(
  89                 this->slot().bnodes()[1],
  90                 this->slot().bnodes()[2]
  91         );
  92         if (d1 > d2)
  93                 this->slotType_ = PERPENDICULAR;
  94         else
  95                 this->slotType_ = PARALLEL;
  96 }
  97
  98 // other
  99 void ParallelSlot::fip()
 100 {
 101         // see https://courses.cs.washington.edu/courses/cse326/03su/homework/hw3/bfs.html
 102         // RRTNode.s() works as iteration level
 103         std::queue<BicycleCar *, std::list<BicycleCar *>> q;
 104         std::queue<BicycleCar *, std::list<BicycleCar *>> empty;
 105         int di = -1;
 106         if (this->slotSide() == LEFT)
 107                 di = 1;
 108         BicycleCar *CC = this->getEPC();
 109         BicycleCar *B = this->getEP();
 110         this->DH(di * 0.01 / CC->out_radi());
 111         BicycleCar *c;
 112         int i = 0;
 113         c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 114         while (!this->slot().collide(c->frame())) {
 115                 q.push(c);
 116                 c = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 117                 i += 1;
 118         }
 119         delete c; // not in q and collide
 120         while (!q.empty()) {
 121                 c = q.front();
 122                 q.pop();
 123                 if (this->isInside(c)) {
 124                         goto createcuspandfinish;
 125                 } else if (c->s() < 9) {
 126                         BicycleCar *cc = this->flnc(c);
 127                         cc->s(c->s() + 1);
 128                         cc->bcparent(c);
 129                         q.push(cc);
 130                 } else {
 131                         delete c; // not in q and collide
 132                 }
 133         }
 134         std::swap(q, empty);
 135         return;
 136 createcuspandfinish:
 137         std::vector<RRTNode *> cusp;
 138         while (c) {
 139                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 140                 c = c->bcparent();
 141         }
 142         std::reverse(cusp.begin(), cusp.end());
 143         this->cusp().push_back(cusp);
 144         std::swap(q, empty);
 145 }
 146
 147 void ParallelSlot::fipr(BicycleCar *B)
 148 {
 149         std::vector<RRTNode *> cusp;
 150         cusp.push_back(new RRTNode(B->x(), B->y(), B->h()));
 151         int di = 1;
 152         if (this->slotSide() == LEFT)
 153                 di = -1;
 154         if (this->slotType() == PERPENDICULAR) {
 155                 cusp.push_back(new RRTNode(
 156                         B->x() - di * B->length(),
 157                         B->y(),
 158                         B->h()
 159                 ));
 160                 std::reverse(cusp.begin(), cusp.end());
 161                 this->cusp().push_back(cusp);
 162                 return;
 163         }
 164         this->DH(di * 0.01 / B->out_radi());
 165         BicycleCar *c;
 166         c = this->flncr(B);
 167         c->s(B->s() + 1);
 168         while ((
 169                 this->slotSide() == LEFT
 170                 && this->slot().collide(new RRTNode(c->lfx(), c->lfy(), 0))
 171         ) || (
 172                 this->slotSide() == RIGHT
 173                 && this->slot().collide(new RRTNode(c->rfx(), c->rfy(), 0))
 174         )) {
 175                 cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 176                 BicycleCar *cc = this->flncr(c);
 177                 cc->s(c->s() + 1);
 178                 delete c;
 179                 c = cc;
 180         }
 181         cusp.push_back(new RRTNode(c->x(), c->y(), c->h()));
 182         std::reverse(cusp.begin(), cusp.end());
 183         this->cusp().push_back(cusp);
 184 }
 185
 186 BicycleCar *ParallelSlot::flnc(BicycleCar *B)
 187 {
 188         RRTNode *cc;
 189         if (this->slotSide() == LEFT) {
 190                 if (int(B->s()) % 2 == 0)
 191                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 192                 else
 193                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 194         } else {
 195                 if (int(B->s()) % 2 == 0)
 196                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 197                 else
 198                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 199         }
 200         BicycleCar *p;
 201         int i = 1;
 202         p = B->move(cc, i * this->DH());
 203         while (
 204                 !this->slot().collide(p->frame())
 205                 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
 206         ) {
 207                 delete p;
 208                 i += 10;
 209                 p = B->move(cc, i * this->DH());
 210         }
 211         i -= 10;
 212         p = B->move(cc, i * this->DH());
 213         while (
 214                 !this->slot().collide(p->frame())
 215                 && std::abs(this->slotHeading() - p->h()) < M_PI / 2
 216         ) {
 217                 if (this->isInside(p)) {
 218                         i += 1;
 219                         break;
 220                 }
 221                 delete p;
 222                 i += 1;
 223                 p = B->move(cc, i * this->DH());
 224         }
 225         delete p;
 226         return B->move(cc, (i - 1) * this->DH());
 227 }
 228
 229 BicycleCar *ParallelSlot::flncr(BicycleCar *B)
 230 {
 231         RRTNode *cc;
 232         if (this->slotSide() == LEFT) {
 233                 if (int(B->s()) % 2 == 0)
 234                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 235                 else
 236                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 237         } else {
 238                 if (int(B->s()) % 2 == 0)
 239                         cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 240                 else
 241                         cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 242         }
 243         BicycleCar *p;
 244         int i = 1;
 245         p = B->move(cc, i * this->DH());
 246         while (
 247                 !this->slot().collide(p->frame())
 248                 && ((
 249                         this->slotSide() == LEFT
 250                         && this->slot().collide(new RRTNode(
 251                                 p->lfx(),
 252                                 p->lfy(),
 253                                 0
 254                         ))
 255                 ) || (
 256                         this->slotSide() == RIGHT
 257                         && this->slot().collide(new RRTNode(
 258                                 p->rfx(),
 259                                 p->rfy(),
 260                                 0
 261                         ))
 262                 ))
 263         ) {
 264                 delete p;
 265                 i += 10;
 266                 p = B->move(cc, i * this->DH());
 267         }
 268         i -= 10;
 269         p = B->move(cc, i * this->DH());
 270         while (!this->slot().collide(p->frame())) {
 271                 if(
 272                         this->slotSide() == LEFT
 273                         && !this->slot().collide(new RRTNode(
 274                                 p->lfx(),
 275                                 p->lfy(),
 276                                 0
 277                         ))
 278                 ) {
 279                         i += 1;
 280                         break;
 281                 }
 282                 if(
 283                         this->slotSide() == RIGHT
 284                         && !this->slot().collide(new RRTNode(
 285                                 p->rfx(),
 286                                 p->rfy(),
 287                                 0
 288                         ))
 289                 ) {
 290                         i += 1;
 291                         break;
 292                 }
 293                 i += 1;
 294                 p = B->move(cc, i * this->DH());
 295         }
 296         delete p;
 297         return B->move(cc, (i - 1) * this->DH());
 298 }
 299
 300 RRTNode *ParallelSlot::fposecenter()
 301 {
 302         return this->slot().bnodes().front();
 303 }
 304
 305 bool ParallelSlot::flast(
 306         RRTNode *P,
 307         bool right,
 308         int il,
 309         std::vector<RRTNode *> &cusp
 310 )
 311 {
 312         BicycleCar *B = new BicycleCar(P->x(), P->y(), P->h());
 313         RRTNode *cc;
 314         if (right)
 315                 cc = BicycleCar(B->x(), B->y(), B->h()).ccr();
 316         else
 317                 cc = BicycleCar(B->x(), B->y(), B->h()).ccl();
 318         BicycleCar *p;
 319         int i = 1;
 320         p = B->move(cc, i * this->DH());
 321         while (!this->slot().collide(p->frame())
 322                         && (
 323                                 (this->DH() > 0 && p->x() <= 0)
 324                                 || (this->DH() < 0 && p->x() >= 0)
 325                         )) {
 326                 delete p;
 327                 i += 10;
 328                 p = B->move(cc, i * this->DH());
 329         }
 330         i -= 10;
 331         p = B->move(cc, i * this->DH());
 332         while (!this->slot().collide(p->frame())
 333                         && (
 334                                 (this->DH() > 0 && p->x() <= 0)
 335                                 || (this->DH() < 0 && p->x() >= 0)
 336                         )) {
 337                 if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 338                         i += 1;
 339                         break;
 340                 }
 341                 if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 342                         i += 1;
 343                         break;
 344                 }
 345                 delete p;
 346                 i += 1;
 347                 p = B->move(cc, i * this->DH());
 348         }
 349         delete p;
 350         p = B->move(cc, (i - 1) * this->DH());
 351         if (this->DH() > 0 && p->rfx() <= 0 && p->rrx() <= 0) {
 352                 cusp.push_back(p);
 353                 return true;
 354         } else if (this->DH() < 0 && p->lfx() >= 0 && p->lrx() >= 0) {
 355                 cusp.push_back(p);
 356                 return true;
 357         } else if (il < 8) {
 358                 cusp.push_back(p);
 359                 return this->flast(p, !right, il + 1, cusp);
 360         }
 361         return false;
 362 }
 363
 364 void ParallelSlot::fpose()
 365 {
 366         bool left = false; // right parking slot
 367         float di = -1;
 368         BicycleCar *CC = new BicycleCar(
 369                 this->fposecenter()->x(),
 370                 this->fposecenter()->y() - 0.01,
 371                 this->slotHeading()
 372         );
 373         BicycleCar *B = new BicycleCar(
 374                 CC->x() - CC->width() / 2,
 375                 CC->y() - (CC->length() + CC->wheelbase()) / 2,
 376                 this->slotHeading()
 377         );
 378         if (this->slot().bnodes()[0]->x() > this->slot().bnodes()[1]->x()) {
 379                 left = true;
 380                 di = 1;
 381                 delete B;
 382                 B = new BicycleCar(
 383                         CC->x() + CC->width() / 2,
 384                         CC->y() - (CC->length() + CC->wheelbase()) / 2,
 385                         this->slotHeading()
 386                 );
 387         }
 388         this->DH(di * 0.01 / CC->out_radi());
 389         BicycleCar *p;
 390         int i = 0;
 391         p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 392         while (!this->slot().collide(p->frame())) {
 393                 std::vector<RRTNode *> tmpcusp;
 394                 tmpcusp.push_back(new BicycleCar(p->x(), p->y(), p->h()));
 395                 if (this->flast(p, left, 0, tmpcusp)) {
 396                         this->cusp().push_back(tmpcusp);
 397                         return;
 398                 }
 399                 i += 1;
 400                 delete p;
 401                 p = B->move(CC, -i * di * 0.01 / CC->diag_radi());
 402         }
 403 }
 404
 405 BicycleCar *ParallelSlot::getEP()
 406 {
 407         // new pose for parallel parking to right slot
 408         float tnx;
 409         float tny;
 410         float nx;
 411         float ny;
 412         BicycleCar *CC = this->getEPC();
 413         // move left by car width / 2
 414         tnx = CC->x() + CC->width() / 2 * cos(CC->h() + M_PI / 2);
 415         tny = CC->y() + CC->width() / 2 * sin(CC->h() + M_PI / 2);
 416         if (this->slotSide() == LEFT) {
 417                 // move right by car width / 2
 418                 tnx = CC->x() + CC->width() / 2 * cos(CC->h() - M_PI / 2);
 419                 tny = CC->y() + CC->width() / 2 * sin(CC->h() - M_PI / 2);
 420         }
 421         if (this->slotType() == PARALLEL) {
 422                 // move down
 423                 nx = tnx - (CC->length() + CC->wheelbase()) / 2 * cos(CC->h());
 424                 ny = tny - (CC->length() + CC->wheelbase()) / 2 * sin(CC->h());
 425         } else {
 426                 // move down
 427                 nx = tnx + (CC->length() - CC->wheelbase()) / 2 * cos(CC->h());
 428                 ny = tny + (CC->length() - CC->wheelbase()) / 2 * sin(CC->h());
 429         }
 430         return new BicycleCar(nx, ny, CC->h());
 431 }
 432
 433 BicycleCar *ParallelSlot::getEPC()
 434 {
 435         // new pose for parallel parking to right slot
 436         float ta;
 437         float nx;
 438         float ny;
 439         ta = this->slotHeading() + M_PI;
 440         if (this->slotSide() == RIGHT)
 441                 ta -= M_PI / 4;
 442         else
 443                 ta += M_PI / 4;
 444         nx = this->fposecenter()->x() + 0.01 * cos(ta);
 445         ny = this->fposecenter()->y() + 0.01 * sin(ta);
 446         return new BicycleCar(nx, ny, this->slotHeading());
 447 }
 448
 449 BicycleCar *ParallelSlot::getFP()
 450 {
 451         float x = this->slot().bnodes()[3]->x();
 452         float y = this->slot().bnodes()[3]->y();
 453         float h = this->slotHeading();
 454         float nx;
 455         float ny;
 456         if (this->slotType() == PARALLEL) {
 457                 if (this->slotSide() == LEFT) {
 458                         nx = x + BCAR_WIDTH / 2 * cos(h + M_PI / 2);
 459                         ny = y + BCAR_WIDTH / 2 * sin(h + M_PI / 2);
 460                 } else {
 461                         nx = x + BCAR_WIDTH / 2 * cos(h - M_PI / 2);
 462                         ny = y + BCAR_WIDTH / 2 * sin(h - M_PI / 2);
 463                 }
 464                 x = nx + ((BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 + 0.01) * cos(h);
 465                 y = ny + ((BCAR_LENGTH - BCAR_WHEEL_BASE) / 2 + 0.01) * sin(h);
 466         } else {
 467                 if (this->slotSide() == LEFT) {
 468                         h -= M_PI / 2;
 469                         nx = x + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 470                                 * cos(h + M_PI);
 471                         ny = y + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 472                                 * sin(h + M_PI);
 473                         x = nx + (BCAR_WIDTH / 2 + 0.01) * cos(h + M_PI / 2);
 474                         y = ny + (BCAR_WIDTH / 2 + 0.01) * sin(h + M_PI / 2);
 475                 } else {
 476                         h += M_PI / 2;
 477                         nx = x + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 478                                 * cos(h - M_PI);
 479                         ny = y + (BCAR_LENGTH + BCAR_WHEEL_BASE) / 2
 480                                 * sin(h - M_PI);
 481                         x = nx + (BCAR_WIDTH / 2 + 0.01) * cos(h - M_PI / 2);
 482                         y = ny + (BCAR_WIDTH / 2 + 0.01) * sin(h - M_PI / 2);
 483                 }
 484         }
 485         return new BicycleCar(x, y, h);
 486 }
 487
 488 bool ParallelSlot::isInside(BicycleCar *c)
 489 {
 490         bool inside = true;
 491         RRTNode *tmpn;
 492         tmpn = new RRTNode(c->lfx(), c->lfy(), 0);
 493         if (!this->slot().collide(tmpn))
 494                 inside = false;
 495         delete tmpn;
 496         tmpn = new RRTNode(c->lrx(), c->lry(), 0);
 497         if (!this->slot().collide(tmpn))
 498                 inside = false;
 499         delete tmpn;
 500         tmpn = new RRTNode(c->rrx(), c->rry(), 0);
 501         if (!this->slot().collide(tmpn))
 502                 inside = false;
 503         delete tmpn;
 504         tmpn = new RRTNode(c->rfx(), c->rfy(), 0);
 505         if (!this->slot().collide(tmpn))
 506                 inside = false;
 507         delete tmpn;
 508         return inside;
 509 }
 510
 511 struct SamplingInfo ParallelSlot::getSamplingInfo()
 512 {
 513         struct SamplingInfo si;
 514         BicycleCar *CC = this->getEPC();
 515         si.x = this->slot().bnodes()[0]->x();
 516         si.y = this->slot().bnodes()[0]->y();
 517         if (this->slotSide() == RIGHT) {
 518                 si.dx = 1;
 519                 si.dy = 1;
 520                 si.dh = 1;
 521         } else {
 522                 si.dx = -1;
 523                 si.dy = -1;
 524                 si.dh = -1;
 525         }
 526         si.r = CC->diag_radi();
 527         si.sh = this->slotHeading();
 528         if (this->slotType() == PARALLEL) {
 529                 si.h = this->slotHeading() - acos(EDIST(
 530                         this->slot().bnodes()[0],
 531                         this->slot().bnodes()[1]
 532                 ) / BCAR_LENGTH);
 533         } else {
 534                 si.h = M_PI /2;
 535         }
 536         return si;
 537 }